Linked Lists vs Arrays

queue = ["song-a", "song-b", "song-c"]
queue.insert(0, "song-new")
```text

This works. It also moves every other song one position to the right. For a 10,000-song library, that is 10,000 element copies on every "play next" tap. The list's strength — O(1) random access via `queue[5000]` — is a strength the music player never uses.

The linked list solves this by giving up random access entirely. You cannot ask "what is the 5000th element?" and get an instant answer. But you can insert at the front in O(1) — one pointer change, no element copies, no matter the list size.

**Example 1 — three nodes, linked by hand.**

Create three stand-alone nodes and wire them into a chain:

```text
node1 = Node(10)        node1.data = 10,  node1.next = None
node2 = Node(20)        node2.data = 20,  node2.next = None
node3 = Node(30)        node3.data = 30,  node3.next = None
```text

After wiring `node1.next = node2` and `node2.next = node3`:

```text
node1 → [data:10 | next: → node2] → node2 → [data:20 | next: → node3] → node3 → [data:30 | next: None]
```text

Each node holds a value and a reference. `node1.next.next.data` is `30` — you reached the third element without an index, by following pointers.

**Example 2 — traversal, step by step.**

Start at `head` (which is `node1`) and walk until `None`:

| Step | current | current.data | current.next |
|------|---------|-------------|-------------|
| 1 | node1 | 10 | node2 |
| 2 | node2 | 20 | node3 |
| 3 | node3 | 30 | None |

Walking three nodes requires three steps. For n nodes, it requires n steps. **Time:** O(n). This is the cost of losing random access — every "find" is a walk from the head.

**Example 3 — insert at head, array vs linked list.**

Insert value `99` at the front of a 5-element structure:

Array approach:
```text
Before:  [10, 20, 30, 40, 50,  _ ]

Step 1:  shift arr[4] → arr[5]
Step 2:  shift arr[3] → arr[4]
Step 3:  shift arr[2] → arr[3]
Step 4:  shift arr[1] → arr[2]
Step 5:  shift arr[0] → arr[1]
Step 6:  arr[0] = 99
```text
5 elements moved. 5 copies. O(n).

Linked list approach:
```text
Before:  head → [10 | →] [20 | →] [30 | →] [40 | →] [50 | None]
Step 1:  new_node = Node(99)
Step 2:  new_node.next = head
Step 3:  head = new_node
After:   head → [99 | →] [10 | →] [20 | →] [30 | →] [40 | →] [50 | None]
```text
Zero elements moved. Two pointer writes. O(1).

<svg role="img" aria-label="Insert 99 at head of 10→20→30→40→50: new_node created, new_node.next=head, head=new_node. Result: 99→10→20→30→40→50" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 750 100" xmlns="http://www.w3.org/2000/svg" width="100%">
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="75" y="45">99</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="75" y="62">new_node</text>
  <path d="M 120 40 L 145 40" marker-end="url(#insarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">10</text>
  <path d="M 250 40 L 280 40" marker-end="url(#insarrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">20</text>
  <path d="M 385 40 L 415 40" marker-end="url(#insarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1.5" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="475" y="45">30</text>
  <path d="M 520 40 L 550 40" marker-end="url(#insarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="560" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="600" y="45">40</text>
  <path d="M 645 40 L 675 40" marker-end="url(#insarrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="685" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="720" y="45">50</text>
  <path d="M 75 70 L 75 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="75,90 70,80 80,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="75" y="98">head</text>
  <defs><marker id="insarrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

The difference grows with the list. For 10,000 elements, the array copies 10,000 values; the linked list writes two pointers.

## What a Linked List Is

A linked list is a chain of nodes. Each node holds two fields: the data, and a reference to the next node. The list itself is just a reference to the first node, called the `head`.

To find the third song, start at `head`, follow `.next` to the second node, follow `.next` to the third. O(n) walks instead of O(1) indexing.

<svg role="img" aria-label="Linked list with head pointing to song-new, which points to song-a, which points to song-b, which points to song-c, which points to None" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 650 100" xmlns="http://www.w3.org/2000/svg" width="100%">
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" font-weight="600" text-anchor="start" x="10" y="45">head</text>
  <path d="M 50 40 L 85 40" marker-end="url(#marrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="95" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="135" y="45">'song-new'</text>
  <path d="M 175 40 L 205 40" marker-end="url(#marrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="215" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="255" y="45">'song-a'</text>
  <path d="M 295 40 L 325 40" marker-end="url(#marrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="335" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="375" y="45">'song-b'</text>
  <path d="M 415 40 L 445 40" marker-end="url(#marrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="455" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="14" font-weight="600" text-anchor="middle" x="495" y="45">'song-c'</text>
  <path d="M 535 40 L 565 40" marker-end="url(#marrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="575" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="615" y="45">None</text>
  <defs><marker id="marrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

`class Node:` — defines a plain data container. No methods beyond the constructor. Everything about a linked list — traversal, insertion, deletion — lives in functions outside this class.

`def __init__(self, data):` — called when `Node(10)` is written. Takes the value to store.

`self.data = data` — stores the value in the node's first field.

`self.next = None` — initialises the pointer to `None`. Until another node is wired in, this node points nowhere. That is correct for the last node in any chain.

`data` holds whatever you want to store — an integer, a string, an object. `next` holds a reference to another `Node`, or `None` if this is the last node.

**Time:** O(1) — creating a single node allocates memory and sets two fields. **Space:** O(1) for the node itself, plus the data it holds.

### Traversal

Walk from the head, following `.next`, until `None`:

```textpython
def traverse(self):
    current = self.head
    while current:
        print(current.data, end=" -> " if current.next else "\n")
        current = current.next
```text

`current = self.head` — starts at the first node. If `self.head` is `None`, the loop body never runs and nothing prints.

`while current:` — the only gate to continue. As long as `current` is a `Node` object, the loop runs. The moment `current` becomes `None`, the loop stops. There is no stored length, no index — only the pointer chain.

`print(current.data, end=" -> " if current.next else "\n")` — prints the data of the current node. Uses a conditional to append an arrow for the next node or a newline for the last node.

`current = current.next` — advances to the next node. On the last node, `current.next` is `None`, so `current` becomes `None` and the next loop condition check fails.

**Empty list:** `self.head` is `None`, `current` is `None`, loop never runs. Correct.

**Single node:** loop runs once, prints the data, `current` becomes `None`, loop stops. Correct.

**Cycle:** if the last node's `next` points back into the list, `current` never becomes `None` — infinite loop. The next post covers detecting and fixing cycles.

**Time:** O(n) — visits every node once. **Space:** O(1) — a single `current` pointer regardless of list size.

Let us trace `traverse()` on the list `10 → 20 → 30 → None`. The pointer chain is built first:

| Step | Action | head | head.next | head.next.next |
|------|--------|------|-----------|----------------|
| 1 | `node1 = Node(10)` | [10\|→] | None | — |
| 2 | `node2 = Node(20)` | — | — | — |
| 3 | `node1.next = node2` | [10\|→node2] | [20\|→] | None |
| 4 | `node3 = Node(30)` | — | — | — |
| 5 | `node2.next = node3` | [10\|→node2] | [20\|→node3] | [30\|→None] |

After wiring: `node1 → [10|→node2] → [20|→node3] → [30|→None]`.

Now trace `traverse()`:

| Iteration | current (before) | current.data | current.next | current (after) |
|---|---|---|---|---|
| 1 | node1 | 10 | node2 | node2 |
| 2 | node2 | 20 | node3 | node3 |
| 3 | node3 | 30 | None | None |
| 4 (exit) | None | — | — | — |

Loop exits. `current` is `None`. `while current` is false.

Let us visualise each step:

<svg role="img" aria-label="Step 1 of traverse on 10→20→30: current points to node1 containing data=10, next pointer leads to node2" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="80" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="80" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="215" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="215" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="350" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="350" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="475" y="45">None</text>
  <path d="M 40 70 L 40 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="40,90 35,80 45,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="40" y="98">current</text>
  <defs><marker id="arrow" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="Step 2 of traverse on 10→20→30: current advances to node2 containing data=20, next pointer leads to node3" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="80" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="80" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="215" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="215" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="350" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="350" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="475" y="45">None</text>
  <path d="M 175 70 L 175 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="175,90 170,80 180,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="175" y="98">current</text>
  <defs><marker id="arrow2" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="Step 3 of traverse on 10→20→30: current advances to node3 containing data=30, next pointer leads to None" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="80" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="80" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="215" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="215" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="350" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="350" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow3)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="475" y="45">None</text>
  <path d="M 310 70 L 310 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="310,90 305,80 315,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="310" y="98">current</text>
  <defs><marker id="arrow3" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="Step 4 of traverse on 10→20→30: current becomes None, loop exits. All nodes printed." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="80" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="80" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="215" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="215" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="350" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="350" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow4)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="475" y="45">None</text>
  <path d="M 450 70 L 450 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="450,90 445,80 455,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="450" y="98">current</text>
  <defs><marker id="arrow4" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

## The LinkedList Class

A wrapper around the head pointer. Every operation in this section will be a method on this class.

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

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> " if current.next else "\n")
            current = current.next
```text

`class LinkedList:` — the wrapper. Holds a single pointer to the first node.

`def __init__(self):` — called when `LinkedList()` is written.

`self.head = None` — an empty list has no nodes, so `head` starts as `None`. This is the only invariant the class maintains.

`def traverse(self):` — walks the entire chain and prints every node's data. Defined earlier with full line-by-line explanation.

The head is the single point of truth for the entire list. If you lose it — say, by overwriting the variable — every node becomes unreachable and the list is garbage.

**Time:** O(1) to create an empty list. **Space:** O(1) — only the `head` pointer is stored.

## When Linked Lists Pay Rent

- **Queue-like behavior** — frequent head insertions and removals.
- **LRU caches** — reorder nodes in O(1) on access by moving a node to the front.
- **Hash map chaining** — one linked list per bucket for collision resolution.
- **Adjacency lists for graphs** — each vertex stores neighbors in a linked list.

Most of the time, the right answer is still a Python list. Linked lists win where insertion matters more than access. The music player queue from the opening — that is a linked list problem dressed as an array problem.

The pointer discipline that makes linked lists work — never losing the head, wiring `.next` before cutting the old link — is the same discipline behind every pointer-based data structure. Trees, graphs, and hash table collision chains all depend on it. The next post builds the input and length functions that every operation in this section relies on.