Boxes joined by arrows
An array keeps its items side by side in memory. A linked list does not. Each item sits in its own small box, called a node, and a node holds two things:
- a value, and
- an arrow (a pointer) to the next node.
The list itself is just a pointer to the first node, the head. To read the list you start at the head and follow arrows until an arrow points at nothing.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
head = Node(1, Node(2, Node(3))) # 1 -> 2 -> 3 -> NoneWhat that buys you, and what it costs
Example
Insert in the middle
To put a new node between 2 and 3, point the new node at 3, then point 2 at the new node. Two arrows change. Nothing else in the list is touched.
In an array, everything after that position would have to shift one place to make room.
Good at
- Insert or remove anywhere by changing one or two arrows
- Grows one node at a time, with no resizing and no copying
Where it bites
- No jumping to position 500: you must walk there from the head
- Each node needs extra memory for its arrow
- Nodes are scattered in memory, which makes walking them slower than walking an array
Reversing a list without moving anything
This is the classic linked list exercise, and it shows what "the arrows are the structure" really means. To reverse 1 → 2 → 3 → 4 → 5, no node moves and no value is copied. Each arrow is simply turned around.
It takes three markers that walk along the list together:
- curr: the node whose arrow is about to be turned.
- prev: the node before it, which is where the arrow will point.
- nxt: the node after it, saved so the rest of the list is not lost.
1prev = None2curr = head3while curr is not None:4 nxt = curr.next5 curr.next = prev6 prev = curr7 curr = nxt8head = prev
Grey arrows still point forwards. Pink arrows have been turned around.
Start. A list of five nodes. Each node holds a value and an arrow to the next node. The goal: make every arrow point the other way.
Save the way forward
nxt = curr.next. Once curr's arrow is turned, this would be the only way left to reach the rest of the list.Turn the arrow
curr.next = prev. The node now points backwards.Step both markers forward
prev = curr, thencurr = nxt.Repeat until curr falls off the end
The last node visited is the new head.
Each node is visited once and only three extra variables are used, however long the list is.
Where you will meet it
- Queues and stacks in standard libraries are often linked lists underneath.
- LRU caches keep items in a linked list so that moving one to the front is a few arrow changes. See Cache Eviction Policies.
- Hash tables that use chaining keep a small linked list in each bucket.
Key takeaways
- A linked list is a chain of nodes. Each holds a value and a pointer to the next.
- Inserting and removing change a couple of pointers. Reaching a position means walking to it.
- Reversing a list turns each arrow around. No node moves.
- Always save the next node before changing an arrow.