LEARN WITH ME

Doubly Linked List

Overview

A doubly linked list is a linear data structure consisting of nodes, where each node contains three components:

• A data field to store the value.
• A pointer to the next node in the sequence (next pointer).
• A pointer to the previous node in the sequence (previous pointer).

This structure allows traversal in both directions (forward and backward).

Key Operations on a Doubly Linked List

• Insertion:
• At the Beginning: To insert a new node at the beginning, create a new node and set its next pointer to the current head. Then update the head to point to this new node.
  Time Complexity: O(1).
• At the End: To insert a new node at the end, traverse to the end of the list, then set the next pointer of the last node to the new node.
  Time Complexity: O(n).
• After a Given Node: To insert a new node after a given node, set the new node's next pointer to the next pointer of the current node, then set the current node's next pointer to the new node.
  Time Complexity: O(n).

Insertion Operation

Insertion Code

class Node {
    int data;
    Node prev;
    Node next;

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

class DoublyLinkedList {
    Node head;

    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
        newNode.prev = last;
    }

    // Insert after a given node
    public void insertAfter(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }
        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        newNode.prev = prevNode;
        if (newNode.next != null) {
            newNode.next.prev = newNode;
        }
    }
}

                    

• Deletion:
• At the Beginning: To delete the first node, set the head to the next node of the current head.
  Time Complexity: O(1).
• At the End: To delete the last node, traverse to the second last node and set its next pointer to null.
  Time Complexity: O(n).
• By Key: To delete a node by its key, traverse the list, find the node, and adjust the pointers accordingly.
  Time Complexity: O(n).

Deletion Operation

Deletion Code

class DoublyLinkedList {
    // ... (other methods)

    // Delete at the beginning
    public void deleteAtBeginning() {
        if (head == null) {
            return;
        }
        head = head.next;
        if (head != null) {
            head.prev = null;
        }
    }

    // Delete at the end
    public void deleteAtEnd() {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.prev.next = null;
    }

    // Delete by key
    public void deleteByKey(int key) {
        Node current = head;
        while (current != null) {
            if (current.data == key) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    head = current.next;
                }
                if (current.next != null) {
                    current.next.prev = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }
}

                    

• Displaying the List: To display the elements of the doubly linked list, traverse the list from the head to the tail.

Displaying Code

class DoublyLinkedList {
    // ... (other methods)

    // Print the list from head to tail
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Print the list from tail to head
    public void printListReverse() {
        Node last = head;
        if (last == null) {
            return;
        }
        while (last.next != null) {
            last = last.next;
        }
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.prev;
        }
        System.out.println();
    }
}

                    

Applications of Doubly Linked Lists

Doubly linked lists are used in various applications, such as:

• Implementing complex data structures like deques and adjacency lists.
• In web browsers for maintaining a history of visited pages.
• In music players to navigate through playlists in both directions.
• In text editors for implementing undo and redo functionalities.

Advantages and Disadvantages

Advantages:

• Allows traversal in both directions (forward and backward).
• Can easily insert or delete nodes from both ends.
• More flexible than singly linked lists.

Disadvantages:

• More memory is required for storing an extra pointer (previous pointer) in each node.
• Complexity increases for operations compared to singly linked lists.
• Higher overhead due to additional pointers.