Insert and Delete
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Changing a linked list means changing links, not moving values. Done in the right order, an insert or a delete touches only two or three nodes. This lesson shows the safe order and the dummy node trick.
Insert at the front
Adding a node at the front needs no walking. Make a node whose next is the old head. That node is now the head, so the function must return it.
def push_front(head, value): return Node(value, head)
head = Nonehead = push_front(head, 30)head = push_front(head, 20)Example 1 · Build a list by pushing at the front
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def push_front(head, value): return Node(value, head)
head = Nonefor value in [1, 2, 3]: head = push_front(head, value)print(to_list(head))[3, 2, 1]
What this code does
- Each push goes in front of the earlier ones, so the list comes out in reverse order.
- Every push is O(1), however long the list is. A Python
list.insert(0, x)would be O(n).
Always write head = push_front(head, ...). A function cannot rebind the caller's name, so it hands back the new head. The cost is O(1).
Insert at the end
To add at the end, walk to the last node and link the new node to it. An empty list is a special case: the new node is the head.
def append(head, value): new = Node(value) if head is None: return new node = head while node.next: node = node.next node.next = new return headExample 2 · Append, with and without a tail
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
head = tail = Node("A")for name in ["B", "C", "D"]: tail.next = Node(name) tail = tail.nextprint(to_list(head))['A', 'B', 'C', 'D']
What this code does
- Keeping
tailmeans each append is O(1): link the new node, then move the tail. - Without a tail, every append must first walk the whole list, which makes n appends cost O(n squared).
The loop stops on the last node because its next is None. Walking makes this O(n). Keeping a separate tail reference makes it O(1).
Insert after a node
Pointer rewiring means changing next references so the nodes join a different chain. Insert and delete are a few rewirings, and no values are moved or copied.
When you already hold a node, inserting after it costs O(1) with no walking. Link the new node to the old next first, then link the node to the new one.
def insert_after(node, value): node.next = Node(value, node.next)Example 3 · Insert after a chosen node
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def insert_after(node, value): node.next = Node(value, node.next)
head = build([10, 20, 40])insert_after(head.next, 30)insert_after(head.next.next.next, 50)print(to_list(head))[10, 20, 30, 40, 50]
What this code does
head.nextis the node holding 20, so 30 goes between 20 and 40.- The second call inserts after the last node, which works the same way: its old next was None.
Node(value, node.next) captures the old next before node.next is changed, so no node is lost. This O(1) insert in the middle is what a linked list does better than an array.
Delete a value
To delete a node, make the node before it skip over it. So you stop at the previous node and set prev.next = prev.next.next. Deleting the head is special, because nothing sits before it.
def delete(head, target): if head is None: return None if head.value == target: return head.next node = head while node.next and node.next.value != target: node = node.next if node.next: node.next = node.next.next return headExample 4 · Delete the first match: head, middle and missing
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def delete(head, target): if head is None: return None if head.value == target: return head.next node = head while node.next and node.next.value != target: node = node.next if node.next: node.next = node.next.next return head
print(to_list(delete(build([1, 2, 3]), 1)))print(to_list(delete(build([1, 2, 3]), 2)))print(to_list(delete(build([1, 2, 3]), 9)))[2, 3] [1, 3] [1, 2, 3]
What this code does
- Deleting the head returns the second node as the new head. A middle value is skipped by its previous node.
- A value that is not there changes nothing, and the loop ends on the last node.
The skipped node has no references left, so Python frees it by itself. There is no free call. This deletes the first match only, and costs O(n).
A dummy node removes the special cases
Dummy node is an extra node placed before the head of a list. It gives the first real node a previous node, so inserts and deletes at the front need no special case.
A dummy node is a throwaway node placed before the head. Then the head has a previous node like every other node, and one loop handles all cases.
def delete_all(head, target): dummy = Node(0, head) node = dummy while node.next: if node.next.value == target: node.next = node.next.next else: node = node.next return dummy.nextExample 5 · Delete every match with a dummy node
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def delete_all(head, target): dummy = Node(0, head) node = dummy while node.next: if node.next.value == target: node.next = node.next.next else: node = node.next return dummy.next
print(to_list(delete_all(build([3, 3, 1, 3, 2, 3]), 3)))print(to_list(delete_all(build([5, 5]), 5)))[1, 2] []
What this code does
- Runs of equal values, like the leading 3 3, are removed because
nodestays put after a delete. - When every node is removed,
dummy.nextis None and the result is the empty list.
Example 6 · Insert into a sorted list
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def insert_sorted(head, value): dummy = Node(0, head) node = dummy while node.next and node.next.value < value: node = node.next node.next = Node(value, node.next) return dummy.next
head = build([10, 20, 30])for value in [5, 25, 40]: head = insert_sorted(head, value)print(to_list(head))[5, 10, 20, 25, 30, 40]
What this code does
- The loop stops on the node just before where the value belongs. The dummy lets 5 go in front of the head.
- Finding the place costs O(n), but the insert itself is O(1).
Return dummy.next, because the head itself may have been deleted. Move node forward only when nothing was deleted, or you would skip a neighbour.
Next step
Check your understanding
12 quick questions