Visual walkthrough — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

Before we touch code, we agree on the pictures.

Step 1 — What a "node" and an "arrow" look like

WHAT. A node is a box split in two halves. The left half holds data (the value you care about). The right half holds next — which is not a value, it is an address: a note saying "the next box is over there." We draw that note as an arrow.

WHY draw it as an arrow? Because next never stores the next value — it stores where to find the next box. An arrow is exactly "go there." When next is ==null== / None (nothing to point at), we draw a small ground symbol ⏚ meaning "end of chain, stop."

PICTURE. One box, two halves, one arrow leaving the right half.

If the arrow-as-address idea feels shaky, refresh Pointers and References — that is the entire vocabulary of this page.

Step 2 — A whole list is just boxes joined by arrows

WHAT. Chain three nodes. One extra arrow, ==head==, comes from outside and points at the first box. head is the only door in.

WHY only head? Because a box only knows its own next. Nothing points backward, nothing points to the middle. If you drop head, every box becomes unreachable — the whole list is lost. So head is sacred.

PICTURE. head → [10|•]→[20|•]→[30|⏚]. Follow the arrows left to right; the last one grounds out at null/None.

Step 3 — Traversal: the only way to move is forward, one hop at a time

WHAT. Put a walking pointer cur on head. Print its data. Then do cur = cur.next — jump cur to wherever the arrow points. Repeat until cur lands on the ground (null/None).

WHY this loop and no shortcut? There is no base + i*size. A box hands you exactly one thing: the address of the next box. To reach box #3 you are physically forced through #0, #1, #2. Walking is the only primitive move.

$\underset{\text{where I stand}}{\underbrace{\text{cur}}}=\underset{\text{the arrow leaving my box}}{\underbrace{\text{cur.next}}}$

The left cur is reassigned to the address stored on the right. One line = one hop.

PICTURE. cur shown at three moments, sliding along the arrows, then falling off into null.

Step 4 — The Golden Rule, drawn: wire the NEW arrow before moving the OLD one

Every insert is the same dance. We prove the dance once, here, so Steps 5–7 are just "apply it."

WHAT. We have a spot to insert new. Two arrows must end up correct:

1. new must point at whatever used to come next.
2. The pointer leading into the spot (head or some prev.next) must point at new.

WHY the order matters — the whole lesson. The address of "whatever came next" is currently held by the incoming pointer. If you overwrite that incoming pointer first, you erase the only copy of that address — the rest of the chain floats away. So you must copy it into new.next first, then redirect.

PICTURE (two panels). Left = WRONG order: redirect first → chain snaps, tail is lost. Right = RIGHT order: new.next set first (dashed arrow), then the incoming arrow swings onto new — nothing is lost.

Step 5 — Insert at HEAD, arrow by arrow ($O(1)$)

WHAT. Put new in front of everything.

$\text{new.next}=\underset{\text{old first box}}{\underbrace{\text{head}}}\text{then}\underset{\text{front door}}{\underbrace{\text{head}}}=\text{new}$

• Line 1: new's arrow grabs the old first box (so we keep the chain).
• Line 2: the front door now opens onto new.

WHY $O(1)$? We never walked. Two arrow writes, done — no matter how long the list is.

PICTURE. Frame A: new floating, head → [10]. Frame B: dashed new.next → [10]. Frame C: head swung onto new.

Reverse the two lines and head = new runs first — [10]… is orphaned before new can grab it. That is Step 4's WRONG panel in the flesh.

Step 6 — Insert at TAIL, and the empty-list edge case ($O(n)$)

WHAT. Attach new after the last box — the one whose next is null/None.

WHY walk with cur.next? For the tail we want to stand on the last node, not fall off it. So we stop while cur.next is null-bound: while cur.next is not None: cur = cur.next. When the loop ends, cur is the last box. Then we apply the Golden Rule.

Apply the Golden Rule here too. Even at the tail we wire new first: new.next = None (the arrow must ground out, so new becomes the new last box), then cur.next = new. In practice new.next is already None from the constructor (Step 1's invariant) — but conceptually the "wire first" step still happens, it's just done for free by the constructor. Equivalently you may write new.next = cur.next (which is None anyway). Never skip the idea: the new node's forward arrow is settled before we redirect cur.

Degenerate case — empty list. If head is None there is no last box to stand on. cur = head is None, and cur.next explodes. Fix: handle it first — head = new and stop.

def insert_tail(self, data):
    new = Node(data)            # invariant: new.next is already None (Step 1)
    new.next = None             # Golden Rule, wire first: new grounds out as the last box
    if self.head is None:       # empty-list edge case
        self.head = new         # Why? no box to stand on; new becomes head
        return
    cur = self.head
    while cur.next is not None: # Why .next? we WANT the last box, not None
        cur = cur.next
    cur.next = new              # then redirect: last box now points at new

PICTURE (two panels). Top: empty list, head grounded → head swings straight to new (which already grounds out). Bottom: 3-node list, cur walks to the last box, new grounds out at null, then a new arrow drops from cur to new.

Step 7 — Insert in the MIDDLE, after node p ($O(k)$ to find p)

WHAT. Splice new between p and whatever followed p.

• Line 1: new copies p's current forward address (so the tail survives).
• Line 2: p now points at new.

Same Golden Rule as Step 4 — copy first, redirect second. Finding p costs $O(k)$ hops (Step 3's walk); the splice itself is $O(1)$ (two writes).

PICTURE. p → [30] becomes p → new → [30], with the dashed "wire first" arrow drawn before the solid "redirect" arrow.

Reverse the lines: p.next = new first overwrites p's only copy of [30]'s address → [30]… lost. The rule never bends.

Step 8 — Deletion: skip the box, carry prev, and guard the edges

WHAT. To delete box X, make the box before it jump over it: prev.next = X.next. Once nothing points at X, it is unreachable and gets freed.

WHY carry prev? A singly list has no backward arrow. Standing on X you cannot reach the box that points into X. So as you walk you drag a trailing pointer prev one step behind cur.

How prev is maintained — the concrete loop. Start cur at the second node and prev at the head. Each iteration checks cur; if it's not the target, both advance together — prev = cur then cur = cur.next — so prev is forever exactly one box behind cur.

def delete(self, value):
    cur = self.head
    if cur is None:              # EDGE 1: empty list — nothing to delete
        return                   # Why? no box, no head.next to touch
    if cur.data == value:        # EDGE 2: the head itself is the target
        self.head = cur.next     # move the door; no prev needed
        return
    prev = self.head             # prev starts one behind...
    cur  = self.head.next        # ...cur starts on the second box
    while cur is not None:       # walk until we fall off (value not found)
        if cur.data == value:
            prev.next = cur.next # unlink: prev skips cur
            return
        prev = cur               # keep prev one box behind...
        cur  = cur.next          # ...as cur hops forward
    # EDGE 3: fell off the end -> value was never in the list; do nothing

Head case (edge). If the very first box is the target, there is no prev — instead move the door: head = head.next.

Empty-list & not-found edges. If head is None we return immediately (no box to look at, and touching head.next would crash). If the loop reaches null without a match, the value simply wasn't there — we do nothing, safely.

PICTURE (two panels). Top: deleting the head — the door slides to the second box. Bottom: deleting a middle box — prev's arrow swings past cur onto cur.next; the orphaned box greys out.

The one-picture summary

Every operation on this page is one truth: change one or two arrows, and always wire the new arrow before you move the old one. This final figure stacks head-insert, middle-insert, and delete side by side so you can see they are the same move wearing different clothes.