What is a linked list?
A linked list is a chain of small pieces, called nodes, where each node holds a value and a link to the next node. The nodes can sit anywhere in memory, because the links join them.
That makes inserting and deleting cheap, because you change a link instead of moving a whole row of items. The price is that you must walk the chain to find anything.
By the end of this lesson
Note
I can build and walk a linked list.
Key words
| Word | What it means | Example |
|---|---|---|
| Node | one piece of a linked list: a value and a link | |
| Link | a reference to the next node | node.next |
| Head | the first node, the way into the list | |
| Reference | a name that points at a value in memory | |
| Traverse | visit the nodes one by one from the head | |
| Class | a recipe for making objects of one kind | class Node: |
The cells students fill in are left blank in this preview.
A node holds a value and a link
Python needs a class to make a node. A class is a recipe, and each node made from it is an object with its own fields.
The __init__ function runs when a node is made. self.value stores the value. self.next stores the link, and it starts as None, which means "nothing here". The last node of a list always has next equal to None.
Build three nodes and walk them
# A node holds a value and a link to the next node.
class Node:
def __init__(self, value):
self.value = value
self.next = None
first = Node("hello.c")
second = Node("scope.c")
third = Node("calc.y")
first.next = second
second.next = third
# Walk from the head until the link is None.
current = first
while current is not None:
print(current.value)
current = current.next
# Add a fourth node, "Makefile", after the third and run again.
A link is a reference, not a copy
A name in Python does not hold the value itself. It points at it. Two names can point at the same thing.
A link works the same way: first.next = second makes first point at the very node second points at. Nothing is copied, so changing a link is one cheap step.
Two names for one list
python3 -c "a = [1, 2, 3]; b = a; b.append(4); print(a)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A node as a pair, read by links
python3 -c "node = ['a', ['b', ['c', None]]]; print(node[1][1][0])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think b = a makes a copy of a list. It does not. It gives the same list a second name, so a change made through b shows through a. When you reverse a linked list, the nodes are the same ones, only the links change.
Inserting and deleting only change links
To insert after a node, make the new node point at the old next node, then make the node point at the new one. The order matters.
To delete the node after current, set current.next to current.next.next. To find a place you still walk from the head, one node at a time.
Worked example: array against linked list
| Operation | Array | Linked list |
|---|---|---|
| Read item number 500 | One step | 500 steps from the head |
| Insert at the front | Shifts every item | One link changed |
| Insert after a node you hold | Shifts later items | Two links changed |
| Memory | One block | A node each, plus a link each |
The cells students fill in are left blank in this preview.
Reversing turns every link round
To reverse a list, walk it once and make each node point at the one before it. Use three names: previous, current and following.
Save following first, or the rest of the list is lost the moment you change current.next.
Worked example: reversing 1, 2, 3
| Step | previous | current | Links after the step |
|---|---|---|---|
| Start | None | 1 | 1 to 2 to 3 |
| 1 | 1 | 2 | 1 to None, 2 to 3 |
| 2 | 2 | 3 | 2 to 1, 3 unchanged |
| 3 | 3 | None | 3 to 2 to 1 to None |
The cells students fill in are left blank in this preview.