🧩 Data Structures & Algorithms · Chapter 8

Linked lists

An array keeps its items shoulder to shoulder, so squeezing one in moves everyone. A linked list keeps each item wherever it likes and just remembers who comes next — so inserting is rewiring one arrow.

Study this lesson free in the app →

The basics

A linked list is a chain of nodes, where each node holds a value and a pointer (next) to the following node. The list itself is just a reference to the first node, the head; the last node points to nothing (None).

The problem it solves: in an array, inserting or deleting near the front shifts every later item — O(n). In a linked list, nodes can live anywhere in memory, so once you're at the right spot, inserting or deleting is just changing one or two pointers — O(1). The price: there's no index arithmetic. To reach the 500th node you must follow 499 arrows — O(n).

The mental model: a treasure hunt. Each clue tells you where the next clue is hidden. Adding a new clue between two others means rewriting one clue. Finding clue number 40 means walking through the first 39.

Space is O(n), plus one pointer per node (two for doubly linked).

Explained

Insert one song at the start of a 100,000-song playlist stored as an array: 100,000 songs shift one place.

Store it as a linked list: create one node, point it at the old first song, call it the new head. Two pointer writes.

But ask the linked list for song number 50,000, and it has to walk past 49,999 others to find it. Every data structure is a trade; this is the linked list's.

The treasure hunt

At a birthday party, each clue is hidden somewhere different, and each one says where the next is: "under the blue chair", "behind the clock", "in the left boot".

Adding a clue between "blue chair" and "clock" is easy: hide the new clue, then rewrite the blue-chair clue to point to it, and make the new clue point to the clock. Nothing else moves.

Removing a clue is just as easy: rewrite the clue before it to skip past it.

But if a child asks "where's clue number 9?", nobody knows without starting at clue 1 and following the trail. And if someone accidentally writes "go back to the blue chair" on a later clue, the hunt loops forever — a cycle.

Precisely

head
 │
 ▼
[ 3 | •]──▶[ 8 | •]──▶[ 2 | •]──▶ None

| Operation | Singly linked | Array | | --- | --- | --- | | access i-th item | O(n) | O(1) | | search by value | O(n) | O(n) | | insert/delete at front | O(1) | O(n) | | insert/delete after a node you hold | O(1) | O(n) | | append at end | O(1) with a tail pointer, else O(n) | O(1) amortised | | delete the last node | O(n) — need its predecessor | O(1) |

Doubly linked lists add a prev pointer to every node. Cost: more memory. Benefit: walk both ways, delete any node you hold in O(1) (it knows its own predecessor), and with a tail pointer, O(1) at both ends.

Why "O(1) insert" needs care: it's O(1) once you're at the position. Inserting at position 5,000 still means walking 5,000 nodes first.

Insert, delete, find

insert 5 at 1: walk to the node before position 1, point the new node at 4, point 1 at the new node — 1 → 5 → 4 → 7. No other node moves. delete 4: point 5 past 4, straight at 7. find 7: there's no shortcut — follow arrows from the head, 1 → 5 → 7. Rewiring is O(1); getting there is O(n).

Reverse the chain in place

Reverse walks the list once and flips each arrow to point backwards, so 3 → 8 → 2 → 6 → 9 becomes 9 → 6 → 2 → 8 → 3 without creating a single new node: O(n) time, O(1) space. Then find 3 has to walk all five nodes — 3 used to be the head and is now the tail.

The core operations

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

def push_front(head, val):           # O(1)
    return Node(val, head)           # new node becomes the head

def delete(head, target):            # O(n) to find, O(1) to unlink
    dummy = Node(0, head)            # sentinel: the head is no longer special
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next   # skip over it
            break
        prev = prev.next
    return dummy.next

def middle(head):                    # fast/slow: O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:
        slow = slow.next             # 1 step
        fast = fast.next.next        # 2 steps
    return slow                      # even length -> second middle

def has_cycle(head):                 # Floyd's algorithm
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:             # same node, not just same value
            return True
    return False

Where linked lists earn their keep

Honest truth first: for most everyday jobs, an array is faster even where Big-O says otherwise. Array items sit next to each other, so the CPU fetches dozens at once; linked-list nodes are scattered, so each next can be a slow trip to main memory. Each node also carries pointer overhead — in Python a small node object costs tens of bytes beyond the value.

Linked lists win as building blocks where you already hold a pointer to the node:

• LRU cache — a dict maps key → node in a doubly linked list ordered by recent use. On access: find the node in O(1) via the dict, unlink it, move it to the front — O(1). Evict from the tail — O(1). Python's OrderedDict and functools.lru_cache rely on this idea.
• Deques and queues — O(1) at both ends (CPython's deque is a doubly linked list of blocks).
• Memory allocators and OS schedulers — free lists and run queues, where nodes are spliced in and out constantly.
• Hash-table chaining — each bucket's collision chain.

Gotchas

• Losing the rest of the list — overwrite cur.next before saving it, and everything after cur is gone.
• Forgetting the head case — deleting the first node needs special handling, unless you use a dummy node.
• None checks — fast.next.next crashes if fast or fast.next is None; the loop guard is while fast and fast.next.
• Calling insert O(1) without the walk — inserting at position k is O(k) to get there.
• Indexing in a loop — calling a get(i) helper for i = 0…n−1 walks from the head every time: O(n²). Traverse once instead.
• Comparing values instead of nodes in cycle detection — use is; two different nodes can hold the same value.
• Deep recursion — recursive reversal of a 100,000-node list hits Python's recursion limit.

Words to know

In two minutes

• A linked list is a chain of nodes (value + next pointer) starting at the head and ending at None. Space O(n), with pointer overhead per node.
• Insert or delete at the head: O(1). Insert or delete after a node you already hold: O(1) — just rewire pointers.
• Access by position, search by value, and reaching the tail without a tail pointer: O(n) — you must walk.
• Deleting a node needs its predecessor; a dummy node before the head removes the head-is-special case.
• Reverse in place with three pointers (prev, cur, nxt): save next, flip the arrow, step forward. O(n) time, O(1) space.
• Fast/slow pointers: fast moves 2, slow moves 1. When fast hits the end, slow is at the middle; if they ever meet, there's a cycle. O(n) time, O(1) space.
• In practice arrays usually win on speed because of cache locality; linked lists shine as building blocks — LRU caches (hash map + doubly linked list), deques, queues.

Test yourself

There are 9 questions, 4 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.