Doubly Linked List in JavaScript

A Linked List 🔗 is a linear data structure that stores data in a list of nodes, each node has a pointer to the next node and so on until the tail points to null.

Singly Linked List: In a singly linked list, each node has a pointer only to the next node.

|1|* --> |2| *--> |3| *--> null

Doubly Linked List: In a doubly linked list, each node has pointers to both the next and the previous nodes.

NULL <--|1|<-->|2|<-->|3|--> NULL

Methods of a Linked List

isEmpty – Checks whether the linked list is empty.
peek – Returns the value of the head node without removing it.
push – Adds a new node with the specified value to the end of the list and returns the new length.
pop – Removes and returns the last node from the list.
shift – Removes and returns the first node from the list.
unshift – Adds a new node with the specified value to the beginning of the list and returns the new length.
get – Retrieves the node at a specified index.
set – Sets a new value for a node at a specified index and returns true if successful.
insert – Inserts a new node with a given value at a specified index in the list and returns true if successful.
remove – Removes the node at a specified index and returns it.
reverse – Reverses the order of nodes in the linked list. (not need incase of a doubly linked list as it is already linked both the ways by next and previous pointers)

JavaScript Code for a Doubly Linked List

class Node {
  constructor(value) {
    this.value = value; // Data stored in the node
    this.next = null; // Pointer to the next node
    this.prev = null; // Pointer to the previous node

  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Checks if the list is empty
  isEmpty() {
    return this.length === 0;
  }

  // Returns the value of the head node
  peek() {
    return this.head?.value;
  }

  // Adds a new node with the given value to the end of the list
  push(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      // If the linkedList is empty, the new node becomes both the head and tail
      this.head = newNode;
      this.tail = newNode;
    } else {
      // Otherwise, add the new node to the end and update the 'tail' pointer
      this.tail.next = newNode;
      newNode.prev = this.tail
      this.tail = newNode;
    }
    return ++this.length;
  }

  // Removes the last node from the list and returns it
  pop() {
    if (this.isEmpty()) return undefined;
    const oldTailNode = this.tail;
    if (this.length === 1) {
      // If the list has only one node
      this.head = null;
      this.tail = null;
    } else {
      this.tail = oldTailNode.prev;
      this.tail.next = null;
      oldTailNode.prev = null;
    }
    this.length--;
    return oldTailNode;
  }

  // Removes the first node from the list and returns it
  shift() {
    if (this.isEmpty()) return undefined;
    const oldHeadNode = this.head
    this.head = oldHeadNode.next
    this.head.prev = null
    oldHeadNode.next = null
    this.length--
    if (this.isEmpty()) {
      this.tail = null
    }
    return oldHeadNode
  }

  // Adds a new node with the given value to the beginning of the list
  unshift(value) {
    const newHeadNode = new Node(value);
    if (this.isEmpty()) {
      this.tail = newHeadNode
    } else {
      this.head.prev = newHeadNode
      newHeadNode.next = this.head
    }
    this.head = newHeadNode
    return ++this.length;
  }

  // Retrieves the node at the specified index
  get(index) {
    if (index < 0 || index >= this.length) return undefined;
    let counter = 0
    let currentPointer = null;
    if (index <= this.length / 2) {
      currentPointer = this.head
      while (counter !== index) {
        currentPointer = currentPointer.next
        counter++
      }
    } else {
      currentPointer = this.tail
      counter = this.length - 1
      while (counter !== index) {
        currentPointer = currentPointer.prev
        counter--
      }
    }
    return currentPointer
  }

  // Sets the value of the node at the specified index
  set(index, value) {
    const findNode = this.get(index)
    if (findNode) {
      findNode.value = value
      return true
    }
    return false
  }

  // Inserts a new node with the given value at the specified index
  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) {
      this.unshift(value)
      return true
    }
    if (index === this.length) {
      this.push(value)
      return true
    }
    const newNode = new Node(value)
    const beforeNode = this.get(index - 1)
    const afterNode = beforeNode.next
    beforeNode.next = newNode
    newNode.prev = beforeNode
    newNode.next = afterNode
    afterNode.prev = newNode
    this.length++
    return true
  }

  // Removes the node at the specified index and returns it
  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) {
      return this.shift()
    }
    if (index === this.length - 1) {
      return this.pop()
    }
    const beforeNode = this.get(index - 1)
    const nodeToBeRemoved = beforeNode.next
    const afterNode = nodeToBeRemoved.next
    beforeNode.next = afterNode
    afterNode.prev = beforeNode
    this.length--
    return nodeToBeRemoved
  }
}

Output

const myList = new DoublyLinkedList();

console.log(myList.isEmpty()); // true
myList.push(100);
myList.push(200);
myList.push(300);
console.log(myList.length); // 3 - list length
console.log(myList.peek()); // 100 - value at head
console.log(myList.head);
/*
<ref *2> Node {
  value: 100,
  next: <ref *1> Node {
    value: 200,
    next: Node {
      value: 300,
      next: null,
      prev: [Circular *1]
    },
    prev: [Circular *2]
  },
  prev: null
}
*/

console.log(myList.pop().value); // 300 - removed tail value
console.log(myList.length); // 2 - list length

console.log(myList.shift().value); // 100 - removed head value
console.log(myList.length); // 1 - list length
console.log(myList.peek()); // 200 - value at head

console.log(myList.length); // 1 - list length
console.log(myList.unshift(100)); // 2 (updated length)
console.log(myList.peek()); // 100 - value at head

console.log(myList.length); // 2 - list length
console.log(myList.get(0).value); // 100 - value at 0 index
console.log(myList.set(0, 1000)); // true - set value to 1000 at 0 index
console.log(myList.peek()); // 1000 - value at head

console.log(myList.insert(1, 150)); // true - inserted value at 1 index to 150
console.log(myList.head);
/*
<ref *2> Node {
  value: 1000,
  next: <ref *1> Node {
    value: 150,
    next: Node {
      value: 200,
      next: null,
      prev: [Circular *1]
    },
    prev: [Circular *2]
  },
  prev: null
}
*/
console.log(myList.remove(1).value); // 150 - Node removed
console.log(myList.head);
/*
<ref *1> Node {
  value: 1000,
  next: Node {
    value: 200,
    next: null,
    prev: [Circular *1]
  },
  prev: null
}
*/

Time Complexity – O(n)

isEmpty() – O(1)
peek() – O(1)
push(value) – O(1)
pop() – O(n)
shift() – O(1)
unshift(value) – O(1)
get(index) – O(n)
set(index, value) – O(n)
insert(index, value) – O(n)
remove(index) – O(n)

Real World Applications

undo/redo functionality in applications
operating systems for managing process queues
navigation in web browsers and apps for forward/backward functionality