Linked Lists

The opposite trade from arrays

An array buys O(1) indexing with contiguous memory and pays O(n) to insert. A linked list takes the exact opposite deal: each element (node) lives anywhere in memory and carries a pointer (reference — Level 1 concept) to the next node:

HEAD → [40|•] → [60|•] → [90|•] → [25|∅]
        data next

A treasure hunt instead of a row of lockers: each clue tells you where the next one is. Consequences:

Insertion is the magic: to add between A and B, create node X, point A at X, point X at B. No shifting — the neighbors never move; only two pointers change. Deletion is the same trick backwards: point A past X, and X is gone.

Implementation

# Python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None        # pointer to the next Node (or None at the end)

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

    def push_front(self, val):          # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def delete(self, val):              # O(n) find, O(1) unlink
        cur = self.head
        if cur and cur.val == val:
            self.head = cur.next        # special case: deleting the head
            return
        while cur and cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next   # unlink
                return
            cur = cur.next

    def traverse(self):                 # the universal loop shape
        cur = self.head
        while cur:
            print(cur.val)
            cur = cur.next

// Java
class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}

// C++ — the one language where you free nodes yourself
struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};
// delete a node: prev->next = cur->next; delete cur;  ← manual memory!

That while cur: ... cur = cur.next loop is to linked lists what for i in range(n) is to arrays — every algorithm on this page is a variation of it.

The dummy-head trick

Notice delete needed a special case for the head. Interviews punish that. The fix: a dummy (sentinel) node before the real head, so every node has a predecessor and one code path handles all cases:

def delete(self, val):
    dummy = Node(0)
    dummy.next = self.head
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next
            break
        cur = cur.next
    self.head = dummy.next      # head may have changed; dummy knows

Reach for a dummy head whenever the head itself might be modified — merging, deleting, partitioning. It's the single highest-value linked-list habit.

Variants in one breath

• Doubly linked — nodes also point backward (prev), so you can walk both ways and delete a node given only the node in O(1). Cost: one more pointer to maintain. This is the engine inside an LRU cache.
• Circular — the tail points back to the head; used for round-robin scheduling.

Watch a reversal

The classic three-pointer dance: save next, flip the arrow, advance. Watch the green (already-flipped) arrows grow — and notice why saving next first is non-negotiable.

The two-pointer toolkit

Linked lists can't be indexed, so their classic problems are solved by walking pointers at different speeds or offsets — two pointers, born here:

• Middle of the list: slow moves 1, fast moves 2; when fast hits the end, slow is at the middle.
• Cycle detection (Floyd's): same setup; if they ever meet, there's a loop.
• k-th from the end: lead pointer starts k ahead; move both; when lead ends, trail is the answer.

And the king of them all — in-place reversal, the most-asked linked-list question in existence:

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # save where we're going
        cur.next = prev     # flip the arrow
        prev = cur          # advance prev
        cur = nxt           # advance cur
    return prev             # new head

Three pointers, one pass, O(1) space. Draw four nodes on paper and run this by hand until the pointer dance is boring — that's the bar.

Production perspective

• Linked lists hide inside things you use daily: the LRU cache's doubly linked list (full LLD treatment), OS run-queues, memory allocators' free lists, and hash-table collision chains — next page.
• Honest engineering note: as a general-purpose container, arrays usually win in practice even where lists win on paper — pointer-chasing defeats CPU caches (arrays page). Lists earn their keep when you hold a node reference and need O(1) splice — exactly the LRU pattern. Saying this trade-off out loud is senior-signal in interviews.

Common mistakes

• Losing the rest of the list — assigning cur.next before saving it. The nxt = cur.next line in reverse is load-bearing; reorder it and the list evaporates.
• Null-pointer crashes — fast.next.next when fast.next is None. Guard: while fast and fast.next: — the order of those checks matters (short-circuit).
• Forgetting the head can change — return the (possibly new) head; better, use a dummy.
• Infinite loops on cycles — while cur: never ends on a circular list; that's why cycle detection exists.
• Off-by-one in k-th-from-end — decide "k=1 means the last node" upfront and test with a 1-node list.

Interview perspective

Practice

1. Build: implement push_front, push_back, delete, and traverse from memory — then add the dummy-head version of delete and diff the two.
2. The canon (all on paper first, then code): reverse a list; find the middle; detect a cycle; merge two sorted lists into one sorted list (dummy head shines here).
3. Combiner: reorder a list A→B→C→D→E into A→E→B→D→C. Hint: it's three problems from this page glued together — middle, reverse, merge.
4. Think: your music app's "up next" queue supports play-next (insert at front), append, and skip-to-song-5. Which operations favor a list, which favor an array, and what would you actually use?

Next: Stacks & Queues — restricting access to gain power.

Practice — climb the ladder

Every linked-list problem is pointer surgery: draw boxes and arrows before typing, and re-draw after every operation.