# Deep Dive into Data structures using Javascript - Doubly Linked List

### 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.

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.

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.

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.tail = null
this.length = 0
}

// make it optional to create Doubly Linked List with or without starter value
if (value) {
this.append(value)
}
}

/* doublyLinkedList output at initializing stage (empty starter):

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 end
• `prepend(value)` - add to the beginning
• `toArray()` - return Doubly Linked List elements in an array for ease of debugging
• `traverseToIndex(index)` - traversal helper
• `insert(index, value)` - add to the middle
• `deleteHead()` - delete from beginning
• `deleteTail()` - delete from the end
• `delete(index)` - delete from the middle
• `reverse()` - 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 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.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

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.
// 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!
// now that newNode has the this.head as next and newNode as prev, we can set the this.head as newNode directly.
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 = []

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

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
}`````` ``````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) {
this.tail = null
this.prev = null
this.length--
}

// pick the current head value:
// make the new heads prev pointer null
this.length--
}``````

#### 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.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.tail = null
this.prev = null
}

// If not define removal style. Removal will be either head, middle or tail.
let removalType

if (index === 0) {
}
// 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 === '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 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):
// Now reference this head to previousNode (contains the reversed list):

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
}
}

constructor(value) {
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 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.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

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.
// 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!
// now that newNode has the this.head as next and newNode as prev, we can set the this.head as newNode directly.
this.length++
return this
}

// toArray - loop through nested objects, then return the values in an array
toArray() {
const array = []

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

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
// 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) {
this.tail = null
this.prev = null
this.length--
}

// pick the current head value:
// make the new heads prev pointer null
this.length--
}

// 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.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.tail = null
this.prev = null
}

// If not define removal style. Removal will be either head, middle or tail.
let removalType

if (index === 0) {
}
// 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 === '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 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):