Little Known Ways to Link Lists

by Vibrant Publishers

A linked list is a list of connected nodes. Each node stores the value and address of the next or the previous node. Since the address is stored in the node, linked lists can be dynamically allocated. Linked lists are used in implementing dynamic arrays, stacks, and queues. However, they consume extra memory for storing the address of the next node. These sequential lists are very cumbersome for traversing longer lists.

Array vs Linked List:

Compared to an array, a linked list can be easily traversed if the list size is smaller. Unlike arrays linked list items cannot be randomly accessed. Lists store the address of the next node, hence consuming more space. The below picture shows how a linked list can store items anywhere and be accessed by the address sequentially. The address can be used to locate the element. This makes insertion, deleting or updating operations in a linked list faster.

Arrays are stored in memory sequentially and accessed using the array index. Hence, arrays take a longer time to insert, delete or update.

Types of Linked Lists:

Linked lists are of 3 main types:

A Singly linked list:

They contain a list of nodes that have a value and address to the next node. The last node’s address is always null. The below illustration shows that a singly linked list can traverse forward only.

Stacks, queues and dynamic arrays are some implementation areas where singly linked lists are used. They are best suited for smaller forward traversals and when the address to the element is unknown.

A Doubly linked list:

A doubly linked list has 3 parts – node value, address to the next node and address to the previous node. The first node’s address to the previous element and the last node’s address to the next node will always be null. A doubly linked list can hence traverse both forward and backward.

We use a doubly linked list to navigate either forward or backward direction, when using an array or other data structures. However, both the next and previous address needs to be stored in the node and hence consume more memory.

A Circular linked list:

When the last node’s address points to the first node, the linked list is called a circular linked list. A circular linked list can be singly or doubly linked.

Below is an example of a singly linked circular list.

A doubly linked circular list is just like the doubly linked list except that the last node’s next pointer stores the address of the first node and the first node’s previous pointer stores the address of the last node.

The operating system’s task scheduler, circular queues and multi-player games are great real-world examples of a circular linked list.

Learn more about Linked List operations here.

Get one step closer to your dream job!

Pave the route to your dream job by preparing for your interview with questions from our Job Interview Questions Book Series. These provide a comprehensive list of questions for your interview regardless of your area of expertise. These books include:

You can find them on our website!

Back to blog