Doubly Linked Lists

A doubly linked list is an enhanced version of a linked list where each node contains references to both the next and previous nodes in the sequence. This bidirectional linking provides additional flexibility but requires more memory per node.

Structure

class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
		this.previous = null;
	}
}

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

Visual Representation

null <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> null
       ^                                                            ^
       head                                                        tail

Advantages Over Singly Linked Lists

1. Bidirectional traversal
2. More efficient deletion operations
3. Can traverse backwards from any node
4. O(1) deletion when node reference is known
5. Easier implementation of certain algorithms

Disadvantages

1. Extra memory for previous pointers
2. Additional complexity in implementation
3. More complex insertion and deletion operations

Core Operations

Insertion

append(value) {
    const newNode = new Node(value);

    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.previous = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }

    this.length++;
    return this;
}

Deletion

remove(node) {
    if (!node.previous) {
        // Node is head
        this.head = node.next;
    } else {
        node.previous.next = node.next;
    }

    if (!node.next) {
        // Node is tail
        this.tail = node.previous;
    } else {
        node.next.previous = node.previous;
    }

    this.length--;
    return true;
}

Traversal

// Forward traversal
traverse() {
    let current = this.head;
    while (current) {
        console.log(current.value);
        current = current.next;
    }
}

// Backward traversal
reverseTraverse() {
    let current = this.tail;
    while (current) {
        console.log(current.value);
        current = current.previous;
    }
}

Complete Implementation

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

	// Add to end
	append(value) {
		const newNode = new Node(value);

		if (!this.head) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			newNode.previous = this.tail;
			this.tail.next = newNode;
			this.tail = newNode;
		}

		this.length++;
		return this;
	}

	// Add to beginning
	prepend(value) {
		const newNode = new Node(value);

		if (!this.head) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			newNode.next = this.head;
			this.head.previous = newNode;
			this.head = newNode;
		}

		this.length++;
		return this;
	}

	// Delete first node
	deleteHead() {
		if (!this.head) return null;

		const deletedHead = this.head;

		if (this.head === this.tail) {
			this.head = null;
			this.tail = null;
		} else {
			this.head = this.head.next;
			this.head.previous = null;
		}

		this.length--;
		return deletedHead;
	}

	// Delete last node
	deleteTail() {
		if (!this.tail) return null;

		const deletedTail = this.tail;

		if (this.head === this.tail) {
			this.head = null;
			this.tail = null;
		} else {
			this.tail = this.tail.previous;
			this.tail.next = null;
		}

		this.length--;
		return deletedTail;
	}

	// Find node by value
	find(value) {
		let current = this.head;

		while (current) {
			if (current.value === value) {
				return current;
			}
			current = current.next;
		}

		return null;
	}
}

Time Complexities

Operation	Time Complexity
Access	O(n)
Search	O(n)
Insertion	O(1)*
Deletion	O(1)*

* When inserting/deleting at a known position. If you need to search first, it becomes O(n).

Space Complexity

O(n) - where n is the number of nodes in the list

Common Use Cases

1. Browser History

   • Forward and backward navigation
   • Recently visited pages

2. Undo/Redo Operations

   • Text editors
   • Image editing software

3. Music Players

   • Next/previous track functionality
   • Playlist navigation

4. Cache Implementation

   • LRU (Least Recently Used) Cache
   • MRU (Most Recently Used) Cache

Practice Problems

1. Implement a music player playlist
2. Create a browser history system
3. Design an undo/redo mechanism
4. Implement LRU cache
5. Convert binary tree to doubly linked list

Additional Resources

• Visualgo - Linked List Visualization
• GeeksforGeeks - Doubly Linked List