Card 09/ 09
Recap: Linked Lists
Rewire in order, keep the tail current, and pay O(n) to reach a position.
Linked Lists comes down to the six ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| A linked list is a chain of nodes joined by references, so reading position i walks i nodes from the head | Linked Lists: Nodes Joined by References |
| Insert by pointing the new node at what follows first, then pointing the node before at it | Insert and Delete a Node by Rewiring References |
| Delete walks with the node before, because unlinking changes that node's next | Singly Linked List in Python, Java and TypeScript |
| Every operation that can change the last node must move the tail too | Forgetting to Update the Tail |
| A reference to the previous node makes every change at a node you hold O(1), but not search | Doubly Linked Lists and What the Back Reference Buys |
| Rewiring is O(1) only once the node is held; reaching position i still costs O(n) | Linked List vs Dynamic Array |
The comparison reduces to the operations where the structures differ, each list keeping head and tail references.
| Operation | Dynamic array | Singly linked list | Doubly linked list |
|---|---|---|---|
| Read the element at position i | O(1) | O(n) | O(n) |
| Binary search a sorted sequence | O(log n) | O(n) | O(n) |
| Insert or delete at the front | O(n) | O(1) | O(1) |
| Delete the last element | O(1) | O(n) | O(1) |
| Delete a node you hold | Not applicable | O(n) | O(1) |
| Extra memory per element | None | One reference | Two references |
Together they let you choose a linked list where a program changes a sequence at nodes it already holds, and make each change in an order that keeps every node reachable and the tail current.
← → move through sections and cards