Insert and Delete

Linked Lists: lesson 3 of 6

Rewire two links, and nothing else has to move.

Lesson 3 of 6 · 5 min

Step 1 of 8

link writes0

node

1•

3•

∅

•

The list is 1 → 3. We want a 2 in between, and we already hold the node it goes after.

The Idea

Insertion and deletion are pure pointer surgery. Point the new node at whatever came next, then point the predecessor at the new node. Deleting is the mirror image: let the predecessor skip one link forward. No shifting, no resizing.

Real-World Example

Shunting a freight train works the same way. To drop a wagon from the middle you uncouple it and clip its two neighbours together. The other eighty wagons never budge, unlike a row of shelved crates where everything after the gap slides down.

The Code

class Node:
    def __init__(self, v): self.value, self.next = v, None

def insert_after(node, value):
    fresh = Node(value)
    fresh.next = node.next      # new node takes over the old link
    node.next = fresh           # predecessor now points at it

def delete_after(node):
    node.next = node.next.next  # unlink: skip straight over one node

head = Node(1); head.next = Node(3)
insert_after(head, 2)           # 1 -> 2 -> 3
delete_after(head)              # 1 -> 3, the 2 is unlinked
print(head.next.value)          # 3

Your turn

Fill in the blank.

class Node:
  def __init__(self, v): self.value, self.next = v, None

a = Node(1); a.next = Node(2); a.next.next = Node(3)
victim = a.next
# unlink the middle node so the list reads 1 -> 3
a.next = ___
print(a.next.value)

Mini quiz

1 / 3

Insert and Delete