Hello Everyone,
Today I will be talking about a data structure called Doubly Linked List. Before I start talking about the Doubly linked list, I highly recommend reading my blog on Singly Linked List (Click Here). It will give you an overview of the Singly Linked List data. What is Doubly Linked List? A Doubly Linked List (points to two directions) very identical to Singly Linked List except it contains an extra pointer that keeps track of the previous node. Doubly Linked List has two pointers on every node that keeps track of the previous node and next node, unlike Singly Linked List which only keeps track of the next node. Just like the Singly Linked List, the first node in the Doubly Linked List is also called the head and the last node is also called the tail. In Doubly Linked List each node stores three things, data (integer or string), a reference to the next node and a previous node.
Doubly Linked List
So in the picture above we have a head node (A) pointing to the next node (B) and then also has a previous pointer but there?s nothing there that?s why it’s NULL. If we go to the node ( B ), you can see it’s pointing to the next node ( C ) as well as it?s pointing to the previous node ( A ).
Now let?s implement the Doubly Linked List (JavaScript).
We need two classes one called Node, Other DoublyLinkedList.
- A Node class will have value, next and prev.
- A DoublyLinkedList class will have a head, tail, and length.
class Node {constructor(val) {this.val = val;this.next = null;this.prev = null; }}class DoublyLinkedList {constructor() {this.head = null;this.tail = null;this.length = 0; }}
At the moment Doubly Linked List doesn’t do anything right now. Let?s write a method called the push to add a node to the end of the Doubly Linked List.
class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }}
Push Method Visual From https://visualgo.net/en/list
Let?s Implement method Pop to remove from the end
class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length–; return currentTail; }}
Pop Method Visual From https://visualgo.net/en/list
Next method Shift to remove from the beginning of the Doubly Linked List
class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length–; return currentTail; }shift() { let oldHead = this.head; if (this.length === 0) return undefined; else 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; }}
Shift Method Visual From https://visualgo.net/en/list
Finally, a method that adds in the front called unshift.
class DoublyLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; }push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail this.tail = newNode; } this.length++ return this; }pop() { if (!this.head) return undefined; let currentTail = this.tail; if (this.length === 1) { this.head = null this.tail = null } else { this.tail = currentTail.prev; this.tail.next = null; currentTail.prev = null; } this.length–; return currentTail; }shift() { let oldHead = this.head; if (this.length === 0) return undefined; else 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(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 }}
UnShift Method Visual From https://visualgo.net/en/list
- Check out my GitHub repository for the code above HERE, it also contains many more methods.
- Gif Animations HERE
There you have it. I hope you found this blog helpful. If you’re having any difficulty or need more explanation, I?m more than happy to help you. Please connect with me on LinkedIn or my email is [email protected].
Happy Coding 🙂
Src: https://s3.amazonaws.com/msoe/files/callouts/wide_sml_computer-science-landing-page.jpg
References:
Doubly Linked List | Set 1 (Introduction and Insertion) – GeeksforGeeks
We strongly recommend to refer following post as a prerequisite of this post. Linked List Introduction Inserting a node?
www.geeksforgeeks.org
https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass
