Doubly linked lists
The list you built is singly linked, with each node pointing 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 beside head.
What that buys:
- walking 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, and unit 5's
dequeis built this way
The costs are real. Every node carries one extra pointer, which is more memory across a large list, and every change touches more wiring: an insert updates four pointers rather than two, and each one has to be correct.
The trade is worth naming plainly. A doubly linked list spends memory and code complexity to buy back the ability to move backward, which is the single capability a singly linked list lacks.
Arrays against 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 or delete at front | O(n) | O(1) |
| insert or delete at end | amortized O(1) | O(n), or O(1) with a tail pointer |
| insert or 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 extra pointers per node, scattered |
One row deserves emphasis beyond its Big-O. Modern CPUs read contiguous memory far faster than scattered memory, an effect called cache locality, so arrays often win in practice even on rows where the table calls it a tie.
The reason is that a CPU fetches memory in blocks. Reading array item 5 pulls items 6 through 12 into cache for free, while following a pointer to a node somewhere else pulls in nothing useful.
So the rule for reaching past arrays is narrower than the table suggests. Choose a linked structure when the shape of your edits demands it, most famously the O(1) both-ends behavior that powers unit 5's deque, rather than because a row says O(1).
Deleting the cursor's line in O(1) needs a doubly linked list, because node.prev and node.next allow the unlink to happen in place.
With the node already in hand, the operation is two assignments, rewiring node.prev.next and node.next.prev to skip past it. No search and no shifting, so the cost does not depend on the file's length.
Both alternatives fail on this operation. An array must shift every later line to close the gap, which is O(n). A singly linked list has the node but not its predecessor, so it has to re-walk from the head to find the node before it, which is also O(n).
The detail that makes the doubly linked list win is having the node reference already. Without it, finding the line in the first place would be O(n) in any of the three.
An array fits better.
Reading by position is the operation that must be fast, and an array indexes in O(1) through base + i × size, while a linked list walks 742 pointer hops on every single read.
The linked list's advantage buys nothing here. Its O(1) edits only matter when edits happen, and the premise says they almost never do, so the structure would be paying for a capability the program does not use.
That is the general shape of these decisions. Identify the operation your program performs most often, then read the row for that operation, since the structure that wins the rare operations is irrelevant.