B. 9 8 7. Last in, first out: 9 went on last, so it comes off first. A stack reverses the order of whatever you put into it: which is exactly how you reverse a list with one.
O(1). Top at index 0 would shift everything, O(n).
Linked list: top at the FRONT
void push(const Item &it) {
myList.prepend(it);
}
O(1). Top at the back would need a walk to find it, O(n).
Same ADT, two implementations, one design rule: put the action where the structure is fast.
Talk to your neighbor · TTYN
Implementing a stack with a linked list, where should the top be?
A. At the front, prepend and remove-first are both O(1)
B. At the back; that's where append is
C. Either; both are O(1)
D. In the middle, to balance the cost
✓ Answer
A. the front. Appending at the back is O(1) thanks to myLast, but removing the last node needs the node before it, which means walking the list: O(n). The front is fast in both directions.
The Queue: First In, First Out
add(item) // join the back
remove() // serve the front
peekFront()
isEmpty()
getSize()
front11 → 22 → 33back
Serve at the front, join at the back, a supermarket queue.
Also called First Come, First Served. Print jobs, request handling, breadth-first search, all queues.
The Obvious Array Queue Is Wrong
Front at index 0, back at mySize - 1. Adding is easy. Removing?
Every remove() shifts every remaining item: O(n). For a structure whose whole job is serving the front, that's a bad trade.
Don't Move the Data, Move the Ends
index[0] [1] [2] [3] [4]
data _ 22 33 44 _
head = 1 tail = 3
Keep two indices. remove() just moves head forward, no shifting, O(1).
…And Wrap Around the End
index[0] [1] [2] [3] [4]
data66 _ 33 44 55
head = 2 tail = 0 (wrapped)
tail = (tail + 1) % myCapacity; // advance with wraparound
head = (head + 1) % myCapacity;
The modulo turns the array into a circle. Both ends move; nothing is ever copied.
Talk to your neighbor · TTYN
With head == tail, is the circular queue empty or full?
A. Empty
B. Full
C. Ambiguous; you can't tell without more information
D. Impossible; they can never be equal
✓ Answer
C. you genuinely can't tell. Both an empty and a completely full queue put the two indices in the same place. The usual fixes: keep a separate mySize counter, or deliberately leave one slot empty so full and empty never look alike.
Circular Array: The Trade
Wins
Every operation O(1)
No shifting, ever
Almost no memory overhead
Costs
Fiddly index arithmetic
Full vs. empty needs care
Fixed capacity unless you grow it
A linked-list queue avoids the fiddliness, add at the tail, remove at the head, both O(1): at the cost of a pointer per item and a new on every insert.
Demo
Watching head and tail chase each other around.
(full and empty look identical. that is the whole bug.)
Push and pop at either end, all O(1). A deque can act as a stack or a queue, which is why the STL's stack and queue are built on one by default.
What If We Just Computed the Index?
A tree finds an item in O(lg n) by comparing. An array finds index i in O(1) by arithmetic.
So: turn the key itself into an index. No comparisons, no walking, one calculation and you're there.
That's a hash table.
A Hash Function
unsigned hash(const string &key, unsigned capacity) {
unsigned sum = 0;
for (char c : key) {
sum = sum * 31 + c; // mix the characters
}
return sum % capacity; // fold into the table
}
Deterministic: same key, same slot, every time
Fast: otherwise you've lost the advantage
Spreads out: keys should scatter across the table
The % capacity is what forces an unbounded key space into a fixed number of slots, and that is exactly why collisions are unavoidable.
Collisions
slot 0(empty)
slot 1"ada" → "bob"both hashed to 1
slot 2"grace"
Two keys, one slot. With 4 billion possible strings and 100 slots, this is not bad luck; it's arithmetic.
Chaining: each slot holds a linked list of everything that landed there
Open addressing: on a clash, probe forward for the next free slot
Talk to your neighbor · TTYN
With chaining, what is the worst case for find?
A. O(1): hashing is always constant
B. O(lg n), the chain is a tree
C. O(n), every key could hash to the same slot
D. O(n²)
✓ Answer
C. O(n). If every key collides, one chain holds everything and you're doing a linear search through a linked list. With a decent hash function it never happens, which is why we quote O(1) average: but the worst case is real.
Load Factor
load factor = items / slots
Low (say 0.5): short chains, fast lookups, memory sitting empty
High (say 5.0): memory well used, chains long, lookups slower
Most implementations rehash: double the table and redistribute: around 0.75
This is the time–space trade-off in its purest form: buy speed with empty slots. Rehashing is O(n), amortised across the inserts, exactly the doubling argument from week 5.
Where Hash Tables Sit
Operation
Hash table
Balanced tree
Sorted array
find
O(1) avg
O(lg n)
O(lg n)
insert
O(1) avg
O(lg n)
O(n)
remove
O(1) avg
O(lg n)
O(n)
sorted listing
O(n lg n)
O(n)
O(n)
worst case
O(n)
O(lg n)
O(lg n)
Fastest on average, and the only one with no sense of order. Every row of this table is a design decision you can now make on purpose.
Cost Summary
Structure
Add
Remove
Peek
Stack (array, top at end)
O(1)
O(1)
O(1)
Stack (list, top at front)
O(1)
O(1)
O(1)
Queue (naive array)
O(1)
O(n)
O(1)
Queue (circular array)
O(1)
O(1)
O(1)
Queue (linked list)
O(1)
O(1)
O(1)
One row is worse than the others, and it's the one you'd write first without thinking. That's the lesson.
Week 09 Recap
An ADT fixes the behavior and leaves the storage open
Stack = LIFO; Queue = FIFO
Put the action where the structure is fast: end of an array, front of a list
A naive array queue makes remove() O(n); a circular array fixes it
(i + 1) % capacity is the whole trick
head == tail is ambiguous, keep a size, or leave a gap
Next: a10 · a11 →
This deck stands on earlier CS112 materials by Joel Adams and Victor Norman · adapted and extended by Eric Araújo