Loading learning content...
Now that we understand the fundamental concept of circular linked lists—structures that form closed loops instead of terminating at null—we face an important design decision. Just as standard linked lists come in singly and doubly linked variants, circular linked lists offer the same choice:
Singly Circular Linked List — Each node has one pointer (to the next node), forming a unidirectional cycle.
Doubly Circular Linked List — Each node has two pointers (to the next and previous nodes), forming a bidirectional cycle.
This choice has profound implications for the operations we can perform efficiently, the memory we consume, and the complexity of our code. Understanding both variants deeply is essential for making informed engineering decisions.
By the end of this page, you will understand both singly and doubly circular linked list variants in complete detail. You'll know their structures, the trade-offs between them, when to choose each, and how to implement both. This knowledge enables you to select the right variant for any circular data structure requirement.
A singly circular linked list is the simpler of the two variants. Each node contains exactly two components:
The key characteristic: the last node's next pointer references the first node, completing the circle.
Visual Representation:
head → [10] → [20] → [30] → [40] ─┐
↑ │
└──────────────────────────┘
Starting from any node and following next pointers will cycle through all nodes and return to the starting point. There is no backward path—if you're at node [30] and want to reach [20], you must traverse forward through [40], [10], and finally [20].
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
// Node for a singly circular linked listclass SinglyCircularNode<T> { data: T; next: SinglyCircularNode<T>; constructor(data: T) { this.data = data; // Initially points to itself (valid single-node circular list) this.next = this; }} // Singly Circular Linked List implementationclass SinglyCircularLinkedList<T> { private tail: SinglyCircularNode<T> | null; private size: number; constructor() { this.tail = null; this.size = 0; } // Get the head (first node) in O(1) getHead(): SinglyCircularNode<T> | null { return this.tail ? this.tail.next : null; } // Get the tail (last node) in O(1) getTail(): SinglyCircularNode<T> | null { return this.tail; } isEmpty(): boolean { return this.tail === null; } getSize(): number { return this.size; } // Insert at the beginning: O(1) insertFirst(data: T): void { const newNode = new SinglyCircularNode(data); if (this.tail === null) { // First node points to itself this.tail = newNode; } else { // New node points to current head newNode.next = this.tail.next; // Tail points to new head this.tail.next = newNode; } this.size++; } // Insert at the end: O(1) insertLast(data: T): void { const newNode = new SinglyCircularNode(data); if (this.tail === null) { // First node points to itself this.tail = newNode; } else { // New node points to head newNode.next = this.tail.next; // Current tail points to new node this.tail.next = newNode; // Update tail reference this.tail = newNode; } this.size++; } // Delete from beginning: O(1) deleteFirst(): T | null { if (this.tail === null) return null; const head = this.tail.next; const data = head.data; if (this.tail === head) { // Only one node in the list this.tail = null; } else { // Tail now points to head's next this.tail.next = head.next; } this.size--; return data; } // Traverse and print all elements traverse(): void { if (this.tail === null) { console.log("Empty list"); return; } const head = this.tail.next; let current = head; const elements: T[] = []; do { elements.push(current.data); current = current.next; } while (current !== head); console.log(elements.join(" → ") + " → (back to start)"); }}This implementation uses a tail reference instead of head. Since tail.next gives us the head in a circular list, we get O(1) access to both ends. This enables O(1) insertions at both the beginning and the end—a significant advantage over head-only implementations.
The singly circular linked list inherits characteristics from both its circular nature and its singly-linked nature. Let's analyze its properties systematically.
Time Complexities:
| Operation | Time Complexity | Notes |
|---|---|---|
| Access head | O(1) | Via tail.next |
| Access tail | O(1) | Direct reference |
| Access by index | O(n) | Must traverse from head |
| Insert at head | O(1) | Update tail.next |
| Insert at tail | O(1) | Update tail reference |
| Insert at arbitrary position | O(n) | Must traverse to find position |
| Delete at head | O(1) | Update tail.next |
| Delete at tail | O(n) | Must traverse to find predecessor |
| Delete at arbitrary position | O(n) | Must find predecessor |
| Search | O(n) | Must traverse up to n nodes |
| Traverse forward | O(n) | Visit all nodes |
| Traverse backward | O(n²) or impossible | Must traverse forward to each predecessor |
The biggest limitation of singly circular lists is finding a node's predecessor. In a doubly circular list, this is O(1) via the prev pointer. In a singly circular list, you must traverse from head until you find the node whose next is your target—O(n) in the worst case. This impacts many operations, especially deletions.
A doubly circular linked list extends the singly circular variant by adding bidirectional links. Each node contains three components:
The key characteristics:
next points to the first nodeprev points to the last nodeThis creates two interlocking cycles: one going forward, one going backward.
Visual Representation:
┌───────────────────────────────────────────────┐
│ │
↓ │
head → [10] ⟷ [20] ⟷ [30] ⟷ [40] │
↑ │ │
│ └──────────────────────────┘
│
└───────────────────────────────────────────────┘
(prev direction)
From any node, you can traverse in either direction. Following next pointers cycles forward; following prev pointers cycles backward. Both directions are O(1) per step.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194
// Node for a doubly circular linked listclass DoublyCircularNode<T> { data: T; next: DoublyCircularNode<T>; prev: DoublyCircularNode<T>; constructor(data: T) { this.data = data; // Initially points to itself in both directions this.next = this; this.prev = this; }} // Doubly Circular Linked List implementationclass DoublyCircularLinkedList<T> { private head: DoublyCircularNode<T> | null; private size: number; constructor() { this.head = null; this.size = 0; } isEmpty(): boolean { return this.head === null; } getSize(): number { return this.size; } // Get the head (first node) in O(1) getHead(): DoublyCircularNode<T> | null { return this.head; } // Get the tail (last node) in O(1) — via head.prev! getTail(): DoublyCircularNode<T> | null { return this.head ? this.head.prev : null; } // Insert at the beginning: O(1) insertFirst(data: T): void { const newNode = new DoublyCircularNode(data); if (this.head === null) { // First node: already points to itself this.head = newNode; } else { const tail = this.head.prev; // Link new node into the cycle newNode.next = this.head; newNode.prev = tail; // Update existing nodes this.head.prev = newNode; tail.next = newNode; // Update head reference this.head = newNode; } this.size++; } // Insert at the end: O(1) insertLast(data: T): void { const newNode = new DoublyCircularNode(data); if (this.head === null) { // First node: already points to itself this.head = newNode; } else { const tail = this.head.prev; // Link new node into the cycle newNode.next = this.head; newNode.prev = tail; // Update existing nodes tail.next = newNode; this.head.prev = newNode; // Head stays the same; new node is the new tail } this.size++; } // Delete from beginning: O(1) deleteFirst(): T | null { if (this.head === null) return null; const data = this.head.data; if (this.head.next === this.head) { // Only one node this.head = null; } else { const tail = this.head.prev; const newHead = this.head.next; // Update links tail.next = newHead; newHead.prev = tail; // Update head reference this.head = newHead; } this.size--; return data; } // Delete from end: O(1) — This is where doubly linked shines! deleteLast(): T | null { if (this.head === null) return null; const tail = this.head.prev; const data = tail.data; if (this.head === tail) { // Only one node this.head = null; } else { const newTail = tail.prev; // Update links newTail.next = this.head; this.head.prev = newTail; } this.size--; return data; } // Delete a specific node: O(1) if we have the node reference! deleteNode(node: DoublyCircularNode<T>): T { const data = node.data; if (node.next === node) { // Only one node in the list this.head = null; } else { // Link neighbors to each other, bypassing this node node.prev.next = node.next; node.next.prev = node.prev; // If we deleted head, update head reference if (this.head === node) { this.head = node.next; } } this.size--; return data; } // Traverse forward traverseForward(): void { if (this.head === null) { console.log("Empty list"); return; } let current = this.head; const elements: T[] = []; do { elements.push(current.data); current = current.next; } while (current !== this.head); console.log("Forward: " + elements.join(" → ") + " → (cycle)"); } // Traverse backward traverseBackward(): void { if (this.head === null) { console.log("Empty list"); return; } let current = this.head.prev; // Start from tail const elements: T[] = []; do { elements.push(current.data); current = current.prev; } while (current !== this.head.prev); console.log("Backward: " + elements.join(" → ") + " → (cycle)"); }}Notice that head.prev gives us the tail in O(1) time! This is a powerful property of doubly circular lists. We don't need to maintain a separate tail pointer—the circular double linking provides it automatically.
The doubly circular linked list combines the benefits of bidirectional traversal with circular semantics. This creates a highly flexible structure at the cost of increased complexity and memory.
Time Complexities:
| Operation | Time Complexity | Notes |
|---|---|---|
| Access head | O(1) | Direct reference |
| Access tail | O(1) | Via head.prev |
| Access by index | O(n) | Can traverse from closer end |
| Insert at head | O(1) | Update 4 pointers |
| Insert at tail | O(1) | Update 4 pointers |
| Insert at arbitrary position | O(n) | Traverse + O(1) insertion |
| Delete at head | O(1) | Update 4 pointers |
| Delete at tail | O(1) | Huge advantage over singly! |
| Delete arbitrary node (given ref) | O(1) | Direct link update |
| Delete at arbitrary position | O(n) | Find + O(1) deletion |
| Find predecessor | O(1) | Via node.prev |
| Traverse forward | O(n) | Visit all nodes |
| Traverse backward | O(n) | Visit all nodes in reverse |
One of the most powerful features of doubly circular lists is O(1) deletion when you have a reference to the node. In a singly linked list, even with a node reference, you need O(n) to find the predecessor. In doubly linked, it's immediate: node.prev.next = node.next; node.next.prev = node.prev. This is crucial for algorithms like LRU caches where nodes are moved frequently.
Now that we understand both variants, let's systematically compare them to develop clear decision criteria.
Memory Comparison:
For a list of n elements where pointers are 8 bytes (64-bit system):
| Variant | Overhead per Node | Total for n Nodes | Example: 1M Nodes |
|---|---|---|---|
| Singly Circular | 8 bytes (1 pointer) | 8n bytes | 8 MB |
| Doubly Circular | 16 bytes (2 pointers) | 16n bytes | 16 MB |
Operation Comparison:
The key differentiator is operations involving predecessors:
| Operation | Singly Circular | Doubly Circular | Difference |
|---|---|---|---|
| Delete last element | O(n) | O(1) | Huge for frequent tail deletions |
| Delete given node | O(n) | O(1) | Critical for LRU, queue reordering |
| Find predecessor | O(n) | O(1) | Enables many optimizations |
| Traverse backward | Impossible efficiently | O(n) | Required for some algorithms |
| Insert before node | O(n) | O(1) | Common in list manipulation |
| Memory overhead | 1x | 2x | Significant for huge lists |
| Implementation complexity | Simple | Moderate | More code, more bugs |
Ask these questions: (1) Do I need to delete elements from the tail frequently? Use doubly. (2) Do I need to delete arbitrary nodes given a reference? Use doubly. (3) Do I need backward traversal? Use doubly. (4) Is memory a critical constraint? Consider singly. (5) Is simplicity paramount and use cases are basic? Consider singly.
A powerful technique for simplifying circular linked list implementations is the sentinel node (also called a dummy node). A sentinel is a special node that doesn't hold meaningful data but serves as a permanent anchor point in the list.
The Idea:
Instead of having head be null for an empty list and a real node otherwise, we always have a sentinel node. The "real" data nodes are between the sentinel and itself (in a circular manner).
Benefits:
Visualization:
With Sentinel (always present):
Empty list:
sentinel → (points to itself in both directions)
List with elements [10, 20, 30]:
sentinel ⟷ [10] ⟷ [20] ⟷ [30] ⟷ sentinel
The "real" head is sentinel.next, and the "real" tail is sentinel.prev.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
// Doubly Circular Linked List with Sentinel Nodeclass DoublyCircularWithSentinel<T> { private sentinel: DoublyCircularNode<T>; private size: number; constructor() { // Create sentinel with dummy data (will never be accessed) this.sentinel = new DoublyCircularNode(null as unknown as T); // Sentinel points to itself initially (empty list) this.sentinel.next = this.sentinel; this.sentinel.prev = this.sentinel; this.size = 0; } isEmpty(): boolean { // Empty if sentinel's next is itself return this.sentinel.next === this.sentinel; } getSize(): number { return this.size; } // Get first real node (or null if empty) getFirst(): DoublyCircularNode<T> | null { if (this.isEmpty()) return null; return this.sentinel.next; } // Get last real node (or null if empty) getLast(): DoublyCircularNode<T> | null { if (this.isEmpty()) return null; return this.sentinel.prev; } // Insert a node between two nodes (helper method) private insertBetween( newNode: DoublyCircularNode<T>, predecessor: DoublyCircularNode<T>, successor: DoublyCircularNode<T> ): void { newNode.prev = predecessor; newNode.next = successor; predecessor.next = newNode; successor.prev = newNode; this.size++; } // Insert at front: O(1) insertFirst(data: T): void { const newNode = new DoublyCircularNode(data); // Insert between sentinel and current first element this.insertBetween(newNode, this.sentinel, this.sentinel.next); } // Insert at back: O(1) insertLast(data: T): void { const newNode = new DoublyCircularNode(data); // Insert between current last element and sentinel this.insertBetween(newNode, this.sentinel.prev, this.sentinel); } // Delete a node (helper method) private deleteNode(node: DoublyCircularNode<T>): T { node.prev.next = node.next; node.next.prev = node.prev; this.size--; return node.data; } // Delete from front: O(1) deleteFirst(): T | null { if (this.isEmpty()) return null; return this.deleteNode(this.sentinel.next); } // Delete from back: O(1) deleteLast(): T | null { if (this.isEmpty()) return null; return this.deleteNode(this.sentinel.prev); }}Sentinel nodes are particularly valuable in doubly circular lists where the elimination of edge cases simplifies code significantly. The cost is one extra node of memory overhead (constant, not proportional to list size). Many real-world implementations (including parts of the Linux kernel) use this pattern.
We've thoroughly explored both singly and doubly circular linked list variants. Let's consolidate the key insights:
Decision Flowchart:
Do you need to traverse backward?
├── Yes → Use Doubly Circular
└── No → Continue...
│
Do you need O(1) deletion from tail or arbitrary nodes?
├── Yes → Use Doubly Circular
└── No → Continue...
│
Is memory a critical constraint?
├── Yes → Use Singly Circular
└── No → Doubly Circular (for flexibility)
What's Next:
Now that you understand both circular linked list variants, we'll explore the real-world applications where these structures excel. You'll see how round-robin scheduling, circular buffers, and other systems leverage circular linked lists to solve problems elegantly.
You now have a comprehensive understanding of both singly and doubly circular linked list variants. You know their structures, trade-offs, operation complexities, and the sentinel node pattern. This knowledge enables you to select and implement the right variant for any circular data structure requirement.