Linked Lists

An array stores its values side by side in one block of memory, so you can jump to any index instantly. A linked list does something different: each value lives in its own little box called a node, and every node holds a pointer to the next one. The boxes can be scattered anywhere — the pointers are what keep them in order.

That trade-off shapes everything. You give up instant indexing, but you gain cheap inserts and deletes: to splice a node in or out, you just re-point a couple of arrows.

The idea

A singly linked list is a chain of nodes. Each node knows two things: its value, and where the next node is. The very first node is the head — it is the only one you are handed, so every operation starts there. The last node's next is None, which marks the end.

To find anything, you start at the head and follow next pointers one at a time. There is no shortcut to the middle — reaching the 5th node means stepping through the first four. That is why search and access are O(n), not O(1) like an array.

Walk through it

The animation has two parts.

Traversal. A curr pointer starts at the head and follows next until it falls off the end at None. Each hop is just curr = curr.next. Visiting every node this way is O(n).

Reversal. This is the classic linked-list interview question: turn 1 -> 2 -> 3 -> 4 into 4 -> 3 -> 2 -> 1 in place (no new list). We keep three variables:

• prev — the node we already reversed (starts at None).
• curr — the node we are reversing now (starts at the head).
• nxt — a temporary save of curr.next, so we do not lose the rest of the list when we overwrite the pointer.

Each loop does four moves: save nxt, flip curr.next to point at prev, then slide prev and curr one step forward. Watch each arrow flip backward in the animation as its line lights up.

The code, line by line

def reverse(head):
    curr = head
    while curr:               # traverse: follow next
        curr = curr.next
    prev = None               # now reverse in place
    curr = head
    while curr:
        nxt = curr.next       # save next
        curr.next = prev      # flip the link
        prev = curr           # advance prev
        curr = nxt            # advance curr
    return prev

• Lines 2–4 are the traversal: follow next until curr is None.
• Line 8 saves the rest of the list in nxt before we clobber the pointer. Skip this and you lose everything after curr forever.
• Line 9 is the actual reversal: point curr backward at prev.
• Lines 10–11 advance both pointers one step. The order matters — update prev first, then curr.
• When the loop ends, curr is None and prev is the new head, so we return prev.

Complexity

The reversal touches each node exactly once, so it is O(n) time. It uses only three pointer variables no matter how long the list is, so the extra space is O(1) — it really is in place.

When to use / pitfalls

Practice