Data Structures and Algorithms Deep‑Dive — Doubly and Circular Linked Lists (Chapter 2, Episode 4)

Episode goals:

• Understand what a prev pointer buys you and exactly which operations it unlocks
• Implement a doubly linked list with sentinel head and tail nodes, eliminating all edge cases
• Implement singly and doubly circular linked lists with correct traversal termination
• Analyse the full operation cost table across all three variants
• See where each variant is actually used in production: LRU cache, deque, round-robin scheduler

1) The Limitation That Motivates This Episode

Episode 3 ended with a table showing that singly linked lists cannot delete or insert before a given node in O(1). The reason: you need the predecessor, and finding it requires O(n) traversal from the head.

The fix is direct: store the predecessor explicitly. Every node gets a prev pointer in addition to next. This doubles the pointer overhead per node but unlocks O(1) deletion and O(1) insert-before given any node pointer — no traversal needed.

Circular linked lists solve a different problem: they remove the null terminator, making the last node point back to the first (and in a doubly circular list, the first’s prev points to the last). This creates a ring used in round-robin schedulers, music playlist loops, and the Josephus problem.

2) Doubly Linked List — Node Structure

Node:
  data  — the value stored
  prev  — pointer to the previous node (or null if head)
  next  — pointer to the next node (or null if tail)

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

template<typename T>
struct Node {
    T data;
    Node* prev;
    Node* next;
    Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};

Memory layout — four nodes [3 ↔ 7 ↔ 1 ↔ 9]:

null ← [3|prev|next] ↔ [7|prev|next] ↔ [1|prev|next] ↔ [9|prev|next] → null

Each node consumes three fields: one for data, two for pointers. In a 64-bit system with 8-byte pointers, each pointer field costs 8 bytes — the pointer overhead is 16 bytes per node regardless of data size, compared to 8 bytes for a singly linked list node.

3) The Two-Sentinel Pattern

Episode 3 introduced the single dummy head. For doubly linked lists, extend this to two sentinels: a permanent dummy head before all real nodes and a permanent dummy tail after all real nodes.

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None)   # sentinel head
        self.tail = Node(None)   # sentinel tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0

Initial state:

head(sentinel) ↔ tail(sentinel)

After inserting 3, 7, 1:

head ↔ [3] ↔ [7] ↔ [1] ↔ tail

Why two sentinels? Every real node now has both a predecessor and a successor — always. Insert and delete code never checks for null predecessor or null successor. The boundary conditions disappear entirely:

• Insert before the first real node: insert between head and head.next.
• Insert after the last real node: insert between tail.prev and tail.
• Delete the first real node: same code as deleting any middle node.
• Delete the last real node: same code as deleting any middle node.

One insertion function and one deletion function handle every case with no conditionals.

4) Core Operations

Insert Between Two Adjacent Nodes — O(1)

The fundamental primitive. All other insertions reduce to this.

InsertBetween(prev_node, next_node, val):
  new_node           ← new Node(val)
  new_node.prev      ← prev_node
  new_node.next      ← next_node
  prev_node.next     ← new_node
  next_node.prev     ← new_node

Pointer update order matters. Set new_node.prev and new_node.next first (before breaking any existing link). Then update prev_node.next and next_node.prev. Any order of the last two is fine since new_node is already correctly wired.

Insert at head (before first real node):

InsertAtHead(list, val):
  InsertBetween(list.head, list.head.next, val)
  list._size += 1

Insert at tail (after last real node):

InsertAtTail(list, val):
  InsertBetween(list.tail.prev, list.tail, val)
  list._size += 1

Both are O(1) — the two-sentinel pattern makes them identical in structure.

Delete a Given Node — O(1)

DeleteNode(node):
  node.prev.next ← node.next
  node.next.prev ← node.prev
  // node is now unreachable; memory freed by GC or explicit delete

Two pointer assignments. That is the entire operation. No traversal, no special cases, no predecessor search.

This is the key advantage of doubly linked lists: if you have a pointer to a node, you can delete it in O(1). The singly linked list required O(n) to find the predecessor; the doubly linked list stores it directly.

Full Python implementation:

def delete_node(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev
    self._size -= 1

def insert_between(self, prev_node, next_node, val):
    new_node = Node(val)
    new_node.prev = prev_node
    new_node.next = next_node
    prev_node.next = new_node
    next_node.prev = new_node
    self._size += 1

def insert_at_head(self, val):
    self.insert_between(self.head, self.head.next, val)

def insert_at_tail(self, val):
    self.insert_between(self.tail.prev, self.tail, val)

5) Full Operation Comparison — All Three Variants

Operation Singly LL Doubly LL Notes Access by index O(n) O(n) No random access in either Search O(n) O(n) Linear scan in both Insert at head O(1) O(1) Both fast Insert at tail O(1) with tail ptr O(1) Both fast with sentinel/tail ptr Insert at position i O(n) O(n) Traversal dominates Insert before given node O(n) O(1) Key doubly LL advantage Delete at head O(1) O(1) Both fast Delete given node O(n) O(1) Key doubly LL advantage Traverse forward O(n) O(n) Both identical Traverse backward O(n²) or impossible O(n) Doubly LL has prev Memory per node data + 1 ptr data + 2 ptrs Doubly costs 8 extra bytes/node

The two O(1) entries in bold — delete given node, insert before given node — are the entire justification for doubly linked lists. Everything else is the same or worse.

6) Singly Circular Linked List

In a circular singly linked list, the last node’s next points back to the first node instead of null. There is no null terminator.

[3] → [7] → [1] → [9] → (back to [3])
 ↑__________________________________|

Representation: maintain a pointer to the tail (not head). The head is then tail.next. This makes both head insertion and tail insertion O(1):

• Insert at tail: new node’s next = tail.next, tail.next = new node, update tail = new node.
• Insert at head: new node’s next = tail.next, tail.next = new node. (Tail unchanged.)

Traversal — termination condition:

TraverseCircular(list):
  if list.tail = null: return   // empty
  current ← list.tail.next     // start at head
  repeat:
    visit(current.data)
    current ← current.next
  until current = list.tail.next  // back at head

Critical: the termination condition is current = starting_node, not current ≠ null. Forgetting this causes an infinite loop — the most common circular list bug.

Where it is used:

• Round-robin schedulers: cycle through processes/threads indefinitely.
• Circular buffers (ring buffers) for producer-consumer queues.
• Token ring networks.

7) Doubly Circular Linked List

Every node has prev and next; the last node's next points to the first, and the first node's prev points to the last.

[3] ↔ [7] ↔ [1] ↔ [9]
 ↑_________________________↓

With a sentinel node, the sentinel’s next points to the first real node and sentinel.prev points to the last real node — the ring is complete and contains exactly one sentinel:

sentinel ↔ [3] ↔ [7] ↔ [1] ↔ [9] ↔ (back to sentinel)

Operations: identical to the non-circular doubly linked list, except:

• Termination condition for traversal: current ≠ sentinel (not current ≠ null).
• No null checks anywhere — the ring is always complete.

Where it is used:

• The Linux kernel’s list_head structure — a doubly circular linked list embedded inside every kernel data structure that can be part of a list.
• Python’s collections.deque — implemented internally as a doubly linked list of fixed-size array blocks.
• LRU cache (see §8 below) — the most important production use case.

8) Production Application — LRU Cache

An LRU (Least Recently Used) cache evicts the least recently used item when capacity is reached. It must support:

• get(key) — O(1): return value if present, mark as recently used.
• put(key, value) — O(1): insert or update; evict LRU item if at capacity.

Data structure: doubly linked list + hash map.

• Doubly linked list: maintains access order. Most recently used at head, least recently used at tail. O(1) move-to-head given a node pointer; O(1) remove-from-tail.
• Hash map: maps keys to node pointers. O(1) lookup to find the node without traversal.

get(key):
  if key not in map: return -1
  move map[key] node to head of list   // O(1) with prev pointer
  return map[key].value

put(key, value):
  if key in map:
    map[key].value ← value
    move map[key] node to head         // O(1)
  else:
    create new node at head            // O(1)
    map[key] ← new node
    if size > capacity:
      evict tail.prev node             // O(1) with sentinel tail
      delete from map

Every operation is O(1) because:

• The hash map gives O(1) node lookup.
• The doubly linked list gives O(1) node deletion (given pointer) and O(1) head insertion.

Without the prev pointer, "move to head" requires O(n) traversal to find the predecessor for deletion. The doubly linked list is not optional here — it is the reason the LRU cache works.

This pattern (doubly linked list + hash map) appears in:

• Browser history (back/forward navigation).
• Database buffer pool management.
• Operating system page replacement.
• CDN cache eviction policies.

9) Common Pitfalls

• Incorrect pointer update order in insertion. Wire the new node (new_node.prev and new_node.next) before touching the existing nodes' pointers. Breaking an existing link before saving it loses the reference permanently.
• Forgetting to update prev on deletion. node.prev.next = node.next is necessary but not sufficient — node.next.prev = node.prev must also be set, or the backward traversal breaks silently.
• Infinite loop in circular list traversal. The termination condition is current == start, not current == null. Missing this is the most common circular list bug.
• Double-freeing in C++. After DeleteNode(node), the node's prev and next pointers still point into the list. If node is accessed or deleted again, undefined behaviour results. Null out node.prev and node.next after deletion and delete node exactly once.
• Confusing the sentinel with a real node. Never call visit(sentinel.data) during traversal. The termination condition must exclude the sentinel — for doubly circular with one sentinel, stop when current == sentinel, not after.

10) Practice Exercises

Level A — Fundamentals:

1. Draw the pointer diagram for a doubly linked list [3 ↔ 7 ↔ 1] with two sentinels. Show the pointer state after deleting the node holding 7 — which pointers change and in what order?
2. What is the termination condition for forward traversal of a singly circular list starting from tail.next? What goes wrong if you use current ≠ null instead?
3. In the two-sentinel doubly linked list, how do you check if the list is empty in O(1)?

Level B — Implementation: 4. Implement MoveToFront(list, node) for a doubly linked list: remove node from its current position and insert it at the head. Use DeleteNode and InsertBetween as primitives. What is the time complexity? 5. Implement a doubly linked list Reverse(list) in-place: reverse the order of all real nodes by swapping prev and next pointers. Do not swap data values. What is the time complexity? 6. Implement a doubly circular linked list with one sentinel. Write insert_after(node, val) and delete_node(node) and verify your traversal terminates correctly.

Level C — Applied Problems: 7. Implement a full LRU cache with get and put operations in O(1) using a doubly linked list and a hash map. Handle: key already exists in put (update value and move to head), capacity = 1, get on a missing key. 8. Josephus Problem: n people stand in a circle. Starting from person 1, every k-th person is eliminated until one remains. Model this with a singly circular linked list and simulate the elimination. What is the time complexity of the simulation? 9. Design a data structure supporting: push_front, push_back, pop_front, pop_back, and peek_front, peek_back — all in O(1). Which linked list variant is required? Why can't a singly linked list do this?

Hints:

• For 3: head.next == tail (the two sentinels are directly adjacent, no real nodes between them).
• For 7: on put when the key exists, update the value, call MoveToFront, no eviction. On put when the key is new, insert at head, add to map, then if over capacity, remove tail.prev from list and from map.
• For 9: doubly linked list required. pop_front needs head.next.next's prev updated — requires prev pointer. Singly linked list cannot pop_back in O(1) because it cannot find the new tail's predecessor.

11) Summary and What’s Next

In this episode, you learned:

• The prev pointer unlocks O(1) delete-given-node and O(1) insert-before-given-node — the two operations singly linked lists cannot do without O(n) traversal
• The two-sentinel pattern (dummy head + dummy tail) eliminates all boundary conditions; every real node always has a predecessor and successor
• InsertBetween and DeleteNode are the two fundamental doubly linked list primitives — all other operations compose from them
• Circular linked lists replace null terminators with a ring; traversal terminates at the starting node, not at null
• The LRU cache is the canonical production application: doubly linked list for O(1) move-to-head and O(1) eviction, hash map for O(1) lookup

Next episode (Chapter 2, Episode 5): Advanced Linked List Operations.

Reversing a linked list iteratively and recursively, detecting and breaking cycles (Floyd’s algorithm formally proved), merging and partitioning lists — the operations that appear most frequently in interview problems and in the implementation of higher-level data structures.

12) Further Reading

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), Chapter 10.2 (Linked Lists)
• Knuth — The Art of Computer Programming, Vol. 1, Section 2.2.4 (Circular Lists)
• Linux kernel source — include/linux/list.h — the real-world doubly circular linked list used in the kernel

Appendix: Reference Implementations

Python — Full doubly linked list with two sentinels:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node()   # sentinel head
        self.tail = Node()   # sentinel tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0

    def _insert_between(self, prev_node, next_node, val):
        node = Node(val)
        node.prev, node.next = prev_node, next_node
        prev_node.next = next_node.prev = node
        self._size += 1
        return node

    def _delete_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1

    def insert_at_head(self, val):
        return self._insert_between(self.head, self.head.next, val)

    def insert_at_tail(self, val):
        return self._insert_between(self.tail.prev, self.tail, val)

    def delete_node(self, node):
        self._delete_node(node)

    def move_to_front(self, node):
        self._delete_node(node)
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self._size += 1

    def is_empty(self):
        return self.head.next is self.tail

    def to_list(self):
        result, cur = [], self.head.next
        while cur is not self.tail:
            result.append(cur.data)
            cur = cur.next
        return result

Python — LRU Cache:

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}            # key → node
        self.dll = DoublyLinkedList()

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        self.dll.move_to_front(self.map[key])
        return self.map[key].data[1]   # node stores (key, value)

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.map[key].data = (key, value)
            self.dll.move_to_front(self.map[key])
        else:
            node = self.dll.insert_at_head((key, value))
            self.map[key] = node
            if len(self.map) > self.cap:
                lru = self.dll.tail.prev   # least recently used
                self.dll.delete_node(lru)
                del self.map[lru.data[0]]

C++ — Doubly circular list with one sentinel:

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val = 0) : data(val), prev(this), next(this) {}
};

void insert_after(Node* pos, int val) {
    Node* node = new Node(val);
    node->next = pos->next;
    node->prev = pos;
    pos->next->prev = node;
    pos->next = node;
}

void delete_node(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node;
}

// Traverse: stop when back at sentinel
void traverse(Node* sentinel) {
    for (Node* cur = sentinel->next; cur != sentinel; cur = cur->next)
        std::cout << cur->data << " ";
}