What is a Doubly Linked List?
A Doubly Linked List is a variation of Linked List data structure. It contains all characteristics of a Singly Linked List (or we simply call it Linked List) with one additional feature: each Node contains 2 pointers (previous and next) unlike Singly Linked List which has only one pointer that points to the next Node.
In this article I will be referring to Singly Linked Lists in some sections, therefore the tone of the article will be assuming you are familiar with the Linked List data structure. If that’s not the case or you need a quick refreshment on Linked Lists, I’d suggest you to start from the Linked List article by following the link below, then come back and continue here later:
Deep Dive into Data structures using Javascript - Linked List
Anatomy of a Doubly Linked List
A Doubly Linked List is consisted by a series of connected Nodes, each Node contains 3 properties:
Prev (pointer): 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.
Similar to Singly Linked List, we also call the first node “HEAD” and the last node “TAIL” here. But you probably have noticed a slight difference with the head node - one part is pointing to null on the visual. Why? It is because since we know the head is always first node - there is no other previous Node in the list to point to. Therefore the previous pointer on the head node will be always pointing to the null.
When and When not to use Doubly Linked List
When you have a situation that you might specifically considering to use a Doubly Linked List, it is most likely you have already decided to use a Linked List - and making comparison between if you go with a Singular Linked List or a Doubly Linked List. On next section we will be comparing these two. But let’s start with taking a quick look at the Big O of common operations in Doubly Linked List.
Doubly Linked List vs Singly Linked List
Whenever we deal with different data structures or their different implementations, answer to what to choose is same: “It depends on the context”. To get a better idea, let’s take a look at pros and cons of each one.
Singly Linked List
Pros:
- Implementation is simpler and more straight-forward compared to Doubly Linked List.
- It requires less memory, due to having a single pointer on each Node.
- Since we need to deal with a single pointer on each Node, there is less operations inside methods.
- Due to having less operations on methods, it operates slightly faster than Doubly Linked List.
Cons:
- Cannot be traversed in reverse direction, because pointers only targets the next Node.
- If the head node is not maintained correctly and lost for some reason, you will lose the rest of the list in memory.
When to use a Singly Linked List
- If you have less memory and memory is expensive.
- Main goal is to do fast insertion & deletion, you don’t have to deal with traversal so often.
Doubly Linked List
Pros:
- Better traversal abilities, it can be traversed in both directions (forward or backward).
- deleteTail() method is faster. In Singly Linked List, to remove the tail you need to traverse the whole list until the tail node and this operation takes O(n) Linear time. In Doubly Linked List you can simply use the tail Node’s previous pointer - which takes O(1) Constant time.
Cons:
- Implementation is more complex compared to Singly Linked List, due to having 2 pointers to deal with inside the methods.
- Takes more memory space due to having 2 pointers.
- It is slightly slower than Singly Linked List due to more operations needed on pointers inside each method.
When to use a Doubly Linked List
- You don’t have a memory problem.
- You want to do traversals / search elements in the list, ability to traverse backwards will give you better options for optimizing traversal performance.
Doubly Linked List implementation in Javascript
Similar to implementation of Singly Linked List, we will be also using ES6 Classes to build this data structure. If you want, you can open your favorite code editor and follow along with me as we go through the steps.
Step 1 - Build a class for the Doubly Linked List Node
Let’s start with identifying the Node element class, which we can use whenever we need to create a new Node.
class Node {
constructor(value) {
this.value = value
this.next = null
this.prev = null
}
}
// Create a new Node:
const newNode = new Node(10)
console.log(newNode)
/* newNode output:
Node {
value: 10,
next: null,
prev: null,
}
*/
Step 2 - Build a class for the Doubly Linked List
Now we can go further and create the class for DoublyLinkedList. We know that there should be head and tail properties. For ease of use, we can as well add a length property to keep track of our list length.
Additionally, we can have an option in the constructor to create the Doubly Linked List empty or with a single starter value. We will be looking at the append method at the next step.
class DoublyLinkedList {
constructor(value) {
this.head = null
this.tail = null
this.length = 0
}
// make it optional to create Doubly Linked List with or without starter value
if (value) {
this.append(value)
}
}
const doublyLinkedList = new DoublyLinkedList()
console.log(doublyLinkedList)
/* doublyLinkedList output at initializing stage (empty starter):
DoublyLinkedList {
head: null,
tail: null,
length: 0
}
*/
At this point we are done with the base building blocks: Node
and DoublyLinkedList
classes. We can continue with extending our DoublyLinkedList class by introducing common methods. To make these methods easier to understand and reason with, I have placed code comments at specific places inside them.
Here is the list of methods we are going to implement:
append(value)
- add to the endprepend(value)
- add to the beginningtoArray()
- return Doubly 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
Step 3 - Doubly Linked List append method
// Add to the end of list
append(value) {
// Initialize a newNode with value recieved
const newNode = new Node(value)
// Let's first check if Doubly Linked List is empty or not.
if (!this.head) {
// If there is no head (no elements) it is empty. In that case make the newNode as head
// since it is the only node at this point and there is no tail either,
// tail will also have the same value (both head and tail will point to same place in memory from now on):
this.head = newNode
this.tail = newNode
} else {
// Since the newNode will be the new tail, set the prev value to current tail before applying changes. Timing is important!
newNode.prev = this.tail
// we have this.tail = this.head is setup with first entry
// at first we populate the this.tail.next with newNode. Since both are referencing the same object, both head and tail will look equal at this step:
this.tail.next = newNode
// at this step, we cleanup the tail by setting it to newNode. In other words we extended the head by using tail first, then cleaned up the tail by using newNode.
this.tail = newNode
}
this.length++
return this
}
Step 4 - Doubly Linked List prepend method
// Add to the beginning of list
prepend(value) {
// Let's check first if Doubly Linked List is empty or not.
// If that's the case, return here by using the append method instead
if (!this.head) {
return this.append(value)
}
// Initialize a newNode with value recieved
const newNode = new Node(value)
// apply a reference to newNode.next prop. When we add it at the start, naturally prepended node's next value should point to the this.head.
newNode.next = this.head
// Since the newNode will be the new previous for the current head, set the prev value of head to be newNode. We do this before changing the pointer of this.head to newNode. Timing is important!
this.head.prev = newNode
// now that newNode has the this.head as next and newNode as prev, we can set the this.head as newNode directly.
this.head = newNode
this.length++
return this
}
Step 5 - Doubly Linked List toArray method (optional)
To easily debug what is going on our list (or have an option to output Doubly Linked List as an array), we will need toArray method:
// toArray - loop through nested objects, then return the values in an array
toArray() {
const array = []
let currentNode = this.head
while (currentNode !== null) {
array.push(currentNode.value)
currentNode = currentNode.next
}
return array
}
Step 6 - Doubly Linked List traverseToIndex method (helper)
Since both insert and removal related methods will have to deal with traversing to a specific index, it will be wise to implement a helper for it:
// lookup / traversal helper
traverseToIndex(index) {
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
let counter = 0
let currentNode = this.head
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
Step 7 - Doubly Linked List insert method
insert(index, value) {
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
// if length is too long, just append (add at the end)
if (index >= this.length || !this.head) {
return this.append(value)
}
// if index is 0, just prepend (add to the beginning)
if (index === 0) {
return this.prepend(value)
}
// Initialize a newNode with value recieved
const newNode = new Node(value)
/*
Solution flow:
1 - Pick the previous index Node of target idx
2 - Pick the target idx Node by using preIdx.next pointer
3 - Now change previous idx Node pointer to newNode. This will change the previous Node's pointer.
4 - Now change the newNode.next to targetIdx.
5 - In other words, we just put the new node in between previous and target: by making previous to point to new node, then new node to previous target idx before insert()
*/
// previous one
const preIdx = this.traverseToIndex(index - 1)
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++
return this
}
Step 8 - Doubly Linked List deleteHead method
deleteHead() {
// check the length - if zero return a warning
if (this.length === 0) return 'List is empty'
// If there is only one node left:
if (this.length === 1) {
const headVal = this.head.value
this.head = null
this.tail = null
this.prev = 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
// make the new heads prev pointer null
newHead.prev = null
// now change the head pointer to newHead
this.head = newHead
this.length--
return headVal
}
Step 9 - Doubly Linked List deleteTail method
deleteTail() {
// check the length - if zero return a warning
if (this.length === 0) return 'List is empty'
// 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
}
// Define new tail by traversing to previous Node of tail idx
// Note that, tail always points to null. (which is length).
// length - 1 will point to last Node with a value. Therefore we need to target length - 2
const tailVal = this.tail.value
const newTail = this.tail.prev
// Now, we can just simply update the pointer of newTail to null:
newTail.next = null
this.tail = newTail
this.length--
return tailVal
}
Step 10 - Doubly Linked List delete method
delete(index) {
// 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) {
this.head = null
this.tail = null
this.prev = null
}
// 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
}
}
Final step - Reverse a Doubly Linked List
Similar to reversing a Singly Linked List, we will be also using 3 pointers here to reverse the Doubly Linked List. Strategy is very similar with a minor difference - and that is we already have a previous pointer inside each node here. When we deal with reversing a Singly Linked List, we need to create a pointer instead for previous node while traversing since the nodes does not contain them.
Our goal here is basically changing the direction of pointers, one step at a time:
reverse() {
// do not reverse if no elements
if (this.length === 0) return
// do not reverse if there is a single element
if (this.length === 1) return this
let currNode = this.head
let prevNode = null
let nextNode = null
while (currNode) {
// Store next node.
nextNode = currNode.next
// Store prev node.
prevNode = currNode.prev
// Change next node of the current node so it would link to previous node.
currNode.next = prevNode
currNode.prev = nextNode
// Move prevNode and currNode nodes one step forward.
prevNode = currNode
currNode = nextNode
}
// 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 = prevNode
return this
}
I hope this article helped you to understand how Doubly Linked Lists works! I’d also like to encourage you to check out this amazing data structures and algorithms visualizer (I have actually generated the gifs you have seen above at this website): https://visualgo.net/en
You can see the full implementation of the Doubly Linked List in Javascript that we went through in this article below. Thanks for reading!
Implementation of Doubly Linked List in Javascript:
class Node {
constructor(value) {
this.value = value
this.next = null
this.prev = null
}
}
class DoublyLinkedList {
constructor(value) {
this.head = null
this.tail = null
this.length = 0
// make it optional to create Doubly Linked List with or without starter value
if (value) {
this.append(value)
}
}
// Add to the end of list
append(value) {
// Initialize a newNode with value recieved
const newNode = new Node(value)
// Let's first check if Doubly Linked List is empty or not.
if (!this.head) {
// If there is no head (no elements) it is empty. In that case make the newNode as head
// since it is the only node at this point and there is no tail either,
// tail will also have the same value (both head and tail will point to same place in memory from now on):
this.head = newNode
this.tail = newNode
} else {
// Since the newNode will be the new tail, set the prev value to current tail before applying changes. Timing is important!
newNode.prev = this.tail
// we have this.tail = this.head is setup with first entry
// at first we populate the this.tail.next with newNode. Since both are referencing the same object, both head and tail will look equal at this step:
this.tail.next = newNode
// at this step, we cleanup the tail by setting it to newNode. In other words we extended the head by using tail first, then cleaned up the tail by using newNode.
this.tail = newNode
}
this.length++
return this
}
// Add to the beginning of list
prepend(value) {
// Let's check first if Doubly Linked List is empty or not.
// If that's the case, return here by using the append method instead
if (!this.head) {
return this.append(value)
}
// Initialize a newNode with value recieved
const newNode = new Node(value)
// apply a reference to newNode.next prop. When we add it at the start, naturally prepended node's next value should point to the this.head.
newNode.next = this.head
// Since the newNode will be the new previous for the current head, set the prev value of head to be newNode. We do this before changing the pointer of this.head to newNode. Timing is important!
this.head.prev = newNode
// now that newNode has the this.head as next and newNode as prev, we can set the this.head as newNode directly.
this.head = newNode
this.length++
return this
}
// toArray - loop through nested objects, then return the values in an array
toArray() {
const array = []
let currentNode = this.head
while (currentNode !== null) {
array.push(currentNode.value)
currentNode = currentNode.next
}
return array
}
// lookup / traversal helper
traverseToIndex(index) {
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
let counter = 0
let currentNode = this.head
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
// insert to specific index
insert(index, value) {
// validate the received index parameter:
if (!index) return 'Index is missing'
if (typeof index !== 'number') return 'Index should be a number'
// if length is too long, just append (add at the end)
if (index >= this.length || !this.head) {
return this.append(value)
}
// if index is 0, just prepend (add to the beginning)
if (index === 0) {
return this.prepend(value)
}
// Initialize a newNode with value recieved
const newNode = new Node(value)
/*
Solution flow:
1 - Pick the previous index Node of target idx
2 - Pick the target idx Node by using preIdx.next pointer
3 - Now change previous idx Node pointer to newNode. This will change the previous Node's pointer.
4 - Now change the newNode.next to targetIdx.
5 - In other words, we just put the new node in between previous and target: by making previous to point to new node, then new node to previous target idx before insert()
*/
// previous one
const preIdx = this.traverseToIndex(index - 1)
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++
return this
}
// Delete from beginning of list
deleteHead() {
// check the length - if zero return a warning
if (this.length === 0) return 'List is empty'
// If there is only one node left:
if (this.length === 1) {
const headVal = this.head.value
this.head = null
this.tail = null
this.prev = 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
// make the new heads prev pointer null
newHead.prev = null
// now change the head pointer to newHead
this.head = newHead
this.length--
return headVal
}
// Delete from the end of list
deleteTail() {
// check the length - if zero return a warning
if (this.length === 0) return 'List is empty'
// 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
}
// Define new tail by traversing to previous Node of tail idx
// Note that, tail always points to null. (which is length).
// length - 1 will point to last Node with a value. Therefore we need to target length - 2
const tailVal = this.tail.value
const newTail = this.tail.prev
// Now, we can just simply update the pointer of newTail to null:
newTail.next = null
this.tail = newTail
this.length--
return tailVal
}
// Delete from specific index
delete(index) {
// 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) {
this.head = null
this.tail = null
this.prev = null
}
// 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 the list
reverse() {
// do not reverse if no elements
if (this.length === 0) return
// do not reverse if there is a single element
if (this.length === 1) return this
let currNode = this.head
let prevNode = null
let nextNode = null
while (currNode) {
// Store next node.
nextNode = currNode.next
// Store prev node.
prevNode = currNode.prev
// Change next node of the current node so it would link to previous node.
currNode.next = prevNode
currNode.prev = nextNode
// Move prevNode and currNode nodes one step forward.
prevNode = currNode
currNode = nextNode
}
// 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 = prevNode
return this
}
}