PYTHON / DATA STRUCTURES AND ALGORITHMS
Linked lists
Build singly linked lists from node objects, splice and unlink nodes correctly, and explain why traversal is O(n) while insertion at a held node is O(1).
What you will learn
- Build a chain by prepending: head = Node(v, head) is O(1) and copies nothing
- Save node.next before overwriting it so you never lose the rest of the chain
- Reverse a list in place with three names: prev, current, and the saved next
- Explain why a cached tail makes append O(1) but popping the tail still O(n)
Understanding Linked lists
A linked list has no single block of memory holding the elements. Each element is its own object carrying a value and a reference to the next node, and the order of the sequence lives entirely in those references. The name head is just a local variable bound to the first node; every other element is reachable only by following .next repeatedly, and the chain ends where some node's .next is None. Nothing in the structure knows its own length or position unless you store that separately.
The cost model follows directly from that shape: work is cheap where you already stand and expensive to reach. If you hold a reference to a node, inserting after it or unlinking its successor is a fixed number of attribute assignments no matter how long the list is. But arriving at position k costs k dereferences, because the nodes sit at unrelated addresses and no arithmetic can jump to the k-th one. That is why a singly linked list has no indexing operation and why finding a predecessor, which insertion-before and deletion both need, is O(n).
In real CPython the constant factors matter as much as the exponents. Every Node is a full Python object with its own header and, without __slots__, its own attribute dict, so a thousand-element chain is a thousand separate allocations scattered across the heap and each traversal step is a pointer chase that may miss cache. A built-in list shifting elements with a single memory move usually beats a hand-written linked list even where the linked list is asymptotically better. Learn the structure for the mental model and for the places it already appears inside other tools, and reach for it when you genuinely hold direct references to nodes and must splice them in constant time.
class Node:
__slots__ = ("value", "next")
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def values(node):
out = []
while node is not None:
out.append(node.value)
node = node.next
return out
head = None
for v in (1, 2, 3):
head = Node(v, head) # prepend, O(1), nothing is copied
print(values(head))
head.next = Node(99, head.next) # splice a node in after the head
print(values(head))
removed = head.next # unlink it again
head.next = removed.next
print(values(head), removed.value, removed.next.value)A linked list keeps order in the references between separate node objects, which makes restructuring at a node you already hold constant time and reaching that node linear time.
Worked examples
Reversing in place
Flips every link in one pass using three names and no new nodes.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(vals):
head = None
for v in reversed(vals):
head = Node(v, head)
return head
def values(node):
out = []
while node is not None:
out.append(node.value)
node = node.next
return out
def reverse(head):
prev = None
while head is not None:
nxt = head.next # save it: the next line destroys it
head.next = prev
prev = head
head = nxt
return prev
h = build([10, 20, 30, 40])
print(values(h))
h = reverse(h)
print(values(h))Example explained
Line 1nxt = head.next must run first, because head.next = prev overwrites the only reference to the rest of the chain.
Line 2prev starts as None, so the original first node ends up with .next = None and becomes the new tail.
Line 3The loop ends with head None and prev on the last node visited, which is why reverse returns prev, not head.
Line 4No Node is created or copied: only four names and one attribute per node are reassigned, so this is O(n) time and O(1) extra space.
Finding the middle without an index
Uses two pointers at different speeds because there is no way to jump to position n // 2.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(vals):
head = None
for v in reversed(vals):
head = Node(v, head)
return head
def middle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
for vals in ([1, 2, 3, 4, 5], [1, 2, 3, 4]):
print(vals, "->", middle(build(vals)).value)Example explained
Line 1slow advances one link per step and fast two, so when fast runs out slow has covered half the links.
Line 2The guard checks fast is not None before fast.next, since fast.next.next would raise AttributeError on the last node.
Line 3With an even count the loop stops with slow on the second of the two middle nodes, which is why [1, 2, 3, 4] gives 3.
Line 4This trick exists only because a linked list cannot compute the address of the middle node; a list would just use vals[len(vals) // 2].
A cached tail for O(1) append
Shows what a tail reference buys you and what it does not.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.n = 0
def append(self, value):
node = Node(value)
if self.tail is None:
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
self.n += 1
def pop_front(self):
node = self.head
self.head = node.next
if self.head is None:
self.tail = None
self.n -= 1
return node.value
def __iter__(self):
node = self.head
while node is not None:
yield node.value
node = node.next
ll = LinkedList()
for c in "abc":
ll.append(c)
print(list(ll), ll.n)
print(ll.pop_front(), list(ll), ll.tail.value)Example explained
Line 1append touches only self.tail.next and self.tail, so its cost does not depend on self.n.
Line 2pop_front must reset self.tail when the list becomes empty, otherwise tail keeps a dead node alive and the next append links onto it.
Line 3n is tracked by hand because the structure itself has no length; counting it would mean walking every node.
Line 4Removing the tail would still be O(n): the last node has no reference back to its predecessor, so it can only be found from head.
Important notes
Unlinking a node does not free it while any other name still references it, and that stale node keeps pointing into the live list, as removed.next shows in the main example.
Recursive traversal of a long chain hits Python's recursion limit around a thousand nodes, so write list algorithms as loops.
Common mistakes
Assigning node.next = new_node before setting new_node.next = node.next, which drops every element after node and leaves the tail unreachable.
Writing insert_front(head, v) that rebinds the local head parameter instead of returning the new node, so the caller's head still points at the old first node and the new value is invisible.
Relinking so a node ends up pointing back into an earlier node, which turns any while node is not None traversal into an infinite loop that appends forever until memory runs out.
Try it yourself
Change, predict, then run
Write delete_value(head, target) that removes the first node whose value equals target and returns the resulting head, correctly handling the case where the match is the first node. Test it on a chain built from [4, 7, 4, 9] by deleting 4, then 9, then 100.
Open the Python workspaceCheck your understanding
You hold a reference to a node n somewhere in the middle of a singly linked list, but not to head. Which operation can you do in constant time?
- Insert a new node immediately after n
- Insert a new node immediately before n
- Remove n from the list, leaving every other node in place
- Read the value of the node one position before n
Show answer
Inserting after n needs two assignments: point the new node at n.next, then point n.next at the new node. The other three all require n's predecessor, and a singly linked node stores no backward reference, so the predecessor can only be found by walking from head, which is O(n). Removing n is tempting because of the trick of copying n.next's value into n and unlinking n.next, but that moves a value into a different node object and fails outright when n is the tail, so it does not leave every other node in place.