Linked lists: follow references
Picture
A holds 3 and points to B. B holds 5 and points to C. There is no index jump to C.
Predict
Can a singly linked list read its kth item in O(1)?
Walk through the small example
No. Insertions can rewire local references without shifting later elements.
Mental model and complete Python solution
A node is a value plus a door to the next node. Algorithms carry a few named hands—current, previous, next—and must know which door each hand preserves.
What the function promises: Build a chain from values and convert it back to a list. Empty input produces None.
class Node:
def __init__(self, value, next_node=None):
self.value, self.next = value, next_node
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
answer = []
while head is not None:
answer.append(head.value)
head = head.next
return answer
assert to_list(build([3,5,8])) == [3,5,8]
assert build([]) is None
Work and storage: Building and traversal are O(n); each node stores one next reference.
When to recognize it: Insertions can rewire local references without shifting later elements.
Check before applying it: Random access requires traversal, and losing a reference can lose the rest of the chain.
Change one rule
Nodes also point backward.
See what changes
A doubly linked list spends another reference to enable local removal when a node is already known.
Connect
links: A link is stored explicitly rather than implied by neighboring indices.
Reverse a linked list: Reversal needs the next reference saved before rewiring.