Linked List Data Structure

A Linked list is a data structure which can store a collection of items. All the items in a linked list are stored in the form of a sequence made up of multiple nodes. Each node stores a value/item and also points out (links) to the next node in the sequence.

Linked lists store collection of items similar to arrays. But unlike arrays, the items are not stored in continuous block of memory and also memory is not reserved in advance. Later in this article, we will discuss about the benefits of using linked lists instead of using contiguous data structures like arrays.

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 standing at the last compartment of a train, which has doors allowing you to move only to the compartment ahead but not behind. You can look into contents of your current compartment and also move to the next compartment.

In order to move forward or reach the front of the train, you have to pass through each compartment sequentially until there are no more compartments at the end.

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, usually from the back to the front. In this analogy last compartment of the train can be considered as head node and the engine can be considered as tail node of the linked list.

Doubly Linked List

Now, picture a train where each compartment has doors both in the front and back, allowing 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 and pointers to both the next and previous nodes, enabling movement in both forward and backward directions within the train (linked list).

Anatomy of a Linked List

A linked list is made up of a chain of multiple nodes. Each node can store an item/element along with the address of the next node in the sequence. For example, the illustration below is a linked list containing 3 items “A”, “B” & “C” in that sequence.

You can observe that there is a 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”. Again 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. This type of linked list is named as singly linked list as each node points to a maximum of one other node.

The first node among the sequence of all the nodes in the linked list is termed as the “head node” and the last node in the sequence which does not point to any other node is termed as the “tail node”.

One other commonly used type of linked list is a doubly linked list in which each node points to the previous node in the sequence and also the next node in the sequence. Below is how it looks (Source):

Representation of Singly Linked List

The nodes which make up a linked list need to store two components:

• Value/Item: Represents the stored information.
• Pointer/Reference to the next node in the sequence.

Below is how definition of a singly linked list node looks like:

class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

Let’s now go through a basic representation of linked list data structure to form the below list in different programming languages.

# Node class to store a item/value and link to the next node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

# We need to create the nodes first before linking them
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# node1 is the head node in the linked list
head = node1
# node4 is the tail node in the linked list
tail = node4

# let's print all the items using head node
cnode = head
while cnode != None:
    print(cnode.item, end=" ")
    cnode = cnode.next

#include <stdio.h>
#include <stdlib.h>

// Node structure to store an item/value and a link to the next node
struct Node {
    char *item;
    struct Node *next;
};

int main() {
    // Create and allocate memory for each node
    struct Node *node1 = malloc(sizeof(struct Node));
    struct Node *node2 = malloc(sizeof(struct Node));
    struct Node *node3 = malloc(sizeof(struct Node));
    struct Node *node4 = malloc(sizeof(struct Node));

    // Assigning items to nodes
    node1->item = "A";
    node2->item = "B";
    node3->item = "C";
    node4->item = "D";

    // Link nodes in sequence to form a linked list
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;

    // node1 is the head node in the linked list
    // node4 is the tail node in the linked list

    // Printing items in the linked list using the head node
    struct Node *cnode = node1;
    while (cnode != NULL) {
        printf("%s ", cnode->item);
        cnode = cnode->next;
    }

    // Let's free the allocated memory
    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

#include <iostream>
using namespace std;

// Node class to store an item/value and link to the next node
class Node {
public:
    Node(string item):item(item){}
    string item;
    Node* next;
};

int main() {
    // We need to create the nodes first before linking them
    Node* node1 = new Node("A");
    Node* node2 = new Node("B");
    Node* node3 = new Node("C");
    Node* node4 = new Node("D");

    // Let's Link nodes in a sequence to form a linked list
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = nullptr;

    // node1 is the head node in the linked list
    // node4 is the tail node in the linked list

    // Let's Print all items in the linked list using the head node
    Node* cnode = node1;
    while (cnode != nullptr) {
        cout << cnode->item << " ";
        cnode = cnode->next;
    }

    // Deleting allocated memory
    delete node1;
    delete node2;
    delete node3;
    delete node4;

    return 0;
}

// Node class to store an item/value and link to the next node
class Node {
    constructor(item) {
        this.item = item;
        this.next = null;
    }
}

// We need to create the nodes first before linking them
let node1 = new Node("A");
let node2 = new Node("B");
let node3 = new Node("C");
let node4 = new Node("D");

// Let us now link/chain the nodes in order
// to form a linked list
node1.next = node2;
node2.next = node3;
node3.next = node4;

// node1 is the head node in the linked list
// node4 is the tail node in the linked list

// let's print all the items using head node
let cnode = node1;
while (cnode !== null) {
    console.log(cnode.item + " ");
    cnode = cnode.next;
}

// Node class to store an item/value and link to the next node
class Node {
    String item;
    Node next;

    Node(String item) {
        this.item = item;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        // Creating nodes
        Node node1 = new Node("A");
        Node node2 = new Node("B");
        Node node3 = new Node("C");
        Node node4 = new Node("D");

        // Linking nodes to form a linked list
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        // Printing items using the head node
        Node cnode = node1;
        while (cnode != null) {
            System.out.print(cnode.item + " ");
            cnode = cnode.next;
        }
    }
}

Note that once a linked list is created, access to internal nodes like node2, node3 etc is not held. Only the head and tail nodes are directly visible/accessible to the users of linked list. Other nodes are accessed by traversing the list using head node.

Linked Lists v/s Arrays

Advantages

• Arrays reserve certain memory before hand and consume that memory even if the array is empty. Whereas for linked lists, total memory consumed is the sum of memory consumed by all the nodes in the list. So in cases where the usage of reserved memory in arrays is less, linked lists can be a better alternative since memory is reserved on demand. But in some cases, because of the extra space required by a linked list node to store the next node info, it might end up taking more space than an array.

• When the reserved memory for array is completely filled up, a larger memory has to be reserved and all the items in the array needs to be copied to the newly reserved memory, which might take time. In these scenarios, a linked list is really efficient since adding any element to the end of list is as simple as creating a new node and attaching it to the tail of linked list.

• Also, since all the nodes in a linked list are chained together and each chain can be easily modified, insertions or deletions of nodes anywhere in the linked list is easy and efficient. Where as in array, all the elements towards the right of where we add/remove item has to be shifted by one position, which consumes more time.

Disadvantages

• Random Access: Arrays allow for direct and constant-time random access to elements using an index, whereas linked lists require traversing the list from the beginning (or end) to access a specific element, which is generally less efficient.
• Cache Performance: Arrays provide better cache performance because their elements are stored in contiguous memory locations. Linked lists, with their scattered memory locations, may result in poorer cache utilization and can be less cache-friendly.
• Overhead in Implementing: Implementing linked lists can be more complex than arrays, especially if you need to manage memory manually. Linked lists require allocating and deallocating memory for nodes and handling pointer manipulation, which can introduce more opportunities for bugs.

Operations on a Linked List

Some of the basic operations that can be performed on a linked list are

• Traversing all nodes in a linked list from head to tail
• Appending a new node to the end of the list
• Prepending a new node to the beginning of the list
• Inserting a new node after a specific node in the list
• Deleting head or tail node
• Deleting a node present in between the list

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

References

• Linked List (OpenDSA)
• Basic Operations Supported
• Operations on Linked List with Illustrations