There are a few different types of linked lists. But the most popular ones are: singly, doubly and circular. In this article we will learn to implement a doubly Linked List Data structure in JavaScript. Some of the operations that we are going to implement in this article are:
- Add a node to the head
- Add a node to the tail
- Reverse a linked list
We will start by creating a linked list function constructor and it will contain two piece of information (a) the head and (b) the tail.
All a linked list class needs are two pointers the head pointer which points to the first
node in the list and the tail pointer which points to the last node in the list.
function LinkedList() {
this.head = null;
this.tail = null;
}
Initially the head and the tail will be set to null because they will have no nodes to point at the start.
Next, for our node list we will create a node constructor function. Each node will have three properties on the them (a) the value, (b) the pointer to the next node and (c) the pointer to the previous node.
function Node(value, next, prev) {
this.value = value;
this.next = next;
this.prev = prev
}
Now we will instantiate a new linked list.
const LL = new LinkedList()
// if you try to access the linked list, it will look like this
console.log(LL) // { head: null, tail: null }
Next up, the new instantiation will have few helper method to add and remove data.
1. addToHead
This method adds new value to head of the linked list.
LinkedList.prototype.addToHead = function (value) {
// instantiate a new node
const newNode = new Node(value, this.head, null);
// if there is already a head present set its prev value to the newNode
if (this.head) {
this.head.prev = newNode;
} else {
this.tail = newNode;
}
// set the current head to newNode
this.head = newNode;
};
LL.addToHead(80)
LL.addToHead(90)
LL.addToHead(100)
2. addToTail
This method adds new value to tail of the linked list.
LinkedList.prototype.addToTail = function (value) {
const newNode = new Node(value, null, this.tail);
if (this.tail) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
};
3. removeHead
This method deletes the current head and returns its value
LinkedList.prototype.removeHead = function () {
// if there is no head, simply return null
if (!this.head) return null;
// else
// store the current head value in a variable to return it later
let currentVal = this.head.value;
// now reassign the current head
this.head = this.head.next;
// if there is a next value, change its prev value to null
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
return currentVal;
};
4. removeTail
This method deletes the current tail and returns its value
LinkedList.prototype.removeTail = function () {
if (!this.tail) return null;
let currentVal = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.tail = null;
}
return currentVal;
};
5. reverse
This method reverses the linked list
LinkedList.prototype.reverse = function () {
// head is the first node in the list
let currentNode = this.head;
// start with the head
// as long as currentNode has a value run the loop
while (currentNode) {
// store the current node prev value in a varialbe
let temp = currentNode.prev;
// swap the previous and next node with each other
currentNode.prev = currentNode.next;
currentNode.next = temp;
// assing the previous node value to the current node which will eventually be null
currentNode = currentNode.prev;
}
// store the currentTail's value in a variable
let currentTail = this.tail;
// reassign the tail's value to current head and head's value to previous tail
this.tail = this.head;
this.head = currentTail;
};
Summary
In this article we implemented a doubly linked list in JavaScript. Hope you enjoyed reading it.:)
Top comments (0)