Linked List

What is a linked list?

A linked list is a chain of nodes. Each node stores two things:

1. the data (a value, like 45), and
2. a pointer (next) — the memory address of the next node in the chain.

A separate pointer called head remembers where the first node is. The last node’s next is NULL, meaning “the chain ends here”.

Analogy: a treasure hunt. Each clue (node) contains a prize (data) and tells you where to find the next clue (pointer). To reach the 5th clue you must follow clues 1, 2, 3 and 4 first.

In the 3D model each node is drawn as a blue data box with a grey pointer box attached, and the arrows are the pointers.

Linked list vs array

	Array	Linked list
Memory	One continuous block	Nodes scattered anywhere
Access the i-th element	O(1) — calculate the address	O(n) — walk from head
Insert at the front	O(n) — shift everything	O(1) — change two pointers
Size	Usually fixed	Grows and shrinks freely
Extra memory	None	One pointer per node

Use a linked list when you insert and delete a lot (especially at the front) and rarely need “give me element #i”.

Insertion

At the head — O(1):

1. Create the new node.
2. node.next = head (the new node points to the old first node).
3. head = node.

In the middle (after node curr) — O(1) once you are there:

1. node.next = curr.next
2. curr.next = node

The order matters. If you did step 2 first, curr.next would already point to the new node and the rest of the list would be lost forever. The 3D model shows these two pointer changes as separate steps so you can see why.

At the tail — O(n): you have to walk from the head to the last node first. (Many implementations keep an extra tail pointer to make this O(1).)

Deletion

To delete a node, find it while remembering the node before it (prev). Then make prev skip over it:

prev.next = curr.next

If the node is the first one, just move the head: head = head.next. In C/C++ you would also free/delete the removed node; in Python and Java the garbage collector does it.

Reversing a linked list (a classic interview question)

We walk the list once with three pointers — prev, curr and next — and flip each arrow to point backwards:

prev = NULL
curr = head
while curr != NULL:
    next = curr.next     # 1. save the rest of the list
    curr.next = prev     # 2. flip the arrow
    prev = curr          # 3. move prev forward
    curr = next          # 4. move curr forward
head = prev

Press Reverse list and step through it — in 3D you can literally watch each pointer box swing to the other side.

Code

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

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, x):
        node = Node(x)
        node.next = self.head
        self.head = node

    def insert_at_tail(self, x):
        node = Node(x)
        if self.head is None:
            self.head = node
            return
        curr = self.head
        while curr.next is not None:
            curr = curr.next
        curr.next = node

    def delete(self, x):
        prev, curr = None, self.head
        while curr is not None and curr.value != x:
            prev, curr = curr, curr.next
        if curr is None:
            return                      # not found
        if prev is None:
            self.head = curr.next       # deleting the first node
        else:
            prev.next = curr.next

    def reverse(self):
        prev, curr = None, self.head
        while curr is not None:
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        self.head = prev

    def __str__(self):
        out, curr = [], self.head
        while curr:
            out.append(str(curr.value))
            curr = curr.next
        return " -> ".join(out + ["NULL"])

lst = LinkedList()
for v in [12, 45, 7, 30]:
    lst.insert_at_tail(v)
lst.reverse()
print(lst)   # 30 -> 7 -> 45 -> 12 -> NULL

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

Node* insertAtHead(Node* head, int x) {
    Node* node = new Node(x);
    node->next = head;
    return node;                     // new head
}

Node* removeValue(Node* head, int x) {
    Node *prev = nullptr, *curr = head;
    while (curr && curr->value != x) { prev = curr; curr = curr->next; }
    if (!curr) return head;          // not found
    if (!prev) head = curr->next;    // deleting the first node
    else prev->next = curr->next;
    delete curr;
    return head;
}

Node* reverse(Node* head) {
    Node *prev = nullptr, *curr = head;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;                     // new head
}

int main() {
    Node* head = nullptr;
    for (int v : {30, 7, 45, 12}) head = insertAtHead(head, v);
    head = reverse(head);
    for (Node* c = head; c; c = c->next) cout << c->value << " -> ";
    cout << "NULL\n";                // 30 -> 7 -> 45 -> 12 -> NULL
}

Types of linked lists

• Singly linked list — each node points to the next (shown here).
• Doubly linked list — each node also has a prev pointer, so you can walk backwards and delete a node in O(1) when you have it.
• Circular linked list — the last node points back to the head instead of NULL.

Where are linked lists used?

• Implementing stacks and queues that can grow without limit.
• Music playlists and browser history (doubly linked: next / previous).
• Hash tables use linked lists to store items that land in the same bucket (chaining).
• The operating system keeps lists of free memory blocks.

Common mistakes

• Losing the rest of the list by overwriting next before saving it.
• Forgetting to update head when inserting or deleting at the front.
• Dereferencing NULL: always check curr != NULL before using curr.next.