Doubly & Circular Linked Lists with Sentinel/Dummy Nodes0%
Fast & Slow Pointers: Floyd's Cycle Detection & Middle Node Finding

Doubly & Circular Linked Lists with Sentinel/Dummy Nodes

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Doubly & Circular Linked Lists with Sentinel/Dummy Nodes

While Singly Linked Lists only allow unidirectional forward traversal, advanced system architectures (like LRU Caches and OS process schedulers) require bidirectional navigation and circular loops. Doubly Linked Lists provide both prev and next pointers, while Sentinel (Dummy) Nodes eliminate treacherous null-pointer edge cases.

1. Real-World Analogy: Train Carriages & Playlists

  • Doubly Linked List (Train Carriages): Each train car is physically hooked to both the car in front (Prev) and the car behind (Next). A conductor can walk forward or backward between cars freely.
  • Circular Linked List (Music Playlist on "Repeat"): When the last song (Tail) finishes, its next pointer loops straight back to the first song (Head), creating an endless seamless cycle.

2. Why Sentinel (Dummy) Nodes Are an Industry Standard

When modifying linked lists (inserting/deleting), handling deletions at the absolute head or tail usually requires verbose, bug-prone if (head == null) checks.

A Sentinel / Dummy Node is an empty placeholder node that permanently anchors the beginning and end of the list:

Output
[Dummy Head] <---> [Node 10] <---> [Node 20] <---> [Dummy Tail]

With dummy nodes:

  • The list is never empty (always contains at least Head and Tail sentinels).
  • Every real data node always has both a valid previous and next neighbor.
  • Edge cases for empty lists, single-node lists, and boundary deletions disappear completely!

3. Designing a Doubly Linked List Node

Python
class DoublyNode:
def __init__(self, val: int = 0):
self.val = val
self.prev: 'DoublyNode' = None
self.next: 'DoublyNode' = None

Removing a Node in $O(1)$ Time Given its Reference:

In a singly linked list, deleting a node requires $O(n)$ traversal to find its predecessor. In a doubly linked list, because the node knows its own prev, deletion is an instant $O(1)$ pointer splice:

Python
def remove_node(node: DoublyNode) -> None:
# Splice out 'node' by connecting its neighbors to each other
node.prev.next = node.next
node.next.prev = node.prev

4. Multi-Language Implementations: Doubly Linked List with Sentinels

Python 3:

Python
class DoublyLinkedList:
def __init__(self):
self.head = DoublyNode(0) # Dummy Head
self.tail = DoublyNode(0) # Dummy Tail
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
 
def add_to_front(self, val: int) -> None:
new_node = DoublyNode(val)
# Connect new_node between dummy head and head.next
new_node.next = self.head.next
new_node.prev = self.head
self.head.next.prev = new_node
self.head.next = new_node
self.size += 1
 
def remove_last(self) -> int:
if self.size == 0:
return -1
last_real_node = self.tail.prev
last_real_node.prev.next = self.tail
self.tail.prev = last_real_node.prev
self.size -= 1
return last_real_node.val

Modern JavaScript / TypeScript:

TypeScript
export class DNode {
val: number;
prev: DNode | null = null;
next: DNode | null = null;
constructor(val: number = 0) {
this.val = val;
}
}
 
export class DoublyLinkedList {
private head: DNode;
private tail: DNode;
public size: number = 0;
 
constructor() {
this.head = new DNode(0);
this.tail = new DNode(0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
 
public addToFront(val: number): void {
const node = new DNode(val);
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
this.size++;
}
 
public removeLast(): number {
if (this.size === 0) return -1;
const toRemove = this.tail.prev!;
toRemove.prev!.next = this.tail;
this.tail.prev = toRemove.prev;
this.size--;
return toRemove.val;
}
}

5. Circular Linked Lists

In a Circular Singly Linked List, the tail node points back to head instead of null:

Output
[Node 1] -> [Node 2] -> [Node 3] -+
^ |
+------------------------------+
  • Traversal Guard: Loops cannot use while curr != null. You must check while curr.next != head to prevent infinite loops!
  • Top Applications: Round-robin CPU time-slice scheduling, multiplayer turn-based board games.
Interactive Quiz

Multiple Choice Questions

Question 1
What additional field does a Doubly Linked List node contain compared to a Singly Linked List node?
Question 2
How does a Sentinel (Dummy) node improve linked list code quality?
Question 3
What is the time complexity of deleting a node from a Doubly Linked List when you already have a direct pointer reference to that node?
Question 4
What is the defining characteristic of a Circular Linked List?
Question 5
In an LRU (Least Recently Used) Cache design, why is a Doubly Linked List paired with a Hash Map?
Next Lesson

Fast & Slow Pointers: Floyd's Cycle Detection & Middle Node Finding

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Singly Linked Lists: Node Architecture, Traversal & In-Place ReversalFast & Slow Pointers: Floyd's Cycle Detection & Middle Node Finding

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext