Doubly Linked List — Full Implementation & 6 Scenario Problems

In a naive doubly linked list where head_ and tail_ are raw pointers directly pointing to data nodes (or nullptr), any insertion or deletion requires multiple branches:

// NAIVE FRAGILE CODE:
if (node == head) { head = node->next; if (head) head->prev = nullptr; }
else { node->prev->next = node->next; }
if (node == tail) { tail = node->prev; if (tail) tail->next = nullptr; }
else { node->next->prev = node->prev; }

This is notoriously prone to off-by-one errors and segmentation faults when lists become empty. By allocating two sentinel dummy nodes (head_ and tail_), every real node is guaranteed to have both a valid prev and a valid next. Unlinking a node collapses into two unconditional pointer writes:

node->prev->next = node->next;
node->next->prev = node->prev;

Not a single if statement is needed, eliminating 100% of boundary condition edge-case bugs.

When inserting a newNode before an existing position node pos, four pointers must be rewired. The order of assignment is critical to avoid losing access to the neighbor nodes:

1. newNode->prev = pos->prev; (wire backward to predecessor)
2. newNode->next = pos; (wire forward to successor)
3. newNode->prev->next = newNode; (rewire predecessor's forward link)
4. pos->prev = newNode; (rewire successor's back link)

If you execute step 4 before step 1, pos->prev is overwritten with newNode, meaning you can no longer reach the original predecessor without an extra temporary variable!

A classic interview trap is asking you to remove elements matching a predicate while iterating through a linked list. If you write:

// BUG: Use-After-Free!
for (Node* curr = list.first(); curr != list.end(); curr = curr->next) {
    if (curr->data % 2 == 0) deleteNode(curr); // curr is destroyed; curr->next is garbage!
}

The moment deleteNode(curr) deallocates memory, curr->next dereferences freed memory (heap corruption / segfault). The production solution is designing erase(Node* curr) to return curr->next:

Node* curr = list.firstNode();
while (curr != list.endNode()) {
    if (curr->data % 2 == 0) {
        curr = list.erase(curr); // Returns curr->next directly!
    } else {
        curr = curr->next;
    }
}

In an LRU Cache (Least Recently Used), accessing a key requires promoting its corresponding node to the front of the list. A naive implementation destroys the old node and creates a new one (erase + push_front), calling operator new and operator delete on every single cache hit! In high-frequency trading or database caches, this causes catastrophic heap fragmentation and latency spikes.

A senior candidate implements moveToFront(Node*) in O(1) with zero allocations by unlinking the existing node from its current position and rewiring it immediately after head_. The node's memory address never changes, ensuring external pointers or hash map iterator values remain 100% valid.

To reverse a doubly linked list in-place, traverse every node from head_ to tail_ and swap curr->prev with curr->next. Finally, swap head_ and tail_. Because both directional links are swapped in a single pass, the list is completely inverted in O(N) time and O(1) auxiliary space.

In Scenario 4 (Corrupted Pointer Repair), interviewers present a DLL where forward next pointers are intact, but one or more back-pointers prev were corrupted by buggy concurrent code or serialization. We can traverse forward via next and verify curr->next->prev == curr. If a discrepancy is found, restoring curr->next->prev = curr heals the list in O(N) time with zero extra space.

In Scenario 5, two doubly linked lists can be concatenated in O(1) time by taking other's entire range [other.head_->next, other.tail_->prev] and splicing it directly before this->tail_, then setting other to empty.

In Scenario 6 (Concurrency Trap), interviewers ask: "Can we use fine-grained per-node mutexes (std::mutex mtx_ inside each Node) to allow concurrent reads and writes?" The answer is a resounding NO without global lock ordering. If Thread A traverses forward (locking Node1 then Node2) while Thread B traverses backward (locking Node2 then Node1), the threads will lock-order invert and deadlock! Concurrent linked lists require coarse-grained list locks, reader-writer locks (std::shared_mutex), or complex lock-free hazard-pointer schemes.