1. Introduction

A Doubly LinkedList is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. This blog post will provide a comprehensive implementation of a Doubly LinkedList in Java, covering common operations like insertion (at the beginning, end, and a specified position), deletion (from beginning, end, and a specified position), and traversal.

2. Program Steps

1. Define the Node class representing individual elements of the Doubly LinkedList.

2. Create a DoublyLinkedList class that houses methods for various operations.

3. Implement the various operations and test the DoublyLinkedList.

3. Code Program

// Step 1: Define the Node class
class Node {
    int data;
    Node prev;
    Node next;

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

// Step 2: Define the DoublyLinkedList class
class DoublyLinkedList {
    Node head;

    // Insert a new node 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 a new node 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 a new node after a given node
    public void insertAfter(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("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;
        }
    }

    // Delete a node from the list
    public void delete(Node delNode) {
        if (head == null || delNode == null) {
            return;
        }
        if (head == delNode) {
            head = head.next;
        }
        if (delNode.next != null) {
            delNode.next.prev = delNode.prev;
        }
        if (delNode.prev != null) {
            delNode.prev.next = delNode.next;
        }
    }

    // Display the list
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        // Step 3: Implement and test the DoublyLinkedList
        DoublyLinkedList list = new DoublyLinkedList();
        list.insertAtEnd(10);
        list.insertAtBeginning(5);
        list.insertAtEnd(15);
        list.insertAfter(list.head.next, 12);
        list.display();

        list.delete(list.head.next);
        list.display();
    }
}

Output:

5 10 12 15
5 12 15

4. Step By Step Explanation

Step 1: We define the Node class. Each Node consists of a data field and two pointers, prev and next.

Step 2: In the DoublyLinkedList class:

1. insertAtBeginning: Inserts a new node at the start.

2. insertAtEnd: Adds a new node at the end of the list.

3. insertAfter: Places a new node after a specified node.

4. delete: Removes a given node from the list.

5. display: Traverses and prints the entire list.

Step 3: We test the DoublyLinkedList operations in the Main class. The test involves adding nodes at the beginning, end, and after a specific node. It also demonstrates node deletion.

The output displays the nodes of the Doubly LinkedList after each significant operation.