Doubly Linked List

A Doubly Linked List (DLL) is a data structure consisting of a sequence of elements, called “nodes,” where each node points to both its next and previous nodes.

This bidirectional linking allows more flexibility than a Singly Linked List.

Structure of a Node

A node in a DLL contains:

• Data: The element value
• Next: A reference to the next node
• Prev: A reference to the previous node

Implementing Doubly Linked List

Below is the complete implementation of a Doubly Linked List in Java.

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

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

public class DoublyLinkedList {
    Node head;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }

    public void delete(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                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;
        }
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        
        System.out.print("List after adding elements: ");
        list.display();  // Output: 1 2 3

        list.delete(2);
        System.out.print("List after deleting 2: ");
        list.display();  // Output: 1 3
    }
}

Advantages of Doubly Linked List

1. Bidirectional Traversal: Allows easy navigation both forward and backward.
2. Efficient Deletions: Deletion of nodes is more efficient as you can access previous nodes directly, useful in stacks and queues with deque operation.
3. Easy Reverse Look-up: Simplifies algorithms requiring reverse look-up, like some forms of sorting and navigation.
4. Tail Operations: Allows quick access to the last element, useful for certain algorithms and data storage types.
5. Insertions at Both Ends: Efficient insertions or deletions at both start and end without traversing.
6. No Reversal for Backtracking: Doesn’t need to be reversed for backward traversal, unlike singly linked lists.
7. Advanced Data Structures: Serves as the basis for more complex data structures like doubly-ended queues (deque) and certain types of binary trees.

Using Built-in Doubly Linked Lists in Java

Java’s standard library provides a ready-to-use class for the doubly linked list data structure, making it straightforward to utilize this powerful and flexible data type.

1. LinkedList Class

The LinkedList class in the java.util package is implemented as a doubly-linked list. This means each element (or node) has a reference to both its next element and its previous element.

Key Methods:

• add(E e): Appends the specified element to the end of the list.
• add(int index, E element): Inserts the specified element at the specified position in the list.
• get(int index): Returns the element at the specified position.
• remove(): Retrieves and removes the head (first element) of the list.
• removeLast(): Removes and returns the last element from this list.
• listIterator(): Returns a list iterator over the elements in this list (in proper sequence).

2. Using LinkedList as a Doubly Linked List

The inherent nature of LinkedList as a doubly-linked list allows for bidirectional traversal, which can be achieved using the ListIterator.

import java.util.LinkedList;
import java.util.ListIterator;

public class DoublyLinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> doublyList = new LinkedList<>();
        
        // Add elements
        doublyList.add("A");
        doublyList.add("B");
        doublyList.add("C");

        // Using ListIterator for bidirectional traversal
        ListIterator<String> iterator = doublyList.listIterator();
        
        // Forward traversal
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // Reverse traversal
        while (iterator.hasPrevious()) {
            System.out.println(iterator.previous());
        }
    }
}

3. Takeaways

• The LinkedList class is the primary and most straightforward way to use a doubly linked list in Java’s standard library.
• LinkedList is versatile and covers various use cases beyond just acting as a list. For instance, it can be used as a stack or a queue, thanks to its doubly-linked nature.
• If you need to frequently add or remove elements from the beginning or end, LinkedList can be a better choice than ArrayList due to its O(1) insertion and deletion operations at both ends.

To sum it up, Java’s LinkedList class is a robust implementation of the doubly linked list data structure. It offers a range of methods that make it easy to perform common operations, and its bidirectional traversal capabilities are particularly powerful.