Card 01/ 09
Linked Lists: Nodes Joined by References
Each node holds a value and the address of the next, so the list can live anywhere in memory.
A linked list stores a sequence as separate nodes, each holding one value and a reference to the node after it, so the elements can sit anywhere in memory. This card covers how those references make the list, why reading the element at a position means walking from the start, and what a reference to the last node adds.
A treasure hunt works the same way. Each clue says where the next one is hidden, so the hunt can spread across a whole house, and the only way to reach the fifth clue is to follow the first four. The comparison stops at changes: nobody slips a new clue into the middle of a hunt, and a linked list does exactly that by changing two references.
A list holding 3, 7 and 5 is three nodes. A node is a small record with two fields: value, and next, a reference to the following node. A reference is the address of another object, which is how Python, Java and TypeScript keep one object inside another. The list itself keeps head, a reference to the first node, and often tail, a reference to the last. The last node's next is null, the value meaning no object, written None in Python.
head -> [3] -> [7] -> [5] -> null
tail -> [5]No formula gives the address of the node at position i, as one does for an array, so reading position i means starting at head and following next i times. Changing the list never moves a value: an insert or a delete rewrites one or two references, wherever the nodes happen to be.
In general, a singly linked list is a chain of nodes each linked only to the next, and its order lives in the references rather than in where the nodes sit. A Python list is not one, despite the name. It is a dynamic array, one block of adjacent cells that grows by copying, so reading items[5] is one calculation and inserting at the front shifts every element.
The table gives the worst case of each operation on a list of n nodes, with and without the tail reference.
| Operation | Head only | Head and tail |
|---|---|---|
| Read the element at position i | O(n) | O(n) |
| Search for a value | O(n) | O(n) |
| Insert at the front | O(1) | O(1) |
| Append at the end | O(n) | O(1) |
| Insert after a node you hold | O(1) | O(1) |
| Delete the first node | O(1) | O(1) |
| Delete the last node | O(n) | O(n) |
The trade is the opposite of an array's: a linked list gives up the instant read by position so that a change at a node you already hold costs O(1). Deleting the last node stays O(n) even with a tail reference, because the node before it has to become the new last node, and only a walk from the head finds it.
← → move through sections and cards