Doubly Linked List - 911 WeKnow

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.

Image for post 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.

Let?s Implement method Pop to remove from the end

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; }} Image for post 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 }} Image for post 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 🙂

Image for post Src: https://s3.amazonaws.com/msoe/files/callouts/wide_sml_computer-science-landing-page.jpg