Doubly Linked List

Doubly Linked List

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 postDoubly 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; }}Image for postPush 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; }}Image for postPop 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; }}Image for postShift 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 postUnShift 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 singhamritpal49@gmail.com.

Happy Coding 🙂

Image for postSrc: 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

1

No Responses

Write a response