Skip to main content

​
Doubly Linked List

A linear data structure where each node contains a value and references to both the next and previous nodes, enabling bidirectional traversal.

​
Overview

Doubly linked lists provide efficient insertion and deletion at both ends (O(1)) and support backward traversal. The trade-off is extra memory for the previous pointer.

​
Implementation

​
Node Structure

class Node<T = number> {
  value: T;
  next: Node<T> | null = null;
  prev: Node<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}
Reference: node.ts:1-10

​
Class Definition

class DoublyLinkedList<T = number> {
  head: Node<T> | null = null;
  tail: Node<T> | null = null;
  size = 0;
  
  // ... methods
}
Reference: doubly-linked-list.ts:3-6

​
API Reference

​
push(value: T): void

Adds an element to the end of the linked list. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
// List: (1) <-> (2) <-> (3) <->
Complexity: O(1) - Direct access to tail Reference: doubly-linked-list.ts:11-13

​
insert(value: T, index: number): void

Inserts a new element at the specified position. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(3);
list.insert(2, 1);
// List: (1) <-> (2) <-> (3) <->
Parameters:
  • value: The value to insert
  • index: Position to insert at (0-based)
Complexity:
  • Insert at head: O(1)
  • Insert at tail: O(1)
  • Insert at arbitrary position: O(n)
Reference: doubly-linked-list.ts:18-76

​
pop(): Node<T> | null

Removes and returns the last element from the linked list. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
const last = list.pop(); // returns node with value 2
// List: (1) <->
Complexity: O(1) - Direct access to tail and its prev pointer Reference: doubly-linked-list.ts:81-111

​
at(index: number): Node<T> | null

Returns the element at the given index without removing it. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
const node = list.at(1); // returns node with value 2
Complexity: O(n) Reference: doubly-linked-list.ts:116-129

​
remove(value: T): void

Removes the first occurrence of an element from the list. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
list.remove(2);
// List: (1) <-> (3) <->
Complexity: O(n) Reference: doubly-linked-list.ts:134-162

​
removeAt(index: number): void

Removes an element from the specified position in the list. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
list.removeAt(1);
// List: (1) <-> (3) <->
Complexity:
  • Remove at head: O(1)
  • Remove at tail: O(1)
  • Remove at arbitrary position: O(n)
Reference: doubly-linked-list.ts:167-205

​
isEmpty(): boolean

Returns true if the list is empty, false otherwise. 
const list = new DoublyLinkedList<number>();
console.log(list.isEmpty()); // true
list.push(1);
console.log(list.isEmpty()); // false
Complexity: O(1) Reference: doubly-linked-list.ts:210-212

​
toString(): string

Returns a string representation of the list. 
const list = new DoublyLinkedList<number>();
list.push(1);
list.push(2);
list.push(3);
console.log(list.toString()); // "(1) <-> (2) <-> (3) <-> "
Complexity: O(n) Reference: doubly-linked-list.ts:217-231

​
Complexity Summary

OperationTime ComplexitySpace Complexity
pushO(1)O(1)
insert (head)O(1)O(1)
insert (tail)O(1)O(1)
insert (arbitrary)O(n)O(1)
popO(1)O(1)
atO(n)O(1)
removeO(n)O(1)
removeAt (head)O(1)O(1)
removeAt (tail)O(1)O(1)
removeAt (arbitrary)O(n)O(1)
isEmptyO(1)O(1)
toStringO(n)O(1)

​
Comparison: Singly vs Doubly Linked List

FeatureSingly Linked ListDoubly Linked List
Memory per node1 pointer2 pointers
TraversalForward onlyBidirectional
Insert at tailO(n)O(1)
Delete from tailO(n)O(1)
Delete with node referenceO(n)O(1)
Implementation complexitySimpleModerate

​
Key Characteristics

Advantages:
  • Bidirectional traversal
  • O(1) insertion/deletion at both ends
  • O(1) deletion with node reference
  • Easier implementation of certain algorithms
Disadvantages:
  • Extra memory for prev pointer (2x pointer storage)
  • More complex to maintain consistency
  • Slightly more overhead on insertions/deletions
  • Still no random access

​
Use Cases

  • Browser history: Forward and backward navigation
  • Music player: Next/previous song functionality
  • Undo/Redo: Bidirectional state navigation
  • LRU Cache: Efficient removal and reordering
  • Text editors: Cursor movement and editing

​
Implementation Details

​
Maintaining Both Pointers

When inserting a node, you must update:
  1. The new node’s next and prev pointers
  2. The previous node’s next pointer
  3. The next node’s prev pointer
// Example: Insert in middle
const current = this.at(index - 1);
const node = new Node(value);

if (current) {
  const temp = current.next;
  current.next = node;
  node.prev = current;
  node.next = temp;
  
  if (temp) {
    temp.prev = node;
  }
}

​
Edge Cases to Handle

When inserting into an empty list, both head and tail should point to the new node, and the node’s prev and next should be null.
When removing the only element, set both head and tail to null.
Always check if you’re operating at boundaries and update both head and tail pointers appropriately.
Performance Tip: For better cache locality and reduced memory overhead in scenarios where backward traversal isn’t needed, consider using a Singly Linked List instead.

Singly Linked List

Simpler alternative with forward-only traversal

Deque

Double-ended queue using doubly linked list

Build docs developers (and LLMs) love

Get started for freeTalk to us