Doubly linked lists
The list you built is singly linked: each node points forward only, which is exactly why delete needed the look-ahead trick. A doubly linked list gives every node two pointers, next and prev, and usually keeps a tail pointer next to head.
What that buys:
- walk the chain in either direction
- O(1) insert or delete given a reference to the node itself, since
node.previs right there - O(1) operations at both ends, which is precisely what a queue needs (unit 5:
dequeis built this way)
The cost: one extra pointer per node (more memory) and more rewiring per change: an insert touches four pointers instead of two, and every one must be right.
Arrays vs linked lists: the honest table
| operation | dynamic array | singly linked list |
|---|---|---|
| read by index | O(1) | O(n) |
| search by value | O(n) | O(n) |
| insert/delete at front | O(n) | O(1) |
| insert/delete at end | amortized O(1) | O(n), or O(1) with a tail pointer |
| insert/delete in middle (node in hand) | O(n) | O(1) |
| binary search when sorted | O(log n) | not practical |
| memory | one compact block | + one or two pointers per node, scattered |
One row deserves emphasis: modern CPUs read contiguous memory much faster than scattered memory (cache locality), so arrays often beat linked lists even on paper-tied rows. Reach for linked structures when the shape of your edits demands them, most famously the O(1) both-ends behavior that powers unit 5's deque.
Quiz
A text editor keeps each line as a node and holds a reference to the cursor's node. The user deletes the current line. Which structure makes that O(1)?
Problem
You need to read item #742 of a 1,000-item collection many times per second, and you almost never insert or delete. Which structure fits better: "array" or "linked list"?