Algorithms from zero
Lists, stacks, queues: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the unit stick.
Reconstruct the unit’s spine — why a linked list trades indexing for head insertion, how reversal and tortoise-and-hare manipulate pointers, why a stack and a queue are disciplines not structures, and why the monotonic stack is linear — without looking back at the lessons.
- 01Why is index access O(n) on a linked list but O(1) on an array, and what does the linked list gain in return?
- 02Walk through in-place reversal of a singly linked list. What is the one pointer move you must never skip, and what are the time and space costs?
- 03Explain the fast-and-slow (tortoise-and-hare) technique. Why must the pointers meet inside a cycle, and why exactly two steps for the fast pointer?
- 04A stack and a queue can both be backed by an array or a linked list. So what actually distinguishes them, and how do you choose between them for a problem?
- 05What is a deque, and why does dequeuing a FIFO queue with a naive array shift quietly destroy performance?
- 06Describe the monotonic stack and the next-greater-element pattern. Why is it O(n) despite having a loop inside a loop?
If you could reconstruct each answer from memory, you hold the unit’s spine: a linked list trades O(1) indexing for O(1) head insertion because scattering requires traversal; reversal and tortoise-and-hare are disciplined pointer dances where you save links before overwriting them; a stack and a queue are LIFO/FIFO disciplines you pick by required order, never dequeued with shift; and the monotonic stack turns an O(n^2) scan into O(n) by the push-once/pop-once invariant.