Question 1

What is a doubly linked list and how does it differ from a singly one?

Accepted Answer

State the difference in one sentence, then list the gain and the cost separately — that balance is what interviewers want. Difference: each node stores a prev reference in addition to next. Gain: O(1) deletion of a node you hold (in a singly list it's O(n), since you must find the predecessor) Backward traversal — browser history, undo-redo, text cursors Together with a tail, O(1) insert/remove at both ends, i.e. natural deque behaviour Cost: An extra pointer per node — memory; with small values the metadata can exceed the payload Keeping two references in sync on every operation — easy to get wrong, and the bug is silent End with a practical example: "An LRU cache specifically requires a doubly list, because I have to unlink the node the hash map gave me in O(1) — you can't do that with a singly list." That one sentence turns the answer from a description into demonstrated understanding.

Question 2

How would you implement an LRU cache?

Accepted Answer

This is the most-asked application question for doubly linked lists. Build the answer in four steps. 1. Clarify the requirement: both get and put must be O(1); when capacity is full the least recently used entry is evicted. 2. Why one structure isn't enough: a hash map gives O(1) lookup but keeps no order. A list keeps order but lookup by key is O(n). So you combine them. 3. The design: HashMap<Key, Node> plus a doubly linked list. The front of the list is the most recently used, the back the oldest. get(key): find the node via the map (O(1)), unlink it (O(1), thanks to prev), move it to the front, return the value put(key, value): if present, update the value and move to the front; if new, create the node, push it to the front and record it in the map; if over capacity, unlink tail.prev and delete it from the map too 4. Details — these set you apart: two sentinel nodes (head and tail) remove every null special case; the node must store its key as well as its value so you can delete from the map; and handle capacity = 0. Finish with: "In a real project I'd use something ready-made — LinkedHashMap with accessOrder = true in Java, LruCache on Kotlin/Android. But an interview expects the hand-written version." That signals practical maturity. If a thread-safe variant is requested, note that it needs a lock or a concurrent structure.

Question 3

Where are circular linked lists used and what is their pitfall?

Accepted Answer

First describe the structure in one sentence: the last node points back to the head instead of null; in a doubly circular list head.prev points at the tail. Real uses — concrete examples land far better than a description: Round-robin scheduling — giving processes their turn in an OS; current = current.next and you never reach an end Media playlists / carousels — "repeat all" comes for free Turn order in games — players around a table cycle through turns Circular buffer logic — fixed-size logs or sensor data Classic algorithmic problems like Josephus The main pitfall: traversal doesn't stop on its own. while (cur != null) is an infinite loop, because no next is ever null. The stop condition must test for returning to the start: do { ... } while (cur !== start). For the same reason toString, computing the length, even inspecting the object in a debugger all need care. A second pitfall: the single-node case on deletion — node.next === node — must be handled separately or the structure corrupts. State the upside too: with no null anywhere there are fewer edge cases, and every node gives access to the whole list — which sometimes makes the code simpler than the singly version.

Question 4

How would you design undo/redo functionality?

Accepted Answer

Present two approaches and justify your pick — that's what design questions reward. Approach 1 — two stacks: an undoStack and a redoStack. A new action: push onto undoStack and clear redoStack. Undo: pop from undoStack, apply it, push onto redoStack. Redo: the reverse. Simple, O(1), and enough for most cases. Approach 2 — a doubly linked list: each node is a state or an action; a current pointer marks where you are. Undo is current = current.prev, redo is current = current.next, and a new action truncates the chain after current. This is the same model as browser history. When the second is better: when the history must be shown to the user as a list (a Photoshop-style history panel), or when jumping to an arbitrary point is required. With two stacks that takes extra work. Practical details — the part that lifts the answer to production level: The command pattern: store each action as an object with execute() and undo() — far more memory-efficient than snapshotting full state A memory cap: bound the history size and drop old steps (again, a doubly list gives O(1) removal from the back) Grouping: coalescing consecutive typed characters into one undo step — that's what users expect For large states: store deltas rather than full snapshots Wrap up: "For a simple app I'd take two stacks; if the history is visible or must be navigable to any point, I'd move to a doubly linked list."

Question 5

What mistakes happen when deleting a node from a doubly linked list, and how do you prevent them?

Accepted Answer

This question probes attention to detail and production experience. Answer it as mistake → consequence → prevention. Mistake 1 — updating only one reference. Update prev.next and forget next.prev, and the list is correct forwards but corrupt backwards. Consequence: silent corruption that surfaces much later as odd behaviour. Prevention: put deletion in a single private method (unlink(node)) and call it everywhere — the two lines never get separated. Mistake 2 — forgetting the edge cases. When the head or tail is removed, node.prev or node.next is null and you get a null dereference. Prevention: sentinel nodes — with empty head and tail nodes every real node always has neighbours and the conditionals disappear entirely. Mistake 3 — not updating metadata. size isn't decremented, head/tail still point at the removed node. Prevention: update everything inside the same method, and assert the invariants in tests. Mistake 4 — not clearing the removed node's references. If node.prev and node.next still point into the list and something outside still holds the node, the whole list can stay alive and escape the GC. Prevention: after unlinking, set node.prev = node.next = null. Mistake 5 — deleting during traversal. If you don't save next before unlinking, the traversal breaks. Close with practices: write tests that check the invariants (forward and backward traversal must produce the same sequence, size must equal the real node count); and prefer a library structure where possible — a hand-rolled linked list rarely earns its place in production code.

Operation	Singly	Doubly	Comment
Insert/remove at head	O(1)	O(1)	Cheap in both
Insert at tail (with a tail pointer)	O(1)	O(1)	—
Remove from tail	O(n)	O(1)	Doubly wins because it has `prev`
Delete a given node	O(n)	O(1)	This is the whole basis of an LRU cache
Backward traversal	Not possible (or O(n) extra work)	O(n)	Essential for browser history
Memory (per node)	1 pointer	2 pointers	Doubly costs roughly 1.5-2x metadata
Risk of bugs	Lower	Higher — two references must stay in sync	Forgetting `prev` on deletion is the classic bug

Doubly and Circular Linked List

📚 Sources and documentation