Basics of Linked List Data Structure

A linked list is a fundamental data structure in computer science that can store and manage a collection of items. Unlike arrays, which use contiguous memory locations, linked lists consist of a sequence of nodes, with each node containing data and a reference to the next node in the sequence. This unique structure allows for dynamic memory allocation and efficient insertion and deletion operations, making linked lists particularly useful in scenarios where the size of the data set is unknown or frequently changing.

Structure of a Linked List

A linked list is made up of a sequence of multiple nodes. You can think of each node as a container that has enough memory to store two key components: the data it holds, and a reference (or link or address) to the next node in the sequence. Below is how a node in singly linked list looks like:

Let’s say we need to store the elements A, B & C in the linked list in that order. First, a dedicated node is created for each element which needs to be stored. Then, each element is stored in a node along with the address to the node corresponding to the next element in sequence. Below is how the linked list looks like after all the nodes are chained together:

You can observe that there is a unique node corresponding to each item stored in the linked list. Also if you look at the node holding the item A, it also points to the next node in the sequence which holds the item B. Similarly, the node holding item B points to the next node in the sequence which holds the item C. Item C is the end of list, so it does not point to any other node.

The first node in a linked list is termed as the “head node”. Head node is the only node in the linked list to which no other node points to. The last node in the sequence which does not point to any other node is termed as the “tail node”.

The linked list shown above is a kind of singly linked list since each node can link to a maximum of one other node. One other commonly used variation of linked list is a doubly linked list. In a doubly linked list, each node points to the previous node in the sequence and also the next node in the sequence. Below is how it looks:

Why do we need Linked Lists?

In the previous section, we explored Array Data Structure and their role as building blocks for various algorithms and applications. However, a key drawback of arrays is their fixed size, making dynamic element addition or removal challenging. Arrays also require contiguous memory blocks, which can be problematic for large datasets or in memory-constrained environments. Moreover, arrays are inefficient for insertions and deletions, especially at the beginning, as these operations often require shifting multiple elements in computer memory.

Linked Lists address these issues and offer several advantages:

Dynamic size: Linked Lists can grow or shrink as needed, without requiring reallocation of existing memory or already created nodes.
Efficient memory usage: Nodes in a Linked List can be stored in non-contiguous memory locations, making better use of available memory.
Easy insertions and deletions: Adding or removing elements from any position in a Linked List is efficient, as it only involves updating a few pointers.
Flexibility in rearrangement: Reordering elements in a Linked List is simple and doesn’t require moving large blocks of memory.

These characteristics make Linked Lists particularly useful in scenarios where frequent insertions, deletions, or rearrangements are necessary, and when dealing with dynamic data sets of unknown size.

Real world Analogy

Consider a running train made up of a long chain of compartments. Think of each compartment in the train as a container used to store a specific item. Let’s see how it can be related to linked lists.

Singly linked list

Imagine yourself standing at the engine compartment of a train (Marked as A in the image). Let’s say the train has doors allowing you to move only towards the end of the train but not towards the engine side of the train. For example, if you are in compartment B, you can move to compartment C but not towards compartment A. All you can do is observe or modify the contents of current compartment, and also move to the next compartment. This also means that if you wish to visit compartment D, you can’t instantly visit it, you need to go through B and C compartments and finally reach compartment D.

Similarly, in a singly linked list (train), each node (compartment) contains data and a pointer to the next node, enabling movement only in one direction. In this analogy engine compartment (A) of the train can be considered as head node and the last compartment (D) can be considered as a tail node.

Doubly Linked List

Now, picture a train where each compartment has doors which allows movement in either direction. You can stand in any compartment and move to the next or previous compartment freely. This setup resembles a doubly linked list where each node (compartment) contains data along with pointers to both the next and previous nodes, enabling movement in both forward and backward directions within the linked list.

Because of the way nodes are linked, addition/removal/rearrangement of nodes can be done just by shuffling the links between the nodes, instead of copying entire data all over again. Click here to learn more about how memory is managed for linked lists and how each node looks like in computer memory.

Operations on a Linked List

Below are some of the basic operations that can be performed on a linked list (Click on the links on each operation to learn more about it):

Traversal/Iteration: Traversal/Iteration refers to the process of visiting each element in the array sequentially. This operation is commonly used to perform actions on all elements present in the linked list or to find specific elements based on certain conditions. Traversal usually has a time complexity of O(n), where n is the number of elements in the linked list.
Insertion: This operation involves adding a new node to the linked list. This can be done at the beginning (head), end (tail), or at a specific position. Insertion at the head or tail typically has a time complexity of O(1), while insertion at a specific position has a time complexity of O(n) in the worst case.
Deletion: This operation involves removing a node from the linked list. Similar to insertion, this can be done at the beginning, end, or at a specific position. Deletion at the head has a time complexity of O(1), while deletion at the end or at a specific position has a time complexity of O(n) in the worst case.
Search: This operation involves finding a specific element in the linked list by traversing/iterating the list until the desired element is found or the end of the list is reached. The time complexity for searching is O(n) in the worst case.
Update: Modifying the value of an existing node in the linked list. If the position of the node is known, updating can be done in O(1) time. However, if searching is required to find the node, the time complexity becomes O(n).
Reverse: Inverting the order of elements in the linked list. This operation typically involves traversing the list once and adjusting the pointers, resulting in a time complexity of O(n).
Concatenation: Joining two linked lists together. If the reference to the last node of the first list is available, concatenation can be done in O(1) time. Otherwise, it requires traversing the first list, resulting in O(n) time complexity.

We will go through each operation in detail along with code examples in the next sections.