Learning Goals
3 minBy the end of this lesson you can:
- Insert a new node at the head, the tail, or after a given node.
- Delete a node by value or by index without breaking the chain.
- Use a "sentinel" or "dummy head" node to simplify head-deletion edge cases.
- Reverse a linked list in place.
Warm-Up · Inserting Between Two Nodes
5 minBefore: A → B → C Insert X between A and B: 1. Make new node X with X.next = B 2. Set A.next = X 3. Done. After: A → X → B → C Two pointer assignments. No shifting.
This is the core idea. In a Python list, inserting in the middle shifts everything right — O(n). In a linked list, two pointer changes — O(1) if you have the "A" node.
Insertion and deletion in a linked list are pointer juggling. Draw boxes and arrows on paper before you write code. Always.
New Concept · Insert & Delete
14 minInsert at head — already done in Part 1
def push_front(self, value): self.head = Node(value, next=self.head) # O(1). New node points to old head; head becomes the new node.
Insert at tail
def push_back(self, value): new = Node(value) if self.head is None: self.head = new return cur = self.head while cur.next is not None: # walk to the last node cur = cur.next cur.next = new # O(n) — must traverse to find the tail. (Doubly-linked or "keep a tail pointer" # would make this O(1); we'll just take the cost for now.)
Insert at index
def insert_at(self, index, value): if index < 0: raise IndexError("Negative not supported") if index == 0: self.push_front(value) return prev = self._node_at(index - 1) # node before insertion point if prev is None: raise IndexError("Index out of range") prev.next = Node(value, next=prev.next) def _node_at(self, index): cur = self.head i = 0 while cur is not None and i < index: cur = cur.next i += 1 return cur # may be None
Find prev, the node before the insertion point. Make new node pointing at prev.next. Set prev.next to the new node. Two pointer changes.
Delete by value
def remove(self, value): """Remove the first node with this value. Return True on success.""" # Handle empty list if self.head is None: return False # Special case: head is the target if self.head.value == value: self.head = self.head.next return True # Otherwise walk and find prev prev = self.head cur = self.head.next while cur is not None: if cur.value == value: prev.next = cur.next # skip cur return True prev = cur cur = cur.next return False
Two cases: removing the head (just move head forward), removing anything else (stitch prev.next past cur). The dropped cur becomes garbage and Python frees it automatically.
The sentinel-node trick · removing the special case
The head-removal special case is annoying. Add a dummy node at the start — a sentinel. Now there's always a prev before every real node, and the logic uniformises:
def remove_with_sentinel(self, value): dummy = Node(None, next=self.head) prev = dummy while prev.next is not None: if prev.next.value == value: prev.next = prev.next.next # skip self.head = dummy.next # head might have changed return True prev = prev.next return False
One less branch. The sentinel pattern is standard in production linked-list libraries.
Reverse the list in place
The classic interview question. Walk through, flipping each node's next to point at its predecessor.
def reverse(self): prev = None cur = self.head while cur is not None: next_node = cur.next # save where we're going cur.next = prev # flip prev = cur # advance prev cur = next_node # advance cur self.head = prev # the old tail is the new head
Three pointers: prev, cur, next_node. Save the next link before clobbering it. Walk all the way; prev ends up at the (formerly last) node, which is the new head.
Worked Example · The Full LinkedList v2
12 minThe complete class. Save as linked_list_v2.py:
# linked_list_v2.py — singly-linked list with insert + delete class Node: def __init__(self, value, next=None): self.value = value self.next = next class LinkedList: def __init__(self, iterable=None): self.head = None if iterable is not None: for v in reversed(list(iterable)): self.push_front(v) # --- inserts --- def push_front(self, value): self.head = Node(value, next=self.head) def push_back(self, value): new = Node(value) if self.head is None: self.head = new return cur = self.head while cur.next is not None: cur = cur.next cur.next = new def insert_at(self, index, value): if index == 0: self.push_front(value) return prev = self._node_at(index - 1) if prev is None: raise IndexError("out of range") prev.next = Node(value, next=prev.next) # --- removes --- def remove(self, value): if self.head is None: return False if self.head.value == value: self.head = self.head.next return True prev = self.head cur = self.head.next while cur is not None: if cur.value == value: prev.next = cur.next return True prev = cur cur = cur.next return False def pop_front(self): if self.head is None: raise IndexError("empty list") val = self.head.value self.head = self.head.next return val # --- in-place reverse --- def reverse(self): prev = None cur = self.head while cur is not None: next_node = cur.next cur.next = prev prev = cur cur = next_node self.head = prev # --- helpers --- def _node_at(self, index): cur = self.head i = 0 while cur is not None and i < index: cur = cur.next i += 1 return cur def __iter__(self): cur = self.head while cur is not None: yield cur.value cur = cur.next def __len__(self): return sum(1 for _ in self) def __repr__(self): return "[" + " → ".join(str(v) for v in self) + "]" # Test ll = LinkedList([10, 20, 30, 40, 50]) print(ll) # [10 → 20 → 30 → 40 → 50] ll.push_front(0) print(ll) # [0 → 10 → 20 → 30 → 40 → 50] ll.push_back(60) print(ll) # [0 → 10 → 20 → 30 → 40 → 50 → 60] ll.insert_at(3, 25) print(ll) # [0 → 10 → 20 → 25 → 30 → 40 → 50 → 60] ll.remove(20) print(ll) # [0 → 10 → 25 → 30 → 40 → 50 → 60] ll.pop_front() print(ll) # [10 → 25 → 30 → 40 → 50 → 60] ll.reverse() print(ll) # [60 → 50 → 40 → 30 → 25 → 10]
Read the diff
Every operation is two-pointer juggling at most. push_front and pop_front are O(1). insert_at, remove, push_back are O(n) because they walk to find the right node. reverse is O(n) — single pass. The class works as a real iterable thanks to __iter__.
Try It Yourself
13 minAdd remove_all(value) that removes every node matching the value. Returns the count of removed nodes.
Hint
def remove_all(self, value): count = 0 # Strip from head while it matches while self.head is not None and self.head.value == value: self.head = self.head.next count += 1 if self.head is None: return count prev = self.head cur = self.head.next while cur is not None: if cur.value == value: prev.next = cur.next count += 1 cur = cur.next # don't advance prev else: prev = cur cur = cur.next return count
Two phases: skip matching heads first, then walk and skip the rest. Don't advance prev when you delete — same prev compares against the next survivor.
Return the value of the middle node — without using len. Use the slow/fast pointer trick from Floyd's.
Hint
def middle(self): slow = self.head fast = self.head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next return slow.value if slow is not None else None ll = LinkedList([1, 2, 3, 4, 5]) print(ll.middle()) # 3 ll = LinkedList([1, 2, 3, 4]) print(ll.middle()) # 3 (the second of two middles)
Fast moves twice as fast as slow. When fast reaches the end, slow is at the middle. One pass, no length precomputed. Famously elegant.
Given two sorted linked lists, merge them into one sorted list. Modify the pointers; don't make new nodes.
Hint
def merge_sorted(a_head, b_head): dummy = Node(None) tail = dummy a, b = a_head, b_head while a is not None and b is not None: if a.value <= b.value: tail.next = a a = a.next else: tail.next = b b = b.next tail = tail.next tail.next = a if a is not None else b # whichever still has nodes return dummy.next a = LinkedList([1, 3, 5, 7]) b = LinkedList([2, 4, 6, 8, 10]) merged = LinkedList() merged.head = merge_sorted(a.head, b.head) print(merged) # [1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 10]
The dummy head simplifies things — no special case for "first node to add". Walk both lists, pick the smaller head each time, attach. Classic mergesort building block.
Mini-Challenge · Remove Duplicates
8 minAdd dedupe() to your LinkedList. Remove all duplicate values, keeping the first occurrence. The list should keep its existing order.
ll = LinkedList([1, 2, 1, 3, 2, 4, 1, 5]) ll.dedupe() print(ll) # [1 → 2 → 3 → 4 → 5]
Show one possible solution
def dedupe(self): seen = set() prev = None cur = self.head while cur is not None: if cur.value in seen: prev.next = cur.next # skip this node else: seen.add(cur.value) prev = cur cur = cur.next
Non-negotiables: a set of seen values, walk with prev tracking. When current is a duplicate, splice it out. prev only advances when we keep the current.
Recap
3 minInsert and delete in linked lists are pointer-juggling exercises. Insert: make new node pointing at successor, change previous node's next to point at new node. Delete: set previous node's next to skip the doomed node. The head is the special case — either handle it explicitly or use a dummy sentinel. Reverse-in-place uses three pointers (prev/cur/next). Linked lists shine when you have many middle insertions/deletions and few index accesses — otherwise, use Python's list.
Vocabulary Card
- insert at position
- Stitch a new node in by changing two pointers.
- splice out
- Remove a node by making the previous node skip past it.
- sentinel / dummy node
- A fake head node that simplifies the "deleting at head" special case.
- slow/fast pointer
- Walk one pointer at half speed of another. Finds the middle, detects cycles, splits the list.
Homework
4 minBuild a DoublyLinkedList. Each node has value, next, prev. Implement push_front, push_back, pop_front, pop_back, all O(1). Add a __reversed__ dunder that iterates backwards — a doubly-linked list does this for free.
Sample · DoublyLinkedList
class DNode: def __init__(self, value, prev=None, next=None): self.value = value self.prev = prev self.next = next class DoublyLinkedList: def __init__(self): self.head = None self.tail = None def push_front(self, value): new = DNode(value, next=self.head) if self.head is not None: self.head.prev = new self.head = new if self.tail is None: self.tail = new def push_back(self, value): new = DNode(value, prev=self.tail) if self.tail is not None: self.tail.next = new self.tail = new if self.head is None: self.head = new def pop_front(self): if self.head is None: raise IndexError("empty") val = self.head.value self.head = self.head.next if self.head is not None: self.head.prev = None else: self.tail = None return val def pop_back(self): if self.tail is None: raise IndexError("empty") val = self.tail.value self.tail = self.tail.prev if self.tail is not None: self.tail.next = None else: self.head = None return val def __iter__(self): cur = self.head while cur is not None: yield cur.value cur = cur.next def __reversed__(self): cur = self.tail while cur is not None: yield cur.value cur = cur.prev def __repr__(self): return "[" + " ↔ ".join(str(v) for v in self) + "]" dll = DoublyLinkedList() for v in [10, 20, 30, 40]: dll.push_back(v) print(dll) # [10 ↔ 20 ↔ 30 ↔ 40] print(list(reversed(dll))) # [40, 30, 20, 10] print(dll.pop_back(), dll.pop_front()) # 40 10 print(dll) # [20 ↔ 30]
Non-negotiables: prev/next on every node, head and tail tracked. All four ends-operations O(1). Doubly-linked is what Python's collections.deque uses internally for its O(1) both-ends performance.