DSA Basics: Doubly Linked List

A doubly linked list is a linked list where each node points in two directions.

Each node stores:

• value
• next
• prev

null <- [12] <-> [24] <-> [36] -> null

Why add prev?

A singly linked list can only move forward. A doubly linked list can move forward and backward.

That extra link makes some operations easier, but each node uses more memory and every mutation must update two directions correctly.

Insert between two nodes

function insertBetween(left, right, node) {
	node.prev = left;
	node.next = right;
	left.next = node;
	right.prev = node;
}

Where doubly linked lists show up

• LRU cache
• Browser history
• Music playlist navigation
• Editor cursor movement
• Deques

Complexity

• Move next: O(1)
• Move previous: O(1)
• Search: O(n)
• Insert near known node: O(1)
• Delete known node: O(1)

Practice links

• LeetCode Linked List problems
• NeetCode practice roadmap

Use the visualizer below to move in both directions.