Speed:

Doubly Linked List

Search: O(n)Insert: O(1) at endsDelete: O(1) at endsBidirectional

🔗Doubly Linked List Operations

Each node contains data and two pointers: next (forward) and prev (backward). Enables bidirectional traversal.

Insert at beginning, end, or specific position. Update up to 4 pointers to maintain forward and backward links.

Traverse from head or tail to find elements. Bidirectional search can optimize performance in some scenarios.

Remove nodes by updating both next and prev pointers of adjacent nodes. Handle head and tail updates appropriately.

🔧Setup - Node Structure

A Doubly Linked List extends the concept of a singly linked list by adding a previous pointer to each node. This bidirectional connectivity allows traversal in both forward and backward directions. Each node contains three components: the data value, a next pointer to the following node, and a prev pointer to the previous node. The list maintains references to both head and tail nodes, enabling efficient operations at both ends. This structure provides flexibility at the cost of additional memory overhead for the extra pointer.

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

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

➕Insert - Add Operation

Insertion in a doubly linked list requires careful pointer management due to the bidirectional nature. There are three main scenarios: inserting at the beginning, at the end, or at a specific position. When inserting at the beginning, we update the head pointer and set the new node's next to the current head, while updating the old head's prev pointer. For end insertion, we use the tail pointer for direct access. Middle insertion requires traversing to the position and updating up to four pointers: the new node's next and prev, plus the adjacent nodes' connecting pointers. This complexity provides the benefit of O(1) insertion at both ends.

insertAtPosition(data, position) {
    if (position < 0 || position > this.size) return false;
    
    const newNode = new Node(data);
    
    if (position === 0) {
        // Insert at beginning
        if (this.head === null) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
    } else if (position === this.size) {
        // Insert at end
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    } else {
        // Insert in middle
        let current = this.head;
        for (let i = 0; i < position; i++) {
            current = current.next;
        }
        
        newNode.next = current;
        newNode.prev = current.prev;
        current.prev.next = newNode;
        current.prev = newNode;
    }
    
    this.size++;
    return true;
}

🔍Search - Find Operation

Search operation in a doubly linked list offers unique advantages due to bidirectional traversal capability. While the basic search still requires O(n) time complexity in the worst case, the ability to start from either head or tail can provide optimizations. For instance, if searching for a value likely to be in the latter half of the list, starting from the tail and moving backward using prev pointers can reduce the average search time. Additionally, the bidirectional nature enables more sophisticated search strategies and makes it easier to implement operations that require knowledge of neighboring elements.

search(data) {
    let current = this.head;
    let position = 0;
    
    while (current !== null) {
        if (current.data === data) {
            return { found: true, position: position, node: current };
        }
        current = current.next;
        position++;
    }
    
    return { found: false, position: -1, node: null };
}

// Optimized search (can start from either end)
searchOptimized(data, fromTail = false) {
    if (fromTail) {
        let current = this.tail;
        let position = this.size - 1;
        
        while (current !== null) {
            if (current.data === data) {
                return { found: true, position: position, node: current };
            }
            current = current.prev;
            position--;
        }
    } else {
        return this.search(data);
    }
    
    return { found: false, position: -1, node: null };
}

🗑️Delete - Remove Operation

Deletion in a doubly linked list requires updating multiple pointers to maintain the bidirectional integrity. Three scenarios exist: deleting the first node (update head and the new first node's prev pointer), deleting the last node (update tail and the new last node's next pointer), and deleting a middle node (update both adjacent nodes' pointers). The key advantage is that once you have a reference to the node to delete, removal is O(1) since you can directly access both neighboring nodes through the prev and next pointers. This eliminates the need to traverse from the head to find the predecessor, as required in singly linked lists.

deleteAtPosition(position) {
    if (position < 0 || position >= this.size || this.head === null) {
        return false;
    }
    
    let nodeToDelete;
    
    if (position === 0) {
        // Delete first node
        nodeToDelete = this.head;
        this.head = this.head.next;
        
        if (this.head !== null) {
            this.head.prev = null;
        } else {
            this.tail = null; // List becomes empty
        }
    } else if (position === this.size - 1) {
        // Delete last node
        nodeToDelete = this.tail;
        this.tail = this.tail.prev;
        this.tail.next = null;
    } else {
        // Delete middle node
        let current = this.head;
        for (let i = 0; i < position; i++) {
            current = current.next;
        }
        
        nodeToDelete = current;
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }
    
    this.size--;
    return true;
}