Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Doubly Linked List Operations

Explore how doubly linked lists work by implementing core operations such as traversal, insertion, and deletion in JavaScript. Understand the impact of the additional previous node reference on algorithm efficiency and how it enables both forward and backward navigation. This lesson helps you gain practical skills for manipulating doubly linked lists while analyzing time and space complexities for each operation.

We'll cover the following...

By now, you are introduced to the structure of a doubly linked list and how each node stores two references: one to the next node and one to the previous node.

You have already implemented the core linked list operations for singly linked lists, including traversal, insertion, and deletion. The overall ideas behind these operations remain the same in a doubly linked list. However, because each node now stores an additional prev reference, some extra pointer updates are required to keep the structure consistent.

Let’s revisit the three core operations and understand how they work in a doubly linked list, and what changes they entail compared to singly linked lists.

Traversal in a doubly linked list

Traversal in a doubly linked list is primarily the same as traversal in a singly linked list. The process begins at the head node and repeatedly follows the next reference until the end of the list is reached.

As in a singly linked list, a temporary pointer, such as current, is used during traversal so that the head reference remains unchanged. At each step, the data stored in the current node can be processed, such as printing the value or comparing it with a target.

The main difference is that a doubly linked list also supports backward traversal, because each node stores a reference to the previous node.

In summary:

  • Forward traversal works exactly like it does in a singly linked list by following the next references.

  • Backward traversal becomes possible by following the prev references.

Backward traversal

To traverse backward in a doubly linked list:

  1. First move to the last node in the list.

  2. Process the data stored in the current node.

  3. Move to the previous node using current = current.prev.

  4. Repeat this process until current becomes NULL, which indicates that the beginning of the list has been passed.

Let’s look at the following interactive visualizer for the doubly linked list traversal.

JavaScript implementation of traversal in a doubly linked list

The following code shows a simple implementation of a doubly linked list and its traversal methods.

Javascript (babel-node)
class ListNode {
    constructor(data) {
        this.data = data;
        this.prev = null; // Points to the previous node
        this.next = null; // Points to the next node
    }
}
class DoublyLinkedList {
    constructor() {
        this.head = null; // Points to the first node
    }
    traverseForward() {
        let current = this.head; // Start from the head
        while (current !== null) {
            process.stdout.write(current.data + " -> "); // Process current node
            current = current.next; // Move to the next node
        }
        console.log("NULL"); // End of list
    }
    traverseBackward() {
        let current = this.head; // Start from the head
        if (current === null) {
            return;
        }
        // First move to the last node
        while (current.next !== null) {
            current = current.next;
        }
        while (current !== null) {
            process.stdout.write(current.data + " -> "); // Process current node
            current = current.prev; // Move to the previous node
        }
        console.log("NULL"); // Beginning of list reached
    }
}
// Create a doubly linked list manually: 10 <-> 20 <-> 30
const sampleList = new DoublyLinkedList();
const first = new ListNode(10);
const second = new ListNode(20);
const third = new ListNode(30);
sampleList.head = first;
first.next = second;
second.prev = first;
second.next = third;
third.prev = second;
// Show the difference between forward and backward traversal
process.stdout.write("Forward traversal: ");
sampleList.traverseForward();
process.stdout.write("\nBackward traversal: ");
sampleList.traverseBackward();
Doubly linked list traversal

  • Time complexity: Traversal takes O(n)O(n) time because each node is visited once.

  • Space complexity: Traversal uses O(1)O(1) extra space because it only requires a constant number of additional variables, such as a single temporary pointer (current). ...

Insertion in a doubly linked list