Study notes · 9% of the exam

Linked Lists, Stacks and Queues

Linked lists, stacks, queues and deques: know their costs, the pointer patterns interviewers love (reversal, fast/slow, dummy nodes) and the monotonic stack/deque tricks that turn O(n²) scans into O(n).

Key points

1
Linked lists give O(1) insert/delete at a known node but O(n) indexing; a singly linked list cannot remove its tail in O(1) even with a tail pointer.
2
Use a dummy (sentinel) node so head insertions and deletions need no special case, and save next before rewiring a pointer.
3
Fast/slow pointers find the middle (loop condition decides which middle on even lengths), detect cycles in O(1) space, and with a head reset find the cycle start.
4
In Python, use list.append/pop() for stacks and collections.deque for queues; list.pop(0) is O(n).
5
Monotonic stacks answer next-greater/next-smaller and histogram problems in O(n); monotonic deques give sliding-window maximum in O(n).
6
Two stacks make a queue with O(1) amortized operations, but transfer only when the out-stack is empty.
7
An LRU cache is a hash map plus a doubly linked list (or OrderedDict with move_to_end and popitem(last=False)).

Common traps

Overwriting curr.next before saving it loses the rest of the list during reversal.
Recursive reversal is O(n) stack space and fails on long lists in CPython (default recursion limit 1000).
With duplicates, monotonic-stack counting needs asymmetric comparisons (one side strict, the other not) to avoid under- or double-counting.

Read the source

Test yourself on Linked Lists, Stacks and Queues

Ten questions, with the answer and explanation after each one.