What is a Doubly Linked List?

A Doubly Linked List is a linked list where each node contains pointers to both the next node and the previous node.

Singly vs Doubly Linked List?

Doubly Linked Lists allow for two-way traversal and easier deletion of a node (if given a pointer to it), but they require more memory for the additional pointer.

Real-world examples of Doubly Linked Lists?

They are used in music player playlists (next/previous song), browser cache management (LRU cache), and UNDO/REDO operations.

Doubly Linked List

A doubly linked list is a linked list in which each node has two pointers: one to the next node and one to the previous node.

0 / 8 NODES

READY

List is empty

Insert a value to begin. Each node holds a value and a reference to the next one.

Value

Intuition

Like a train where each car is connected to the one in front AND the one behind. You can walk from the engine to the caboose and back.

Concept

A Doubly Linked List allows traversal in both directions. Each node contains data, a next pointer, and a prev pointer.

How it Works

Prev Pointer: Points to the previous node.
Bidirectional: Can traverse forward and backward.
Memory: Requires more memory than Singly Linked List for the extra pointer.

Step-by-Step Breakdown

Insert at Head:

Create new node.
Set new node's next to current Head.
Set current Head's prev to new node.
Update Head to new node.

When to Use

Backward Traversal: When you need to navigate back and forth (e.g., Browser History, Music Player).
Deletion: Deleting a given node is O(1) if you have the pointer to it.

When NOT to Use

Memory Constraints: Extra pointer takes more space.
Complexity: More pointers to update during insertion/deletion.

How to Identify

Problems requiring backward traversal or O(1) deletion of a known node.

Sample Problems

LRU Cache

Implement LRU Cache using Doubly Linked List and Hash Map.

Flatten Multilevel Doubly Linked List

Flatten the list vertically.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Singly Linked List

Circular Linked List

Complexity

Time (Best)

O(1)

Time (Average)

O(n)

Time (Worst)

O(n)

Space

O(n)

Doubly Linked List Code

1class Node {
2  constructor(data) {
3    this.data = data;
4    this.next = null;
5    this.prev = null;
6  }
7}
8
9class DoublyLinkedList {
10  constructor() {
11    this.head = null;
12  }
13
14  insertHead(data) {
15    const newNode = new Node(data);
16    if (this.head) {
17      this.head.prev = newNode;
18    }
19    newNode.next = this.head;
20    this.head = newNode;
21  }
22
23  insertTail(data) {
24    const newNode = new Node(data);
25    if (!this.head) {
26      this.head = newNode;
27      return;
28    }
29    let current = this.head;
30    while (current.next) {
31      current = current.next;
32    }
33    current.next = newNode;
34    newNode.prev = current;
35  }
36
37  deleteHead() {
38    if (!this.head) return;
39    this.head = this.head.next;
40    if (this.head) {
41      this.head.prev = null;
42    }
43  }
44  deleteAt(index) {
45    if (index === 0) return this.deleteHead();
46    let node = this.head;
47    for (let i = 0; i < index && node; i += 1) node = node.next;
48    if (!node) return;
49    node.prev.next = node.next;
50    if (node.next) node.next.prev = node.prev;
51  }
52}

Related Lessons

Doubly Linked List

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

LRU Cache

Flatten Multilevel Doubly Linked List

AI resume checker — match your resume to the job description

Frequently Asked Questions

What is a Doubly Linked List?

Singly vs Doubly Linked List?

Real-world examples of Doubly Linked Lists?