Unit 3 · Moderate
Structures defined by a restriction. The restriction is what makes each one fit a specific class of problem, so recognising the fit is the skill rather than the implementation.
What a strong answer looks like
A strong Unit 3 answer names the access discipline and explains why the problem needs exactly that discipline.
Know
Last in, first out. The discipline matches nesting, backtracking, undo, and expression evaluation because the most recent unfinished thing is always the one to resolve.
Apply
Reach for a stack when the problem involves matching pairs or reversing recent work.
Watch out
Indexing into a stack, which discards the guarantee that made it appropriate.
Study move
Use a stack to validate nested brackets and state both failure conditions.
Know
First in, first out, which matches fairness and level-by-level exploration. A deque relaxes the restriction at both ends.
Apply
Use a queue for breadth-first work and a deque when a sliding-window maximum is needed.
Watch out
Choosing a stack where a queue was needed, which silently changes a breadth-first traversal into a depth-first one.
Study move
Describe how a graph traversal changes when a stack replaces the queue.
Know
No indexing: position k costs k steps. Insertion and deletion are constant once positioned, which is the whole trade.
Apply
Draw the nodes and order the reassignments so no needed reference is dropped.
Watch out
Detaching before attaching, which loses the remainder of the list.
Study move
Reverse a linked list iteratively and name the three references you must hold.
Know
Fast and slow pointers detect cycles and find midpoints in one pass without extra memory.
Apply
Advance one pointer twice as fast as the other, and reason about when they meet.
Watch out
Failing to check the fast pointer and its successor before advancing, which dereferences null.
Study move
Detect a cycle with two pointers and explain why they must meet if one exists.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Find the middle node of a singly linked list in one pass without counting its length first, and justify the approach.
