Doubly Linked List Implementation in Java

1. Introduction

A doubly linked list is a data structure similar to a linked list but with a twist: each node has two references, one pointing to the next node and the other pointing to the previous node. This bidirectional traversal capability provides more flexibility than singly-linked lists, though at the cost of added complexity in operations and memory consumption.

2. Implementation Steps

1. Define a Node class that will contain the data and two references: next and prev.

2. Define a DoublyLinkedList class which will:

a. Have head and tail references.

b. Provide methods like addFront(), addEnd(), delete(), display(), and isEmpty().

3. Implement these methods to manage the doubly linked list.

4. Instantiate the DoublyLinkedList class and demonstrate its functionality in a main() method.

3. Implementation in Java

class Node<T> {
    T data;
    Node<T> next, prev;
    Node(T data) {
        this.data = data;
        this.next = this.prev = null;
    }
}
class DoublyLinkedList<T> {
    private Node<T> head, tail;
    public DoublyLinkedList() {
        head = tail = null;
    }
    // Check if the list is empty
    public boolean isEmpty() {
        return head == null;
    }
    // Add element to the front of the list
    public void addFront(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
        }
    }
    // Add element to the end of the list
    public void addEnd(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    // Delete the first occurrence of the given element
    public boolean delete(T data) {
        if (isEmpty()) return false;
        Node<T> current = head;
        while (current != null && !current.data.equals(data)) {
            current = current.next;
        }
        if (current == null) return false; // Element not found
        if (current.prev != null) current.prev.next = current.next;
        else head = current.next;  // Adjust head if needed
        if (current.next != null) current.next.prev = current.prev;
        else tail = current.prev;  // Adjust tail if needed
        return true;
    }
    // Display the list from head to tail
    public void display() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        DoublyLinkedList<Integer> dll = new DoublyLinkedList<>();
        dll.addFront(10);
        dll.addEnd(20);
        dll.addFront(5);
        dll.display();  // Outputs: 5 <-> 10 <-> 20 <-> null
        dll.delete(10);
        dll.display();  // Outputs: 5 <-> 20 <-> null
    }
}

Output:

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

Explanation:

1. We define a generic Node class to represent each element of the doubly linked list. It has a data field for value storage, and next and prev fields for references to adjacent nodes.

2. The DoublyLinkedList class maintains both head and tail references, representing the start and end of the list.

3. isEmpty() checks if the list is devoid of nodes by looking at the head reference.

4. addFront() adds an element to the beginning of the list, adjusting the previous head node's prev reference if necessary.

5. addEnd() appends an element to the list, adjusting the previous tail node's next reference.

6. delete() removes the first occurrence of a specified element from the list. It handles cases where the node to be deleted is at the start, end, or middle of the list.

7. display() prints out the list in order, from head to tail.

8. In the main() method, operations on a DoublyLinkedList of Integers demonstrate the list's functionality.