Doubly Linked List Implementation in Java

A Doubly Linked List (DLL) is an extension of the singly linked list, where each node points to its next node and also its previous node, giving it bi-directional traversal capabilities. This added feature offers a wider range of operations and efficiencies, especially when it comes to backward navigation and specific types of insertions and deletions. In this blog post, we will dive deep into the implementation of a Doubly Linked List in Java, including its structure, methods, and functionalities. 

Doubly Linked List Implementation

Node Structure of Doubly Linked List:

First and foremost, let's understand the structure of an individual node in a DLL.

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

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

Here, prev is the pointer to the previous node, and next is the pointer to the next node. The data field stores the value of the node. 

Create Doubly Linked List Class:

class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        head = null;
        tail = null;
    }

    // Add a node to the end of the list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    // Insert a node at the beginning
    public void prepend(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }
        head.prev = newNode;
        newNode.next = head;
        head = newNode;
    }

    // Delete a node with a given value
    public void deleteNodeByValue(int data) {
        Node currentNode = head;

        while (currentNode != null) {
            if (currentNode.data == data) {
                // Handle head and tail cases
                if (currentNode.prev != null) {
                    currentNode.prev.next = currentNode.next;
                } else {
                    head = currentNode.next;
                }
                if (currentNode.next != null) {
                    currentNode.next.prev = currentNode.prev;
                } else {
                    tail = currentNode.prev;
                }
                return;
            }
            currentNode = currentNode.next;
        }
    }

    // Print the list
    public void printList() {
        Node currentNode = head;
        while (currentNode != null) {
            System.out.print(currentNode.data + " <-> ");
            currentNode = currentNode.next;
        }
        System.out.println("null");
    }
}

Testing the Doubly Linked List Implementation:

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.append(10);
        dll.append(20);
        dll.append(30);
        dll.prepend(5);

        dll.printList(); // 5 <-> 10 <-> 20 <-> 30 <-> null

        dll.deleteNodeByValue(20);
        dll.printList(); // 5 <-> 10 <-> 30 <-> null
    }
}

Output:

5 <-> 10 <-> 20 <-> 30 <-> null
5 <-> 10 <-> 30 <-> null

Benefits of Doubly Linked List

Bi-directional Traversal: Can be navigated forward and backward. 

Ease of Deletion: Easier to delete a node when the pointer to the node is given. Flexibility: Can be implemented as data structures like deque.

Conclusion

Doubly Linked Lists offer a versatile data structure option, especially when bi-directional operations are crucial. Implementing it in Java aids in understanding its operations and nuances, laying the foundation for more advanced data structures and algorithms. Whether it's navigating backward through a web browser's history or providing a flexible underlying structure for other more advanced data structures, the doubly linked list is a fundamental tool in the computer scientist's toolbox.