All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Doubly Linked Lists & Circular Lists

Doubly Linked Lists & Circular Lists

0/14 in this phase0/57 across the roadmap

📖 Concept

A doubly linked list has nodes with pointers to BOTH the next and previous nodes. This enables O(1) deletion of a given node and bidirectional traversal.

Structure:

null ← [10|←→] ⇄ [20|←→] ⇄ [30|←→] ⇄ [40] → null
         ↑ Head                              ↑ Tail

Advantages over singly linked lists:

  • O(1) deletion of any node (if you have a reference to it)
  • Bidirectional traversal — can go forward AND backward
  • O(1) tail operations with tail pointer
  • Used in: LRU Cache, browser history, text editors (undo/redo)

Circular Linked List: The last node points back to the first node (and in doubly, the first points back to last). Used in: round-robin scheduling, circular buffers, playlist loops.

Trade-offs:

  • More memory per node (extra prev pointer)
  • More complex insert/delete logic (update both prev and next)
  • But O(1) operations at both ends make it ideal for deques and caches

🏠 Real-world analogy: A doubly linked list is like a two-way street — you can drive in either direction. A singly linked list is a one-way street. A circular list is a roundabout — keeps going around.

💻 Code Example

codeTap to expand ⛶
1// DOUBLY LINKED LIST NODE
2class DLLNode {
3  constructor(val) {
4    this.val = val;
5    this.prev = null;
6    this.next = null;
7  }
8}
9

10// DOUBLY LINKED LIST — Full implementation
11class DoublyLinkedList {
12  constructor() {
13    // Sentinel nodes simplify edge cases
14    this.head = new DLLNode(null); // Dummy head
15    this.tail = new DLLNode(null); // Dummy tail
16    this.head.next = this.tail;
17    this.tail.prev = this.head;
18    this.size = 0;
19  }
20

21  // O(1) — Add to front
22  addFirst(val) {
23    const node = new DLLNode(val);
24    node.next = this.head.next;
25    node.prev = this.head;
26    this.head.next.prev = node;
27    this.head.next = node;
28    this.size++;
29  }
30

31  // O(1) — Add to back
32  addLast(val) {
33    const node = new DLLNode(val);
34    node.prev = this.tail.prev;
35    node.next = this.tail;
36    this.tail.prev.next = node;
37    this.tail.prev = node;
38    this.size++;
39  }
40

41  // O(1) — Remove specific node (given reference)
42  removeNode(node) {
43    node.prev.next = node.next;
44    node.next.prev = node.prev;
45    this.size--;
46    return node.val;
47  }
48

49  // O(1) — Remove from front
50  removeFirst() {
51    if (this.size === 0) return null;
52    return this.removeNode(this.head.next);
53  }
54

55  // O(1) — Remove from back
56  removeLast() {
57    if (this.size === 0) return null;
58    return this.removeNode(this.tail.prev);
59  }
60}
61

62// LRU CACHE — Classic interview problem using DLL + Hash Map
63class LRUCache {
64  constructor(capacity) {
65    this.capacity = capacity;
66    this.map = new Map(); // key → DLLNode
67    this.dll = new DoublyLinkedList();
68  }
69

70  get(key) {
71    if (!this.map.has(key)) return -1;
72    const node = this.map.get(key);
73    // Move to front (most recently used)
74    this.dll.removeNode(node);
75    this.dll.addFirst(node.val.value);
76    // Update map reference
77    this.map.set(key, this.dll.head.next);
78    this.dll.head.next.val = { key, value: node.val.value };
79    return node.val.value;
80  }
81

82  put(key, value) {
83    if (this.map.has(key)) {
84      this.dll.removeNode(this.map.get(key));
85    }
86    this.dll.addFirst({ key, value });
87    this.map.set(key, this.dll.head.next);
88    if (this.map.size > this.capacity) {
89      const last = this.dll.tail.prev;
90      this.dll.removeNode(last);
91      this.map.delete(last.val.key);
92    }
93  }
94}
95

96// TypeScript DLL Node
97class DLLNodeTS<T> {
98  val: T;
99  prev: DLLNodeTS<T> | null = null;
100  next: DLLNodeTS<T> | null = null;
101  constructor(val: T) { this.val = val; }
102}

🏋️ Practice Exercise

Practice Problems:

  1. Implement a doubly linked list with addFirst, addLast, removeFirst, removeLast
  2. Build an LRU Cache using a doubly linked list + hash map
  3. Implement a circular linked list and traverse it
  4. Flatten a multilevel doubly linked list
  5. Design a browser history (back/forward) using a doubly linked list
  6. Implement a deque (double-ended queue) using a doubly linked list
  7. Reverse a doubly linked list
  8. Find pairs in a sorted doubly linked list that sum to a target
  9. Convert a binary search tree to a sorted doubly linked list
  10. Implement an undo/redo system using a doubly linked list

⚠️ Common Mistakes

  • Forgetting to update BOTH prev and next pointers during insert/delete — leads to broken links

  • Not using sentinel/dummy nodes — makes head/tail edge cases much more complex

  • Memory leaks — not nullifying prev/next when removing nodes in languages with manual memory

  • Confusing node reference with node value — especially in LRU cache implementations

  • Not maintaining the size counter — off-by-one errors when checking empty/full

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Doubly Linked Lists & Circular Lists

← PreviousSingly Linked Lists — Build from ScratchNext →Stacks — Implementation & Applications