Linked Lists, Stacks, Caches, And Pointer Techniques

What's being tested

These problems test data-structure design with strict operation-level complexity targets: usually O(1) or O(log n) for get, put, push, pop, peekMax, and removal. Interviewers are probing pointer discipline, reference equality, cache eviction invariants, and whether you can combine structures like hash maps, doubly linked lists, stacks, heaps, and balanced trees cleanly.

Patterns & templates

• LRU cache = HashMap<key, Node> + doubly linked list; get and put move nodes to front in O(1).

• Pointer-safe list operations need helpers like remove(node), insertFront(node), and sentinel head / tail nodes to avoid null-heavy edge cases.

• Linked-list intersection uses two pointers switching heads: a = a ? a.next : headB; detects shared node by reference in O(m+n) time, O(1) space.

• Max stack variants trade off operations: two stacks give getMax() in O(1), but popMax() may require O(n) temporary movement.

• Efficient popMax() usually combines a doubly linked list for stack order with TreeMap<Integer, Stack<Node>> for max lookup/removal in O(log n).

• LFU/cache follow-ups require frequency buckets plus recency ordering; track minFreq, key-to-node map, and freq-to-ordered-nodes map.

• Thread-safety follow-up: protect cache mutations with a lock; mention coarse-grained locking first, then ReadWriteLock or sharding if contention matters.

Common pitfalls

Pitfall: Comparing linked-list node values instead of node references for intersection; intersection means the exact same object, not equal data.

Pitfall: Claiming O(1) max removal from a heap without explaining lazy deletion or node handles; standard heaps do not remove arbitrary elements in O(1).

Pitfall: Forgetting to update both structures on every mutation: cache map and linked list, or max index and stack order.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.