What is a Circular Doubly Linked List?
A Circular Doubly Linked list is a variation of Linked List data structure, which is very similar to Singly Circular Linked List with only one difference: nodes contains 2 pointers (previous and next) instead of a single one (next). We can also say that the difference between them follows the similar fashion like Linear Singly Linked List vs Linear Doubly Linked List.
In Circular Doubly Linked List, the tail and head points to eachother to form a circle of nodes - we do not have any null termination at the tail. Because of this structural difference, Circular Doubly Linked list classifies as a non-linear data structure unlike the regular Linked list variations which is linear - since the shape of connected nodes forms a cyclic data structure.
The tone of this article will be assuming you are familiar with Linked List, Doubly Linked List and Circular Linked List data structures. If that’s not the case or you need a quick refreshment on them, I would suggest you to first follow through the article links below, then come back and continue here later:
Deep Dive into Data structures using Javascript - Linked List
Deep Dive into Data structures using Javascript - Doubly Linked List
Deep Dive into Data structures using Javascript - Circular Linked List
Anatomy of a Circular Doubly Linked List
A Circular Doubly Linked List is consisted by series of connected nodes that forms a cyclic data structure. Each node contains 3 properties:
Prev: Holds a reference (pointer) to the previous Node.
Value: Holds the value / data for the Node.
Next (pointer): Holds a reference (pointer) to the next Node.
Since this variation has no null termination and not a linear list, we don’t actually have a “head” or the “tail” here with the same meaning. But still, maintaining pointers for first and last inserted elements will help to form the circular structure by linking them to eachother. Knowing first and last elements also makes it easier to implement the common methods.
Common methods of Circular Doubly Linked List is extremely similar with regular Doubly Linked List methods, but there are 2 cavaets that we need to be aware of:
- We cannot use the same traversal exit condition (null termination). If we are not careful, a traversal can end up in an infinite loop.
- Relationship of head and tail is different here, therefore we need to keep that in mind and make sure to maintain the circular reference of pointers properly. Specially whenever we do inserts or deletions, wrong way of updating pointers can cause losing rest of the list in memory.
When to use Circular Doubly Linked List
Circular Doubly Linked list shares the same Big O complexity with Doubly Linked Lists. And the reason we may want to consider choosing this data structure is exactly the same with the Singly Circular Linked List variant: Whenever we need to deal with operations that has circular logic - a list that accesses items over and over again in a loop. For more details, please refer to the section “When to use Circular Linked List” in the article: Circular Linked List
Now you might be thinking, “If this circular data structure makes sense for my use case, how should I know which variant to choose between Circular Linked Lists - should I go with Singly or Doubly?”
Answer to this would be pretty much same with deciding between Singly vs Doubly Linked Lists. Please refer to the section “Doubly Linked List vs Singly Linked List” in the article for more details: Doubly Linked List
Circular Doubly Linked List implementation in Javascript
We will be also using ES6 Classes to build this data structure similar to other Linked list types. Here is the list of methods in the implementation:
initialize(value)- helper for initializing the list with circular referenceappend(value)- add to the endprepend(value)- add to the beginningtoArray()- return Circular Linked List elements in an array for ease of debuggingtraverseToIndex(index)- traversal helperinsert(index, value)- add to the middledeleteHead()- delete from beginningdeleteTail()- delete from the enddelete(index)- delete from the middlereverse()- reverse order of items
To make these methods easier to understand and reason with, I have placed code comments at specific places inside them. I hope this article helped you to understand how Circular Doubly Linked List works! I’d like to encourage you to experiment with the implementation below in your favorite code editor, and follow along with comments in case you need further understanding. Thanks for reading!
class Node {
constructor(value) {
this.value = value
this.next = null
this.prev = null
}
}
class CircularDoublyLinkedList {
constructor(value) {
this.head = null
this.tail = null
this.length = 0
if (value) {
this.initialize(value)
}
}
// used to initialize Circular Doubly Linked List
initialize(value) {
// create a node
const newNode = new Node(value)
// create a circular reference (points to itself)
newNode.next = newNode
newNode.prev = newNode
// now make both head and tail to point on newNode
this.head = newNode
this.tail = newNode
// increment length
this.length++
}
append(value) {
// if length is zero, use initialize method instead
if (this.length === 0) {
return this.initialize(value)
}
// create a new node
const newNode = new Node(value)
// fix newNode pointers to set it as a new tail:
newNode.prev = this.tail
newNode.next = this.head
// now update the head and tail accordingly:
this.head.prev = newNode
this.tail.next = newNode
// update the tail to be the newNode:
this.tail = newNode
// increment length:
this.length++
}
prepend(value) {
// if length is zero, use initialize method instead
if (this.length === 0) {
return this.initialize(value)
}
// create a new node
const newNode = new Node(value)
// fix newNode pointers to set it as a new head:
newNode.next = this.head
newNode.prev = this.tail
// now update the head and tail accordingly:
this.head.prev = newNode
this.tail.next = newNode
// update the head to be the newNode:
this.head = newNode
// increment length
this.length++
}
// toArray - loop through nested objects, then return the values in an array
toArray() {
const array = []
// Initialize a currentNode variable pointing to this.head - which will be the starting point for traversal.
let currentNode = this.head
do {
array.push(currentNode.value)
currentNode = currentNode.next
// NOTE:
// Since there can be duplicate values in the list, we will be using "Referential equality" instead of comparing Node values as the exit condition (which is figuring out where the head is).
// When strict equality operator is used in reference types in JS, it checks if compared values referencing the same object instance. This is useful when you like to compare references.
} while (currentNode !== this.head)
return array
}
// traverse to index
traverseToIndex(index) {
if (index < 0) return undefined
// keeps track of traversal
let counter = 0
// starting point
let currentNode = this.head
// traverse to the target index
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
insert(index, value) {
// if length is 0, just prepend (add to the beginning)
if (index === 0) {
return this.prepend(value)
}
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
if (index < 0) return 'Index should be bigger than zero'
// if length is too long, just append (add to the end)
if (index >= this.length) {
return this.append(value)
}
// Initialize a newNode with value recieved.
const newNode = new Node(value)
// pick previous index
const preIdx = this.traverseToIndex(index - 1)
// pick target index
const targetIdx = preIdx.next
// Set the preIdx next to newNode. This is because newNode replaces the targetIdx's position.
preIdx.next = newNode
// Set the newNode prev to preIdx. This is because newNode replaces the targetIdx's position.
newNode.prev = preIdx
// Set the newNode next to targetIdx. This is because newNode replaces the targetIdx's position.
newNode.next = targetIdx
// Now, targetIdx (which have changed place until this step) will point the prev to the newNode. Again, timing is important on steps!
targetIdx.prev = newNode
this.length++
}
// remove from beginning:
deleteHead() {
// check if there is a head value - if not return a warning or null
if (this.length === 0) return null
const currHead = this.head
// if one element left
if (this.length === 1) {
const headVal = this.head.value
this.head = null
this.tail = null
this.length--
return headVal
}
// pick the current head value:
const headVal = this.head.value
// define newHead as this.head.next
const newHead = this.head.next
// move the head to next node:
this.head = newHead
// set the tail next to new this.head:
this.tail.next = this.head
// set the new previous pointer to updated tail:
this.head.prev = this.tail
// decrement length:
this.length--
return headVal
}
// remove from end:
deleteTail() {
// check the length - if zero return null
if (this.length === 0) return null
// If there is only one node left:
if (this.length === 1) {
const tailVal = this.tail.value
this.head = null
this.tail = null
this.prev = null
this.length--
return tailVal
}
// store the tailVal (to return):
const tailVal = this.tail.value
// define new tail by picking the previous node of current tail.
const newTail = this.tail.prev
// prepare for replacement:
// point newTail.next to this.head
newTail.next = this.head
// point this.head.prev to newTail. Now the new tail has correct pointers.
this.head.prev = newTail
// finalize removal by pointing current tail to newTail
this.tail = newTail
// decrement length:
this.length--
return tailVal
}
// Delete from specific index
delete(index) {
// if length is 0, just prepend (add to the beginning)
if (index === 0) {
return this.deleteHead()
}
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
// check the length - if zero return a warning
if (this.length === 0) return 'List is empty'
// Validation - should not be less than 0
if (index < 0) return `Minimum idx should be 0 or greater`
// Check if it is the last element. In that case reset head and tail to null
if (this.length === 1) {
const targetVal = this.head.value
this.head = null
this.tail = null
this.prev = null
return targetVal
}
// If not define removal style. Removal will be either head, middle or tail.
let removalType
if (index === 0) {
removalType = 'head'
}
// When we do a removal from middle on Doubly Linked List, we need to take 3 indexes into account: pre, target and next. To be able to make it work the middle removal with the length prop, we specify the comparison one minus form the length prop compared to a Singly Linked List.
if (index >= this.length - 1) {
removalType = 'tail'
}
if (index > 0 && index < this.length - 1) {
removalType = 'middle'
}
if (removalType === 'head') {
return this.deleteHead()
}
if (removalType === 'tail') {
return this.deleteTail()
}
if (removalType === 'middle') {
/*
Pick the previous Node of targetIdx via traverse.
Pick the target idx with preIdx.next
Now make preIdx point to targetIdx next. This will remove the node in middle.
*/
const preIdx = this.traverseToIndex(index - 1)
const targetIdx = preIdx.next
const targetVal = targetIdx.value
const nextIdx = targetIdx.next
preIdx.next = nextIdx
nextIdx.prev = preIdx
this.length--
return targetVal
}
}
reverse() {
// Checkup - if list only contains one item, no need to reverse
if (this.length === 0) return
// do not reverse if there is a single element
if (this.length === 1) return
// We'll use 3 pointers. Prev and Next is empty at the start
let previousNode = null
let currentNode = this.head
let nextNode = null
// It is quite similar to doubly linked list reverse, the main difference is we can't use null termination as an exit condition - due to dealing with a circular list.
// To tackle this issue, we will be using "Referential equality" instead of comparing Node values as the exit condition (which is figuring out if we come back to the head node again).
// When strict equality operator is used in reference types in JS, it checks if compared values referencing the same object instance. This is useful when you need to compare references.
do {
// Store next node reference
nextNode = currentNode.next
// Store prev node reference
previousNode = currentNode.prev
// Change next node of the current node so it would link to previous node.
currentNode.next = previousNode
currentNode.prev = nextNode
// Move prevNode and currNode nodes one step forward.
previousNode = currentNode
currentNode = nextNode
// console.log(previousNode.value, currentNode.value, nextNode.value)
} while (currentNode !== this.head)
// Set the new tail with this.head (it contains the last item at this point of time):
this.tail = this.head
// Now reference this head to previousNode (contains the reversed list):
this.head = previousNode
return this.toArray()
}
}