In my previous blog, I wrote about singly linked and added some functions, in order to create our data structure. In this blog I cover doubly linked list, which is almost identical to singly linked list, except in doubly linked list, every node has another pointer, which points at the previous node, unlike the singly linked list, where each node has only one pointer, which points at the next node.

As you could tell, doubly linked list gives us more flexibility, but more flexibility usually requires more memory and that is the downside of using doubly linked list.

Let’s create our doubly linked list. The snippet below contains all the code for creating node and doubly linked list classes as well as some basic functions, which let us add, remove, search and insert nodes into our doubly linked list.

// setting up the Node class
class Node {
constructor(val){
this.val = val;
this.next = null;
this.prev = null;
}
}
// Setting up DoublyLinkedList
class DoublyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
// push(val) add an element to end of the list
push(val){
let newNode = new Node(val)
if(!this.head){
this.head = newNode;
this.tail = newNode;
}else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;

}
this.length++;
return this;
}
// pop() removing the last element from the List
pop(){
if(!this.tail) return undefined;
let poppedNode = this.tail;
if(this.length === 1){
this.head = null;
this.tail = null;
} else {

this.tail = poppedNode.prev;
this.tail.next = null;
poppedNode.prev = null;
}
this.length--;
return poppedNode;
}
// shift() removing a node from beginning of the List
shift(){
if(this.length === 0) return undefined;
let oldHead = this.head;
if(this.length === 1){
this.head = null;
this.tail = null;
}else {
this.head = oldHead.next;
this.head.prev = null;
oldHead.next = null;
}
this.length--;
return oldHead;
}
// unshift() adding an element to the beginning of the List
unshift(val){
let newNode = new Node(val)
if(this.length === 0){
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
// get(val) gets a number and return the node
get(index){
if(index < 0 || index >= this.length) return null;
if(index <= this.length/2){
let count = 0;
let current = this.head;
while(count !== index){
current = current.next;
count++;
}
return current;
} else {
let count = this.length -1;
let current = this.tail;
while(count !== index){
current = current.prev;
count--;
}
return current;
}
}
// set(index, val) finds the node with index of given and set it to the new value was passed.
set(index, val){
let foundNode = this.get(index)
if(foundNode != null){
foundNode.val = val;
return true;
}
return false;
}
// insert(index, val) insert the given value in the given index
insert(index, val){
if(index < 0 || index > this.length) return false;
if(index === 0){
this.unshift(val)
return true;
}
if(index === this.length){
this.push(val)
return true;
}
let newNode = new Node(val);
let beforeNode = this.get(index - 1);
let afterNode = beforeNode.next;

beforeNode.next = newNode;
newNode.prev = beforeNode;
newNode.next = afterNode;
afterNode.prev = newNode;
this.length++;
return true;
}
// remove(index)
remove(index){
if(index < 0 || index >= this.length) return false;
if(index === 0){
this.shift()
// return true;
}
if(index === this.length - 1){
this.pop();
// return true;
}
let removedNode = this.get(index);
let beforeNode = removedNode.prev;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
afterNode.prev = beforeNode;
removedNode.next = null;
removedNode.prev = null;
this.length--;
return removedNode;
}
}

Big O of Doubly Linked List

  • Insertion → O(1)

To have more fun learning doubly linked list data structure, I would recommend checking out visualgo. It visualize data structures through animation and make it easier to understand and learn.

Cheers,

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store