Unit 02
Linked Lists
Instead of one continuous memory block, each element lives in its own node and points to the next one. Nothing needs to shift when you insert or remove — you just rewire a couple of pointers.
// each node only knows about the one after it
What it is
A linked list is a chain of nodes, where each node stores a value and a reference (pointer) to the next node. The list itself only needs to remember where the chain starts (the "head"). There's no requirement that nodes sit next to each other in memory — they can be scattered anywhere.
Why it's useful
- Cheap insertion and deletion. Adding or removing a node just means updating a couple of pointers, no shifting required.
- Grows naturally. There's no fixed size to outgrow — you just add another node.
Where it struggles
- No direct indexing. To reach the 50th node, you have to walk through the 49 before it — there's no shortcut.
- Extra memory per element. Each node needs space for its pointer(s), on top of the actual data.
- Less cache-friendly. Since nodes can be scattered in memory, traversing a linked list is typically slower in practice than scanning an array of the same size.
Time complexity
| Operation | Time |
|---|---|
| Access by position | O(n) |
| Insert / delete at head | O(1) |
| Insert / delete at known node | O(1) |
| Search | O(n) |