Understand the structure of doubly linked lists, implement core operations, and compare their performance with singly linked lists.

Doubly Linked List

A doubly linked list is a sequence of nodes connected in both directions. Each node stores a value and two references:

next points to the following node.
prev points to the preceding node.

The list keeps a head reference to its first node and a tail reference to its last node. The head's prev and the tail's next both point to null.

Key Property: Bidirectional

Unlike a singly linked list, a doubly linked list can be traversed from the head to the tail or from the tail to the head. The extra link also makes removing a known node easier because its previous neighbor is immediately available.

Anatomy of a Doubly Linked List

Component	Description
Node	Stores a value plus `next` and `prev` references.
Head	References the first node. Its `prev` is `null`.
Tail	References the last node. Its `next` is `null`.
Length	Tracks the number of nodes for fast boundary checks.

The second pointer increases memory usage, but it enables backward traversal and constant-time updates at both ends.

Defining the Node and List

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;
  }
}

Core Operations

1. Adding to the End (`push`)

Create a node, connect the current tail to it, connect it back to the current tail, and then update tail. If the list is empty, the new node becomes both head and tail.

push(val) {
  const newNode = new Node(val);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }
  this.length++;
  return this;
}

Time Complexity: $O(1)$

2. Removing from the End (`pop`)

Because the tail has a prev reference, the new tail is available without traversing the list.

pop() {
  if (!this.tail) return null;
  const removedNode = this.tail;

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.tail = removedNode.prev;
    this.tail.next = null;
    removedNode.prev = null;
  }

  this.length--;
  return removedNode;
}

Time Complexity: $O(1)$

3. Adding to the Beginning (`unshift`)

Connect the new node to the current head in both directions, then make it the new head.

unshift(val) {
  const newNode = new Node(val);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
  }
  this.length++;
  return this;
}

Time Complexity: $O(1)$

4. Removing from the Beginning (`shift`)

Save the head, advance head to the next node, and clear the links that connected the removed node.

shift() {
  if (!this.head) return null;
  const removedNode = this.head;

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = removedNode.next;
    this.head.prev = null;
    removedNode.next = null;
  }

  this.length--;
  return removedNode;
}

Time Complexity: $O(1)$

5. Accessing and Updating by Index (`get` and `set`)

An index in the first half is reached from the head. An index in the second half is reached from the tail. This does not change the $O(n)$ worst case, but it can reduce the number of nodes visited.

get(index) {
  if (index < 0 || index >= this.length) return null;
  let current;

  if (index <= this.length / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) current = current.next;
  } else {
    current = this.tail;
    for (let i = this.length - 1; i > index; i--) current = current.prev;
  }

  return current;
}

set(index, val) {
  const node = this.get(index);
  if (!node) return false;
  node.val = val;
  return true;
}

Time Complexity: $O(n)$

6. Inserting at Any Position (`insert`)

For a middle insertion, find the node currently at the index and connect the new node between it and its previous neighbor. All four affected links must remain consistent.

insert(index, val) {
  if (index < 0 || index > this.length) return false;
  if (index === 0) return Boolean(this.unshift(val));
  if (index === this.length) return Boolean(this.push(val));

  const nextNode = this.get(index);
  const prevNode = nextNode.prev;
  const newNode = new Node(val);

  prevNode.next = newNode;
  newNode.prev = prevNode;
  newNode.next = nextNode;
  nextNode.prev = newNode;
  this.length++;
  return true;
}

Time Complexity: $O(n)$ to locate the position and $O(1)$ to reconnect the nodes.

7. Removing from Any Position (`remove`)

For a middle removal, connect the target node's previous neighbor directly to its next neighbor, update the reverse link, and detach the removed node.

remove(index) {
  if (index < 0 || index >= this.length) return null;
  if (index === 0) return this.shift();
  if (index === this.length - 1) return this.pop();

  const removedNode = this.get(index);
  removedNode.prev.next = removedNode.next;
  removedNode.next.prev = removedNode.prev;
  removedNode.next = null;
  removedNode.prev = null;
  this.length--;
  return removedNode;
}

Time Complexity: $O(n)$ by index. If the node reference is already known, unlinking it is $O(1)$ .

Singly vs. Doubly Linked Lists

Feature	Singly Linked List	Doubly Linked List
Traversal	Forward only	Forward and backward
Links per node	One: `next`	Two: `next` and `prev`
Memory usage	Lower	Higher
Remove tail	$O(n)$	$O(1)$
Remove a known node	Previous node must be found	Adjacent nodes are directly available
Implementation	Simpler	More pointer updates

Pointer Safety

Every connection has two sides. When inserting or removing a node, update both the forward (next) and backward (prev) references so the list remains valid in either direction.

Performance Summary

Operation	Time Complexity
Push at tail	$O(1)$
Pop from tail	$O(1)$
Unshift at head	$O(1)$
Shift from head	$O(1)$
Get or set by index	$O(n)$
Insert or remove by index	$O(n)$
Remove a known node	$O(1)$
Search	$O(n)$

Real-World Applications

Doubly linked lists are useful when movement in both directions matters:

Browser navigation: move backward and forward through visited pages.
Undo and redo history: move between earlier and later application states.
Dynamic collections: add or remove items without reorganizing an entire array.

Key Takeaways

Every node stores a value, a next reference, and a prev reference.
Bidirectional links allow traversal from either end of the list.
Push, pop, shift, and unshift all run in $O(1)$ time.
Index-based access still takes $O(n)$ because linked lists do not provide random access.
The extra pointer improves navigation and deletion flexibility at the cost of additional memory and more careful pointer management.

Doubly Linked List

On this page