2.2 Linked Lists
Prerequisite: Arrays, about 45 minutes. This lesson completes the statement "linked-list insertion is constant time" with an accurate contract covering position handles, predecessors, a tail pointer, and ownership.
Start with Nodes and Links
A linked list maintains order through references instead of contiguous indexed slots. That choice makes local rewiring cheap, but gives up direct access by integer index.
A linked list is defined by its links
The logical structure of a singly linked list is:
head
│
▼
[1 | next] → [2 | next] → [3 | None]Implementations typically allocate space separately for each node, so nodes might not be adjacent. However, saying they're "scattered all over memory" is an overstatement. Memory pools, region allocators, or compact runtimes can place nodes very close together. The linked list's abstraction contract only requires next to establish order.
A minimal Python node can be written like this:
class ListNode:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
head = ListNode(1, ListNode(2, ListNode(3)))The name next_node avoids shadowing Python’s built-in next() function.
Index Search: Let's first establish the indexing rules
The index in this chapter starts from 0. k = 0 returns the head node; negative values are not accepted:
def get_kth(head, k):
if k < 0:
raise IndexError("index out of range")
current = head
for _ in range(k):
if current is None:
raise IndexError("index out of range")
current = current.next
if current is None:
raise IndexError("index out of range")
return currentTo reach the kth node, you need k links, taking Θ(k + 1) time; when k is of the same order as the list length n, the worst case is Θ(n). A linked list does not have a formula to directly compute the address of the kth node from head.
Insertion and Deletion: Prerequisites for Constant-Time Operations
Insert with Known Predecessor
def insert_after(previous, value):
if previous is None:
raise ValueError("previous node is required")
node = ListNode(value, previous.next)
previous.next = node
return nodeCreate a node and write two links; the operation count does not grow with n, so it's Θ(1). The precondition is that the caller already holds the previous belonging to this list.
If the caller provides "insert after index i", the implementation must first reach the ith node, locate Θ(i + 1), modify the link Θ(1), resulting in a total time of Θ(i + 1), with the worst-case scenario being Θ(n).
Deleting a node from a singly linked list requires a predecessor
def delete_after(previous):
if previous is None or previous.next is None:
raise IndexError("no successor to delete")
removed = previous.next
previous.next = removed.next
removed.next = None
return removedGiven a predecessor, it is Θ(1). Holding only the target node is usually insufficient to delete a tail node from a singly linked list; finding the predecessor might still take Θ(n).
There's an interview trick that copies the successor's value into the target node and then deletes the successor. It alters the node's identity semantics, fails for tail nodes, and might break external references to the node. You can't treat it as a general-purpose delete contract.
Sentinels and Tail Pointers Solve Different Problems
Place a sentinel before the first data node; its value is not part of the list:
sentinel → first → ... → tail → NoneIt lets insertion into an empty list and deletion of the head use the same operation: update the predecessor’s next. The tail pointer allows appending without having to search from the head each time.
| Status | Invariant |
|---|---|
| Empty list | sentinel.next is None, tail is sentinel, size == 0 |
| Non-empty | sentinel.next is head, tail.next is None |
| After each insertion or deletion | The number of nodes reachable from the beginning equals size, and the tail points to the last node |
The sentinel reduces branching but does not automatically maintain these invariants. Failing to update the tail pointer still causes the next append to land in the wrong location.
A Runnable Singly Linked List
This Python 3.10+ implementation records _owner on each node, so it can reject foreign or detached nodes in constant time. Both insert_after and delete_after require a predecessor belonging to the current list. Callers may retain returned nodes, but must not bypass the container to modify links or _owner; a production interface normally encapsulates those fields.
The model counts allocation of one fixed-size node as constant work. Actual allocation, garbage collection, and element construction or destruction need separate accounting.
# linked_list_demo.py
class ListNode:
def __init__(self, value: object, next_node: "ListNode | None" = None) -> None:
self.value = value
self.next = next_node
self._owner = None
class SinglyLinkedList:
def __init__(self) -> None:
self._sentinel = ListNode(None)
self._sentinel._owner = self
self._tail = self._sentinel
self._size = 0
@property
def size(self) -> int:
return self._size
def append(self, value: object) -> ListNode:
node = ListNode(value)
node._owner = self
self._tail.next = node
self._tail = node
self._size += 1
return node
def insert_after(self, previous: ListNode | None, value: object) -> ListNode:
if previous is None or previous._owner is not self:
raise ValueError("previous node does not belong to this list")
node = ListNode(value, previous.next)
node._owner = self
previous.next = node
if self._tail is previous:
self._tail = node
self._size += 1
return node
def delete_after(self, previous: ListNode | None) -> object:
if previous is None or previous._owner is not self:
raise ValueError("previous node does not belong to this list")
if previous.next is None:
raise IndexError("no node exists after previous")
removed = previous.next
previous.next = removed.next
if self._tail is removed:
self._tail = previous
removed.next = None
removed._owner = None
self._size -= 1
return removed.value
def get_kth(self, index: int) -> ListNode:
if index < 0:
raise IndexError("index out of range")
current = self._sentinel.next
for _ in range(index):
if current is None:
raise IndexError("index out of range")
current = current.next
if current is None:
raise IndexError("index out of range")
return current
def middle_node(self) -> ListNode:
slow = self._sentinel.next
fast = self._sentinel.next
if slow is None:
raise IndexError("empty list has no middle node")
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
assert slow is not None
return slow
def reverse(self) -> None:
old_head = self._sentinel.next
previous = None
current = old_head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
self._sentinel.next = previous
self._tail = old_head if old_head is not None else self._sentinel
def to_list(self) -> list[object]:
result: list[object] = []
current = self._sentinel.next
for _ in range(self._size):
assert current is not None
result.append(current.value)
current = current.next
assert current is None
return result
def main() -> None:
linked = SinglyLinkedList()
linked.append(1)
second = linked.append(2)
linked.append(3)
linked.append(4)
initial = linked.to_list()
inserted = linked.insert_after(second, 9)
after_insert = linked.to_list()
removed = linked.delete_after(inserted)
middle = linked.middle_node().value
linked.reverse()
assert initial == [1, 2, 3, 4]
assert after_insert == [1, 2, 9, 3, 4]
assert removed == 3
assert middle == 9
assert linked.to_list() == [4, 9, 2, 1]
assert linked.size == 4
print(f"Initial: {initial}")
print(f"After insertion: {after_insert}")
print(f"Delete: {removed}")
print(f"Midpoint: {middle}")
print(f"Reverse: {linked.to_list()}")
print("Linked list check passed")
if __name__ == "__main__":
main()Run:
python3 linked_list_demo.pyOutput:
Initial: [1, 2, 3, 4]
After insertion: [1, 2, 9, 3, 4]
Delete: 3
Midpoint: 9
Reverse: [4, 9, 2, 1]
Linked list check passedWhen the length is even, the fast-slow pointer in this chapter returns the second of the two midpoints. Therefore, [1, 2, 9, 4] returns 9. If the interface requires the first midpoint, the initial position of the fast pointer or the loop condition should be changed, and the convention should be documented in the tests.
Singly Linked List Operations Table
| Operation | Precondition | Time | Notes |
|---|---|---|---|
Reading the kth node | Only head node | Θ(k + 1) | Out-of-bounds and negative rules |
| Head insertion | Has sentinel/head handle | Θ(1) | Update head link |
| Append tail | Maintain tail handle | Θ(1) | Empty list and tail invariant |
| Append tail | Only head node | Θ(n) | First find tail |
| Insert after predecessor | Known predecessor | Θ(1) | Predecessor must belong to this list |
| Delete successor | Known predecessor | Θ(1) | Might need to update tail |
| Delete by value | Only head node | Worst-case Θ(n) | Predecessor lookup dominates |
| Delete tail node | Only head and tail | Θ(n) | A singly linked list still needs to find the predecessor |
| Full traversal | Has head node | Θ(n) | Establish strategy first when cycles are possible |
The "handle" in the table can be a node reference, a controlled iterator, or a position object provided by a container. When only an integer index is given, the linked list must traverse.
Doubly Linked List
A doubly linked list node stores both predecessor and successor:
None ← [1] ⇄ [2] ⇄ [3] → Noneclass DoublyNode:
def __init__(self, value, previous=None, next_node=None):
self.value = value
self.previous = previous
self.next = next_node
def unlink(node, head, tail):
if node.previous is None:
head = node.next
else:
node.previous.next = node.next
if node.next is None:
tail = node.previous
else:
node.next.previous = node.previous
node.previous = None
node.next = None
return head, tailunlink requires a live node in the current acyclic doubly linked list, with head and tail from that same list. Deleting an already detached node violates this precondition. Given such a node, deletion changes a fixed number of links in Θ(1) time. Bidirectional traversal doesn't require repeatedly starting from the beginning. The cost is one additional link per node, more frequent write operations for insertions and deletions, and more complex invariants. The total node memory doesn't necessarily double exactly, because object headers, alignment, and payload values still take up space.
Circular Linked List
A circular linked list has the last node pointing back to the first node:
head → [A] → [B] → [C]
▲ │
└───────────┘It's suitable for polling routes where members can be added or removed. During iteration, you can't wait for None:
def circular_values(head):
if head is None:
return []
result = [head.value]
current = head.next
while current is not head:
result.append(current.value)
current = current.next
return resultThis traversal requires a nonempty input to form one complete cycle through head. If the chain enters a cycle elsewhere, it never returns to head; if a link is broken, it reaches None. Termination compares node identity with is, since values may repeat. Visiting n nodes takes Θ(n) time, and the returned list occupies Θ(n) output space.
A ring buffer is typically implemented using a fixed array and two index pointers, and it is not a synonym for a circular linked list. Both can express cyclic usage of positions, but they differ in layout and complexity.
Three Basic Algorithms
In-place Reverse
After saving the successor, reverse the current link:
def reverse(head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previousEach node is processed once, taking time Θ(n); only three node references are saved, with auxiliary space Θ(1).
Find the Midpoint
def middle_node(head):
if head is None:
raise IndexError("empty list")
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slowThe fast pointer moves two steps per iteration, while the slow pointer moves one. When the fast pointer reaches the end, the slow pointer has advanced approximately halfway. Time Θ(n), auxiliary space Θ(1). The current implementation returns the second midpoint for even-length lists.
Floyd's Cycle Detection
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseWhen there's no cycle, the fast pointer reaches None. When there is a cycle, both pointers eventually meet within the cycle. Let μ be the number of nodes before the cycle and λ its length. Once both pointers are inside it, their relative position advances by 1 modulo λ per iteration, so they meet within another λ iterations. Time is Θ(μ + λ), or Θ(n) when n counts distinct reachable nodes; auxiliary space is Θ(1). Compare node identities, not values.
Lists and Position Handles in Language
Python
The standard library doesn't have a generic LinkedList type. Queues or deques typically use collections.deque, which is not the hand-written node chain described in this chapter. Hand-written nodes are suitable for learning algorithms or representing domain structures that require stable node identity.
Python's garbage collector can handle regular reference cycles, but external resources like files and locks should still be explicitly managed. Don't rely on when list nodes are garbage collected to close resources.
Java 17+
LinkedList<E> is a doubly linked list that implements List and Deque. General index access may involve traversal, but addFirst, addLast, removeFirst, and removeLast directly operate on the ends.
LinkedList.add(0, value) operates at the front and does not traverse the entire list; a middle index still has to be located. For an ordinary queue or stack, ArrayDeque is usually more direct; it rejects null and is not thread-safe.
C++
std::forward_list is a singly linked list, std::list is a doubly linked list. The standard list supports constant-time insertion or deletion of one element with a valid iterator; bulk operations also depend on the number of elements processed. Insertion preserves existing references and iterators. Deletion invalidates only those referring to erased elements.
Node and element destruction follows C++ ownership rules. Teaching raw pointers requires implementing destructors, copy/move semantics, and exception safety; business code typically starts with standard containers or smart pointers.
Linked Lists and Caching
Linked list traversal includes dependency loading: you only know the next node's address after reading the current node. Nodes allocated separately also introduce overhead from allocation metadata, pointers, and alignment. Array sequential scanning takes advantage of adjacent slots more efficiently.
These factors won't change the fact that both traversals are Θ(n), but they will affect the constants. The gap has no universal multiple; node pools, element sizes, access patterns, runtime, and processor all influence the outcome. When making choices, use real operation combinations as benchmarks, not generic "10x faster" claims.
How to Locate Common Errors
| Symptom | First Check |
|---|---|
Accessing the 0th empty list returns None | Should the interface return null or throw IndexError? Specify in the contract |
| Inserted node is unreachable | Did assigning a link overwrite the original successor before it was saved? |
| Appending loses data after tail deletion | Was tail updated upon deletion |
| Reversed with only one node | Before modifying the link, was next_node saved? |
| Traversal never ends | Does the input contain a cycle while traversal still waits for None? |
| Backward traversal breaks in a doubly linked list | Does it simultaneously update both previous and next |
| Deleted node still connected by links | Should removal clear links, and do external handles still refer to the node? |
Maintain the Link Invariant
- Add
prepend(value)to the example class to verify that both empty and non-empty lists maintain the tail pointer invariant. - Merge two acyclic sorted singly linked lists that share no nodes, without allocating new data nodes; state that the input lists will be rewired.
- Change
middle_nodeto return the first midpoint if the length is even, and write assertions for lengths 0, 1, 2, and 4. - Implement
cycle_entry(head)to return the cycle entry node, rather than a boolean value alone. - Design a doubly linked list with two sentinels, verifying that
head_sentinel.next is tail_sentinelfor an empty list.
State What the Caller Already Holds
Implement "insert after known predecessor" and "insert by index". The former only modifies a constant number of links, while the latter requires traversing from head to the target position. Add assertions for empty list, single-node list, deletion of tail node, and out-of-bounds insertion, and always verify the head, tail, and size invariants.
For reverse, midpoint, and Floyd cycle detection, specify time and auxiliary space complexity. If the input may contain a cycle, any traversal terminating solely on None must be re-evaluated.
The next page puts arrays and linked lists into one table. The comparison specifies the location method, movement cost, cache behavior, and iterator contract instead of stopping at the word "insert."