Arrays, stacks, queues, linked lists, and rooted trees — the five shapes that everything else in the book is built out of.
Part III is where CLRS stops solving problems and starts building the containers that solve them. Chapter 10 is the foundation layer: contiguous storage and pointer-linked storage, and the four access disciplines you can impose on them. Nothing here is difficult. What matters is having the cost of every operation and the reason for that cost available without thinking, because chapters 11 through 13, every graph algorithm in Part VI, and most of the design decisions you make in real code are downstream of exactly these trade-offs.
Part III opens by naming what all these structures are implementations of.
| Operation | Kind | Meaning |
|---|---|---|
SEARCH(S, k) | Query | Return a pointer to an element with key k, or NIL |
INSERT(S, x) | Modify | Add the element pointed to by x |
DELETE(S, x) | Modify | Remove the element pointed to by x — note it takes a pointer, not a key |
MINIMUM(S), MAXIMUM(S) | Query | The extreme element, for ordered sets |
SUCCESSOR(S, x), PREDECESSOR(S, x) | Query | The next or previous element in sorted order |
DELETE takes a pointer, not a key. This detail causes real confusion. CLRS defines deletion as taking a pointer to the element already located. If you only have a key, you must call SEARCH first and pay for that separately. The distinction matters enormously for linked lists, where deletion given a pointer is O(1) but finding the pointer is O(n). Quoting “linked list deletion is O(1)” without that qualification is the single most common data-structures error in interviews.An array is a block of contiguous memory holding n equal-sized elements. Its one superpower follows directly from that layout:
address of A[i] = base_address + (i - 1) · element_size // 1-indexedOne multiply and one add, independent of i and of n. That is why array access is Θ(1), and it is the only reason.
| Operation | Cost | Why |
|---|---|---|
Access A[i] | Θ(1) | Address arithmetic |
| Search unsorted | Θ(n) | Linear scan |
| Search sorted | Θ(lg n) | Binary search |
| Insert or delete at the end | Θ(1) | Nothing moves |
| Insert or delete in the middle | Θ(n) | Everything after it shifts |
vector, ArrayList, and Python list — is to allocate extra capacity and double it when full, copying everything to the new block. A single append can therefore cost Θ(n), but the doublings are rare enough that the average cost over a sequence of appends is O(1). That is amortized analysis, and Chapter 16 proves it. Doubling matters: growing by a fixed increment instead would make appends Θ(n) amortized.New in the 4th edition, and worth having because it explains performance differences that the RAM model cannot.
Memory is one-dimensional. A two-dimensional matrix has to be flattened, and there are two conventions:
Θ(1) access in the RAM model; on real hardware the loop order that matches the layout wins by a large constant.CLRS also mentions blocked layouts, where the matrix is stored as a grid of small submatrices each laid out contiguously. That is what makes tuned matrix-multiplication libraries fast, and it is the practical reason Strassen from Chapter 4 struggles to compete.
PUSH and delete is called POP, and neither takes an argument saying which element — the policy decides.An array of size n plus one index S.top implements it exactly.
STACK-EMPTY(S)
1 if S.top == 0
2 return TRUE
3 else return FALSE
PUSH(S, x)
1 if S.top == S.size
2 error "overflow"
3 S.top = S.top + 1
4 S[S.top] = x
POP(S)
1 if STACK-EMPTY(S)
2 error "underflow"
3 S.top = S.top - 1
4 return S[S.top + 1]All three are Θ(1). Note POP does not erase the slot — it just moves the index. The value is still physically there until overwritten.
Underflow is popping an empty stack, a program error. Overflow is pushing onto a full one, which a dynamic array avoids by reallocating.
ENQUEUE and adds at the tail; delete is DEQUEUE and removes from the head.The array implementation is subtler than the stack, because both ends move. If you never reused space, the queue would crawl off the end of the array. The fix is to wrap around, treating the array as circular.
Q.head points at the next element to leave; Q.tail at the next free slot.ENQUEUE(Q, x)
1 if Q.size == Q.length // would overflow
2 error "overflow"
3 Q[Q.tail] = x
4 if Q.tail == Q.length
5 Q.tail = 1 // wrap around
6 else Q.tail = Q.tail + 1
7 Q.size = Q.size + 1
DEQUEUE(Q)
1 if Q.size == 0
2 error "underflow"
3 x = Q[Q.head]
4 if Q.head == Q.length
5 Q.head = 1 // wrap around
6 else Q.head = Q.head + 1
7 Q.size = Q.size - 1
8 return xBoth Θ(1). Keeping Q.size explicitly is the cleanest way to distinguish empty from full; the alternative is to leave one slot permanently unused.
Θ(1). It generalises both the stack and the queue, and CLRS leaves it as an exercise.Where queues show up: breadth-first search in Chapter 20 is defined by its queue — swap the queue for a stack and BFS becomes DFS. Also task scheduling, buffering, and every producer-consumer pipeline.
x has x.key, x.next, and in a doubly linked list x.prev. The list handle L has L.head, and L.head = NIL means the list is empty.| Variant | Property |
|---|---|
| Singly linked | Only next. Half the pointer overhead, but you cannot walk backwards, which makes deletion given a pointer Θ(n). |
| Doubly linked | Both next and prev. Deletion given a pointer is Θ(1). |
| Sorted | Linear order matches key order, so the minimum is the head. Insertion becomes Θ(n). |
| Circular | The last node’s next points at the head and the head’s prev at the last node. No NIL ends. |
LIST-SEARCH(L, k)
1 x = L.head
2 while x ≠ NIL and x.key ≠ k
3 x = x.next
4 return x // Θ(n) worst case
LIST-PREPEND(L, x)
1 x.next = L.head
2 x.prev = NIL
3 if L.head ≠ NIL
4 L.head.prev = x
5 L.head = x // Θ(1)
LIST-DELETE(L, x)
1 if x.prev ≠ NIL
2 x.prev.next = x.next
3 else L.head = x.next
4 if x.next ≠ NIL
5 x.next.prev = x.prev // Θ(1) — given the pointer xCount the NIL tests. Four of the twelve lines exist only to handle the two boundary cases, head and tail. That noise is what sentinels remove.
Θ(1) deletion claim, precisely. LIST-DELETE(L, x) is Θ(1) because it is handed the pointer. Deleting by key means LIST-SEARCH first, so the real cost is Θ(n). And in a singly linked list even pointer deletion is Θ(n), because you must scan from the head to find the predecessor whose next needs rewriting.A sentinel is a dummy object that lets you treat a boundary condition as an ordinary case. For a doubly linked list, add one node L.nil and make the list circular around it: L.nil.next is the head, L.nil.prev is the tail, and the real ends point back at L.nil instead of holding NIL.
L.nil holds no key; it exists purely to eliminate boundary cases.LIST-DELETE'(x) // with sentinel
1 x.prev.next = x.next
2 x.next.prev = x.prev
LIST-INSERT'(L, x) // insert at the head
1 x.next = L.nil.next
2 L.nil.next.prev = x
3 L.nil.next = x
4 x.prev = L.nilCompare with the versions above. Every NIL test is gone, because x.prev and x.next are never NIL — at worst they are the sentinel.
T.nil node in red-black trees (Chapter 13) is exactly the same idea and is what makes the rebalancing cases tractable to write down.Linked structures generalise beyond lines. The question is how many children a node may have.
Three pointers per node: x.p (parent), x.left, x.right. The tree handle T holds T.root, and T.root.p = NIL. A missing child is NIL. This is the representation used for binary search trees and red-black trees in the next chapters.
If a node can have any number of children you cannot pre-declare a fixed set of pointers, and one pointer per child would waste space when the count varies. The standard trick uses exactly two pointers per node regardless of the number of children:
x.left-child points to the first child of x.x.right-sibling points to the next child of x’s parent.left-child pointer.O(n) pointers for n nodes no matter how the branching varies. The price is that reaching the kth child takes k steps instead of one, and there is no random access among siblings. This representation is used for the disjoint-set forests of Chapter 19 and, in spirit, for adjacency lists in Chapter 20.CLRS notes that other schemes exist and the right one depends on the application — for example, storing children in an array or a hash table per node when random access among siblings matters. Chapter 18’s B-trees do exactly that, with a fixed-capacity array of children per node.
This is the table worth having memorised. Every entry is derivable from the layout, and knowing why beats knowing what.
| Operation | Unsorted array | Sorted array | Singly linked | Doubly linked | Stack / Queue |
|---|---|---|---|---|---|
| Access by index | Θ(1) | Θ(1) | Θ(n) | Θ(n) | — |
| Search by key | Θ(n) | Θ(lg n) | Θ(n) | Θ(n) | — |
| Insert at front | Θ(n) | Θ(n) | Θ(1) | Θ(1) | Θ(1) |
| Insert at end | Θ(1)* | Θ(n) | Θ(n)† | Θ(n)† | Θ(1) |
| Delete given a pointer | Θ(n) | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Minimum | Θ(n) | Θ(1) | Θ(n) | Θ(n) | — |
| Successor of an element | Θ(n) | Θ(1) | Θ(1)‡ | Θ(1)‡ | — |
| Memory overhead | None | None | 1 pointer/node | 2 pointers/node | Small |
* amortized, with a doubling dynamic array. † Θ(1) if you maintain a tail pointer. ‡ in list order, which equals key order only if the list is sorted.
Θ(n). On real hardware the array wins by a large factor, because a linear scan of contiguous memory is prefetched perfectly while a pointer chase stalls on cache misses. For small n a linear scan of an array frequently beats a “better” structure outright. Measure before believing the table.SEARCH, MINIMUM, SUCCESSOR) and modifications (INSERT, DELETE). DELETE takes a pointer, not a key — the search is billed separately.Θ(1) access from address arithmetic alone, and pay Θ(n) for insertion or deletion in the middle. Dynamic arrays double on overflow, giving O(1) amortized append.top index, all operations Θ(1). Underflow is popping empty; overflow is pushing full.head and tail. Empty and full look identical unless you keep a size or waste a slot.Θ(1) only in a doubly linked list and only given the pointer.p, left, right. Left-child, right-sibling represents arbitrary branching with two pointers per node.Both structures so far force a choice between fast lookup and fast modification. Chapter 11 refuses the choice: a hash table computes an array index directly from the key, giving Θ(1) expected search, insert, and delete. The cost is that all ordering information is destroyed — no minimum, no successor, no range queries. Chapter 12 then takes the opposite route with binary search trees, which keep order and accept O(h) per operation, and Chapter 13 makes h provably O(lg n).