Doubly-Linked List

This file covers concepts unique to doubly-linked lists. For singly-linked list fundamentals (traversal, reversal, cycle detection, merge), see linked-list.md.

Core Concepts

Doubly-Linked List (DLL) — a linked list where each node holds prev and next pointers, enabling O(1) deletion and backward traversal when a node reference is held directly.

Sentinel nodes (dummy head/tail) — placeholder nodes at both ends that always exist, so every real node has non-null prev and next. Eliminates boundary edge cases in insert and delete.

Node reference as key — in DLL-backed structures (LRU Cache, etc.), holding a direct pointer to a node enables O(1) access and removal without traversal; this is the core advantage over arrays and singly-linked lists.

---

Structural Invariants

---

Internal Representation

Pointer-based (standard) — each node is an object with val, prev, next. Natural for dynamic insertion/deletion; no pre-allocation required.

Sentinel-augmented — dummy head and tail nodes always present; every real node sits between them. Preferred for interview problems because insert/delete code has no if-branches for boundary cases.

head.next = tail; tail.prev = head  # initial empty list with sentinels

Array-backed (rare) — prev/next index arrays instead of pointers. Appears in competitive programming when pointer overhead is forbidden or cache locality matters; never used in interviews.

---

Types / Variants

---

Traversals & Access Patterns

Forward traversal — cur = head; while cur: cur = cur.next. Identical to singly-linked list.

Backward traversal — cur = tail; while cur: cur = cur.prev. Only possible in DLL; used to process in reverse without extra storage.

Bidirectional scan — two pointers advancing from both ends toward the middle, or scanning forward then backward on the same list. Used in palindrome checks on a DLL without converting to array.

No O(1)-space Morris-style traversal exists for DLL; the prev pointer already provides backward access without stack/recursion.

---

Topic-Specific Operations

Insert after node — set new.prev = node, new.next = node.next, then node.next.prev = new, then node.next = new. Order matters: set outgoing pointers on new before updating neighbors, or node.next is lost.

Insert before node — when sentinels are present, delegate to "insert after node.prev"; identical four-pointer update.

Delete node — O(1) — node.prev.next = node.next; node.next.prev = node.prev. Two updates. With sentinels, no null-check needed. Without sentinels, guard node.prev and node.next for None.

Move node to front/back — delete (2 ops) then insert at sentinel head/tail (4 ops). Encapsulate as _remove(node) + _add_to_tail(node) helpers; LRU Cache calls this on every access.

---

Key Algorithms

LRU Cache (Hash Map + Sentinel DLL)

Map keys to DLL nodes; sentinel DLL keeps nodes ordered by recency (most-recent at tail, oldest at head). get moves the node to tail in O(1); put inserts at tail and evicts head.next when over capacity. Each node must store the key so eviction can remove the hash map entry. O(1) get/put, O(n) space.

Deque via Sentinel DLL

Push/pop from either end in O(1) by inserting/deleting at head.next or tail.prev. Python's collections.deque uses this internally; implement manually only when arbitrary-position splicing is needed.

Navigation History / Undo Stack

visit(url) inserts after the current cursor and truncates all forward nodes. back(k) / forward(k) moves the cursor k steps using prev/next. The O(1) truncate-forward (just update two pointers) is the DLL advantage over an array-based history.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Pointer update order in insert: setting node.next = new before capturing the original node.next loses that reference. Always set new.prev and new.next first, then update node.next.prev and node.next.
• Delete without sentinels: removing the head or tail requires null-checking node.prev and node.next. A sentinel DLL eliminates this entirely — prefer it for any interview implementation.
• Eviction without reverse lookup: the DLL node must store the key (not just the value) so that evicting head.next can also delete that key from the hash map. Storing only the value makes the eviction O(n).
• Move-to-tail vs duplicate insert: in LRU put, if the key already exists, update the value and move the existing node — never insert a second node for the same key.
• Circular DLL termination: when iterating a circular DLL, the stop condition is cur != head, not cur is not None; forgetting this causes an infinite loop.

---

Implementation Notes

• Python has no built-in DLL node class; define class Node with __init__(self, key=0, val=0, prev=None, next=None).
• collections.deque gives O(1) both-end ops but exposes no internal node pointers — use it when you don't need arbitrary-position splicing.
• Java's LinkedList is a DLL; addFirst/removeLast are O(1). LinkedHashMap (access-order mode) is a built-in LRU structure — mention it in interviews before reinventing.
• Track size as a counter field rather than calling len(hash_map) on every put; avoids any ambiguity about when the map is updated.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

LRU/LFU Cache

• LRU Cache (LC 146) — core hash map + sentinel DLL; the canonical DLL interview problem
• LFU Cache (LC 460) — extends LRU with frequency buckets; each bucket is its own sentinel DLL

Navigation / Design

• Design Browser History (LC 1472) — DLL cursor, truncate forward on new visit
• Design Linked List (LC 707) — implement singly or doubly; doubly is cleaner for deleteAtIndex

Structural Manipulation

• Flatten a Multilevel Doubly Linked List (LC 430) — DFS/stack to splice child lists inline; tests pointer-update correctness under nesting

Clarification Questions to Ask

• Is the list circular or null-terminated?
• Should sentinel (dummy) nodes be used internally, or must the external API expose a plain node?
• For cache problems: what is the eviction policy (LRU, LFU, FIFO)? Is capacity fixed?
• Is thread safety required? (If yes, state you'd wrap ops with a lock — don't implement full concurrency in an interview.)

Common Interview Mistakes

• Updating node.next before saving the reference to the original node.next, causing pointer loss during insert.
• Evicting a node from the DLL without removing its key from the hash map, leaving stale entries.
• Storing only the value in DLL nodes, making reverse lookup during eviction impossible without O(n) scan.
• Implementing LRU with a Python OrderedDict when asked to design the data structure from scratch — always confirm whether library structures are permitted.

Typical Follow-Up Escalations

• "Make it thread-safe" → wrap get and put with threading.Lock; explain that the lock scope covers the full operation, not individual pointer updates.
• "Now support O(1) get-minimum in addition to LRU" → augment each node with a running min, or maintain a parallel min-stack alongside the DLL.
• "Implement LFU instead of LRU" → two-level structure: freq → sentinel DLL of nodes at that frequency; maintain min_freq to find the eviction bucket in O(1).