A Python list keeps its items side by side. A linked list does not. Each item sits in its own small object, called a node, and each node tells you where the next one is. This changes which jobs are fast and which are slow.
A node and its next
You met the node class in PYTH-5. A node holds two things: a value, and a reference to the next node. The last node’s next is None. That is how you know the list has ended.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
head = Node(3, Node(8, Node(5))) # 3 -> 8 -> 5 -> None
The list as a whole is just a reference to its first node. This first node is called the head. If you have the head, you can reach every node by following next again and again. If you lose every reference to the head, you lose the list.
A reference is how Python names an object. a = b does not copy a node; it makes a refer to the same node as b. So cur = cur.next moves the name cur on by one node. It does not change any node.
A block against a chain
A Python list keeps references to its items in one block of memory, one after another. To read item k, Python works out its place directly: the start of the block, plus k places. That takes the same time for any k.
Nodes can be anywhere in memory. Nothing says where node 4 is, except node 3. So to read item k you must start at the head and follow next k times. Step through both:
A Python list keeps its items side by side, in one block of memory. So the place of item k is easy to work out: the start of the block, plus k places.
What is fast and what is slow
Here n is the number of items. “A node you hold” means you already have a reference to it, for example in a name like cur.
| Job | Python list | Linked list |
|---|---|---|
| Read item k | O(1) | O(k) |
| Add or remove at the front | O(n): every item moves | O(1) |
| Add or remove at the end | O(1) on average | O(1) if you keep a tail name, else O(n) |
| Insert or delete next to a node you hold | O(n): items after it move | O(1) |
| Find a value | O(n) | O(n) |
| Memory per item | one reference | a whole object: value, next, and the extra data Python keeps for every object |
So a linked list is good when you change the list in the middle often, and you already hold the place to change. It is bad when you read by position.
Linked lists in Python
Python has no built-in linked list class, and in everyday Python code you rarely need one. A list, or collections.deque (lesson 3), is usually faster, for two reasons. The items sit close together in memory. And their methods are built into Python and written in C, a language that runs much faster than Python code.
Linked lists still matter, for three reasons:
- The same idea, objects joined by references, is how trees and graphs are built. The TREE, HEAP and GRPH stations all depend on it.
- Some structures need to remove an item from the middle in O(1). A cache that drops the least recently used item (HASH-7) does this with a two-way linked list.
- Linked list problems train you to change references carefully, in the right order. That skill carries over to all pointer work.
LINK-1 counts as completed once you step through the figure to the last step.