---
title: "Linked Lists"
description: "Singly list — node, head, next pointer"
source: https://vizlearn.app/algorithms/data-structures/linked-lists
---

# Linked Lists

A linked list is a data structure that stores values in separate nodes, each holding one value and a `next` pointer to the following node. Insertion at the head costs O(1) — one pointer write — but reaching any position means walking the chain from `head`, so access, search, and arbitrary insertion all cost O(n) time.

Think of it as a scavenger hunt. Each clue holds one prize and tells you where the next clue is hidden. You can't jump to clue five; you follow one through four first. But slipping a new clue into the middle is trivial — rewrite two clues and nobody downstream ever knows.

## How a Linked List Works

The displayed code is a singly linked list: a `Node` holding `value` and `next`, and a `LinkedList` holding one entry point, `head`. There is no `tail` pointer — `insert_tail` walks the whole chain every time, and the complexity table charges for it.

Every mutation is a clue splice. `insert_head(v)` points the new node's `next` at the old head, then swings `head` onto the new node — two writes, zero walking. `insert_at(k, v)` walks to position `k − 1`, then performs the same two writes: `newNode.next = curr.next`, then `curr.next = newNode`. The order matters (see Common Mistakes), so the animation plays the writes as separate beats.

`delete(v)` checks the head first — an O(1) special case, since the head has no predecessor to rewire. Otherwise `curr` walks while *looking ahead*: it probes `curr.next.value`, never its own, so when the target turns up, `curr` already stands on the predecessor — exactly where `curr.next = curr.next.next` needs it. `search(v)` is the plain walk: compare, step, return the index or `-1`.

One honest disclosure: the capacity slider (4–10 nodes, default 7) exists only because the canvas fits so many boxes. The code mirrors it with a `max` field, but a real linked list has no capacity — unbounded growth is half the point.

## Linked List Operations Step by Step

The list starts empty. Run this sequence from the Inputs panel:

1. **Insert Head 5** — the new node stages above the row, its `next` aims at the sentinel `∅` (the old head was nothing), then `head` swings onto it. List: `5 → ∅`.
2. **Insert Head 8** — node 8 stages, `8.next` aims at the current head 5, then `head` redirects to 8. List: `8 → 5 → ∅`.
3. **Insert Tail 3** — `curr` walks: index 0 (value 8), index 1 (value 5, whose `next` is `∅`, so the walk stops). Then `3.next = ∅` and `5.next` swings to 3. List: `8 → 5 → 3 → ∅`.
4. **Insert At Index 1, value 7** — `curr` walks to the predecessor at index 0. Then `7.next = 8.next` (which is 5), then `8.next = 7`. List: `8 → 7 → 5 → 3 → ∅`.
5. **Search 5** — probe index 0: `8 ≠ 5`; index 1: `7 ≠ 5`; index 2: `5 = 5`. Found at index 2.
6. **Delete 5** — head check: `8 ≠ 5`. Look-ahead walk: `curr` at index 0 probes `7 ≠ 5`; at index 1 probes `5 = 5`. Node 5 lifts out, `7.next` bypasses it to 3, the chain closes. List: `8 → 7 → 3 → ∅`.

On the canvas, the `curr` cursor marks each probe, a staged node hovers above its slot until both pointer writes land, and a deleted node lifts out while the bypass arrow swings past it — the two-writes-then-commit rhythm above, drawn one beat at a time.

## Time and Space Complexity

| Operation | Cost | Why |
|---|---|---|
| Access by index | O(n) | follow clues from `head` |
| Insert at head | O(1) | two pointer writes, no walk |
| Insert at tail | O(n) | no `tail` pointer here — walks the chain |
| Insert at index k | O(k) | walk to the predecessor, then O(1) splice |
| Delete by value | O(n) | look-ahead walk to the predecessor |
| Search | O(n) | compare node by node |
| Space | O(n) | one node plus one pointer per value |

A `tail` pointer would make tail insertion O(1); the code skips it to keep the walk visible. The time complexity of the splice itself is always O(1) — you only pay for getting there.

## Edge Cases

- **Insert into an empty list** — head and tail insertion collapse into the same move: `head` swings from `∅` onto the lone new node.
- **Delete or search on an empty list** — both return gracefully (`False` / `-1`) via the `if not self.head` guard. No exception.
- **Delete the head** — caught by the O(1) head check; `head = head.next`, no walk.
- **Delete a missing value** — `curr.next` hits `∅` and the guard returns `False`.
- **`insert_at(k, v)` with `k` past the end** — the code has no bounds check and would walk off the chain into a crash; the visualization stops and says so instead. (`k = 0` simply delegates to `insert_head`.)

## Common Mistakes

- **Splicing in the wrong order.** Write `newNode.next = curr.next` *before* `curr.next = newNode`. Reversed, you overwrite the only clue pointing at the rest of the hunt — the back half of the list is gone.
- **Hunting the node instead of its predecessor.** The rewire needs the node *before* the target — which is why the delete walk probes `curr.next`, not `curr`.
- **Off-by-one in the walk condition.** `while curr.next` stops on the last node (what tail insertion wants); `while curr` inspects the last node too (what search wants). Swap them and you skip the final node or dereference `∅`.
- **Using a linked list when an array would do.** Pointer-chasing through scattered memory is brutal on caches. Pick the list when you splice in the middle often and rarely access by index; otherwise the boring contiguous array wins.