Doubly Linked List

A doubly linked list is a common data structure similar to the singly linked list, but each node contains an additional pointer that points to the previous node in addition to the one pointing to the next. This structure allows for bidirectional traversal within a doubly linked list, meaning nodes can be accessed either from front-to-back or back-to-front.

Each node in a doubly linked list consists of three main components:

1. Data Element: Used to store specific data, which can be any type such as integers, characters, objects, etc.
2. Pointer to the Previous Node: Points to the preceding node within the list.
3. Pointer to the Next Node: Points to the succeeding node in the list.

The characteristics of a doubly linked list include:

• Nodes in the list do not need to be stored contiguously in memory; they are connected via pointers.
• The size of the list can be dynamically adjusted, allowing for insertion or deletion of nodes at any position.
• Traversal is possible from front-to-back or back-to-front because each node possesses pointers to both its previous and next nodes.

Operations supported by a doubly linked list include:

• Traversal: Iterate through the list starting from the head node forward, or start from the tail node backward.
• Insertion Node: Insert a new node at a specified position.
• Deletion Node: Remove a node located at a specific position.
• Search Node: Locate nodes within the list based on particular conditions.

The advantage of a doubly linked list over a singly linked list lies in its ability to facilitate easier backward traversal and deletion operations, although it requires more memory space to store these additional pointers. In practical applications, doubly linked lists are often used when frequent insertion and deletion at arbitrary positions are required alongside the need for bidirectional traversal, offering greater flexibility and efficiency.

Code Implementation

::: code-tabs
@tab Java

public class DoublyLinkedList<T> {
    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }
    
    // Reference to the first node in the list
    public Node headNode; 
    
    // Keeps track of the number of nodes currently in the list
    public int size; 

    /**
     * Constructs a new DoublyLinkedList with an empty initial state.
     */
    public DoublyLinkedList() {
        this.headNode = null;
    }

    /**
     * Checks if the linked list is empty.
     * @return true if the list contains no nodes, false otherwise.
     */
    public boolean isEmpty() {
        // If head node is null, return true (empty)
        if (headNode == null) 
            return true;
        
        // Otherwise, it's not empty
        return false;   
    }

    /**
     * Inserts a new element at the beginning of the list.
     * @param data The value to be inserted into the node.
     */
    public void insertAtHead(T data) { 
        Node newNode = new Node();
        newNode.data = data;
        
        // New node points to current head
        newNode.nextNode = this.headNode; 
        
        // Current head's previous pointer is set to null initially (handled below if not null)
        newNode.prevNode = null;

        // If there was an existing head, update its prev pointer
        if (headNode != null) 
            headNode.prevNode = newNode;
        
        // Update the new node as the current head
        this.headNode = newNode; 
        
        incrementSize();
    } 

    /**
     * Increments the size counter.
     */
    private void incrementSize() {
        size++;
    }

    public void printList() { 
        // Check if list is empty before printing
        if (isEmpty()) { 
            System.out.println("List is Empty!"); 
            return; 
        } 
        
        Node temp = headNode;
        
        // Print the format indicating a linked structure starting with null reference
        System.out.print("List : null <- "); 

        while (temp.nextNode != null) { 
            // Print current data followed by arrow symbol and space
            System.out.print(temp.data.toString() + " <-> "); 
            temp = temp.nextNode; 
        } 
        
        // Print the last node's data pointing to null
        System.out.println(temp.data.toString() + " -> null"); 
    }

    /**
     * Deletes the first element of the list.
     */
    public void deleteAtHead(){ 
        if(isEmpty()) 
            return; 
            
        headNode = headNode.nextNode; 
        
        // Ensure the new head's previous pointer is cleared (though it might be null already)
        headNode.prevNode = null; 

        decrementSize();
    } 
    
    /**
     * Decrements the size counter.
     */
    private void decrementSize() { 
        size--; 
    }

    /**
     * Deletes a node with specific data value from anywhere in the list.
     * @param data The value of the node to be deleted.
     */
    public void deleteByValue(T data) { 
        if (isEmpty()) 
            return; 

        Node currentNode = this.headNode; 
        
        // Check if head matches target data immediately
        if (currentNode.data.equals(data)) { 
            deleteAtHead(); 
            return; 
        }

        while (currentNode != null) { 
            // Compare current node's data with the target value using equals for object safety
            if (data.equals(currentNode.data)) { 
                currentNode.prevNode.nextNode = currentNode.nextNode; 

                // If there is a next node, update its previous pointer to bypass deleted node
                if(currentNode.nextNode != null) 
                    currentNode.nextNode.prevNode = currentNode.prevNode; 

                decrementSize(); 
            } 
            
            currentNode = currentNode.nextNode; 
        } 
    } 
}

:::