Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in JavaScript

Doubly Linked Lists (DLL)

Explore the concept of doubly linked lists, understanding how nodes with previous and next pointers enable bi-directional traversal. Learn how maintaining a tail pointer enhances performance in operations like deletion, helping you implement efficient doubly linked lists in JavaScript.

We'll cover the following...

Introduction

By now, you may have noticed a constraint that arises when dealing with singly-linked lists. For any function which does not operate at the head, we must traverse the whole list.

Furthermore, since a linked list can only be traversed in one direction, this limits us to a great extent. Thus we needlessly have to keep track of previous elements.

This is where the doubly linked list comes to the rescue!

Structure of the Doubly Linked List (DLL)

The only difference between doubly and singly-linked lists is that in DLLs, each node contains pointers for both the previous and the next node. This makes the DLLs bi-directional.

To implement this in code, we simply need to add a new member to the already constructed Node class:

Node.js
class Node {
  constructor(value) {
    this.data=value; //Stores data
    this.previousElement=null; //Stores pointer to previous element
    this.nextElement=null; //Stores pointer to next element
  }
}

Explanation: data and nextElement remain unchanged. The previousElement pointer has been introduced to store information about the preceding node.

Take a look at what the doubly linked list looks like:

Tail pointer

Maintaining a tail pointer in a doubly-linked list unleashes the real potential of DLLs. The ability to go back from a node in addition to a tail pointer can greatly speed up operations concerning tail e.g., deletion at the tail.

Look at the representation of a DLL class. The only addition is that we now keep the tail pointer in addition to the head.

Node.js
class LinkedList {
 constructor() {
   this.head=null;
   this.tail=null;
 }
}

Look at the following visualization of how a doubly linked list looks with a tail pointer.