Linked List

Intuition

A linked list is a chain of small boxes, each holding one value and an arrow pointing to the next box. The list itself is just a pointer called head aimed at the first box. To find anything, you start at head and follow arrows until you arrive — or run off the end.

This is the opposite of an array. An array stores everything in one contiguous block: random access is O(1), but inserting in the middle has to shift everything that comes after. A linked list pays for the chain: random access is O(n), but inserting anywhere costs only an arrow rewiring once you're standing at the right spot. The right pick depends entirely on what you do more often: read by index, or splice in the middle.

How It Works

The displayed code defines two classes:

• Node — holds a value and a next pointer.
• LinkedList — holds the head pointer (the entry point), a size counter, and a max capacity for the visualization.

The five operations the visualization walks:

• insert_head(v) — allocate a new node whose next is the old head, then point head at the new node. O(1).
• insert_tail(v) — if head is None, the new node is the head. Otherwise walk curr.next to the last node, then attach. O(n).
• insert_at(k, v) — splice at index k. Walk k − 1 steps to the predecessor, then pred.next = Node(v, pred.next). O(k).
• delete(v) — find the first node holding v, then unlink it: pred.next = node.next. Special-case head if the match is at position 0. O(n).
• search(v) — walk from head, return the index of the first match (or −1). O(n).

The single concept every operation reduces to: splice an arrow. Insertion writes one or two .next pointers. Deletion writes one. The visualization deliberately shows these writes as separate beats (makeRoom, setNewNext, setPrev) so the order — new node's next first, then predecessor's next — is unambiguous.

Step By Step

Starting with an empty list:

1. insert_head(5) → head is None, so the new node 5 becomes the head. List: 5 → ∅.
2. insert_head(8) → new node 8's next points at 5, then head = 8. List: 8 → 5 → ∅. Two writes, two beats.
3. insert_tail(3) → walk head → 8, then 8.next → 5, confirm 5.next is None → attach. List: 8 → 5 → 3 → ∅.
4. insert_at(1, 7) → walk k − 1 = 0 steps (stay at head = 8). New node 7's next points at 8.next = 5. Then 8.next = 7. List: 8 → 7 → 5 → 3 → ∅.
5. search(5) → walk from head counting indices: 8 (0), 7 (1), 5 (2). Return 2.
6. delete(5) → walk, find predecessor 7. Rewire 7.next = 3. List: 8 → 7 → 3 → ∅.

In the visualization, each node is a labeled box; the next pointer is a dashed arrow. A traversal cursor (curr) descends along the chain. When a splice fires, the new arrow draws in, the old arrow fades out, and the size header updates atomically.

Complexity

*Tail insertion is O(1) if the list also keeps a tail pointer. The displayed implementation does not — it walks from head every time. That's a deliberate simplification.

Space: O(n) for the nodes, plus one pointer per node — roughly 2× the memory of an equivalent array.

Edge Cases

• Empty list, then insert_head / insert_tail — the new node becomes the head. Both operations collapse to the same write.
• Empty list, delete / search — both return immediately with "not found" (False / −1).
• Single-node list — delete of the head's value sets head = head.next = None. Size drops to 0.
• Delete a value not in the list — curr.next walks off the end and curr.next becomes None. Guard returns False.
• insert_at(k, v) with k = 0 — the displayed code delegates to insert_head explicitly.
• insert_at(k, v) with k > size — the displayed code walks k − 1 steps even if that runs off the end. Real code should bounds-check first.

Common Mistakes

• Rewiring in the wrong order. When inserting between pred and succ, you must set newNode.next = succ before pred.next = newNode. The reverse order writes pred.next = newNode first, then asks "what was the old pred.next?" — but that value is now lost. You'd have to stash it in a temp variable, which is what most languages without tuple assignment effectively do.
• Losing the head. Writing head = head.next to delete the head is correct only if the old head isn't referenced elsewhere. In GC'd languages this is fine; in C / C++ you'd leak the node.
• Walking off the end without checking. while curr.next: stops one node early — leaving curr at the last node, which is what insert-at-tail wants. while curr: walks one too far and crashes on None.next. Pick the one that matches your intent.
• Confusing singly and doubly linked lists. A doubly linked list has a prev pointer in addition to next. That doubles the bookkeeping on every splice (four writes instead of two) but lets you delete a known node in O(1) without walking to find its predecessor. The displayed code is singly linked.
• Using a linked list when you really want an array. Modern CPUs are extremely fast on contiguous memory; pointer-chasing through scattered allocations is a cache disaster. Reach for a linked list when you genuinely need O(1) middle-splices and rarely access by index. Otherwise an array (or ArrayList / vector / Python list) almost always wins on real hardware.