Java Data Structures and Algorithms for Beginners

Doubly Linked List Data Structure

Definition and Concepts

A doubly linked list is a linear data structure consisting of a sequence of nodes, where each node contains data, a reference to the next node, and a reference to the previous node. Unlike a singly linked list, which only allows traversal in one direction, a doubly linked list enables bidirectional traversal, making operations like deletion and insertion at both ends more efficient. The first node (head) has a null previous reference, and the last node (tail) has a null next reference. You can visualize a doubly linked list as a chain of boxes, where each box holds a value and arrows point to both the next and previous boxes. This structure is ideal for applications requiring frequent insertions, deletions, or reverse traversal.

Why Use It?

A doubly linked list is used when you need a dynamic data structure that supports efficient insertions and deletions at both the head and tail, as well as bidirectional traversal. It provides more flexibility than a singly linked list by allowing navigation in both directions, which is useful for applications like undo/redo functionality or browsing history. Although it uses more memory due to the additional previous pointers, it offers O(1) time complexity for operations at the head and tail, making it suitable for dynamic datasets.

Where to Use? (Real-Life Examples)

• Undo/Redo Functionality: Text editors use doubly linked lists to track actions, allowing users to move forward (redo) or backward (undo) through the action history.
• Browser Navigation: Web browsers use doubly linked lists to manage browsing history, enabling users to navigate back and forward between visited pages.
• Music or Video Playlists: Media players use doubly linked lists to manage playlists, allowing users to move to the next or previous song efficiently.
• Deque Implementation: Doubly linked lists are used to implement double-ended queues (deques), supporting insertions and deletions at both ends.

Explain Operations

• Insert at Head: This operation adds a new node at the beginning of the list. It has a time complexity of O(1).
• Insert at Tail: This operation adds a new node at the end of the list. It has a time complexity of O(1) if a tail pointer is maintained.
• Delete at Head: This operation removes the first node. It has a time complexity of O(1).
• Delete at Tail: This operation removes the last node. It has a time complexity of O(1) if a tail pointer is maintained.
• Search: This operation finds a node with a given value. It has a time complexity of O(n).
• isEmpty: This operation checks whether the doubly linked list is empty. It has a time complexity of O(1).
• Size: This operation returns the number of nodes in the doubly linked list. It has a time complexity of O(1) if maintained.

Java Implementation

The following Java code implements a doubly linked list with basic operations, maintaining both head and tail pointers for efficiency.

public class DoublyLinkedList {
    private class Node {
        int value; // Value stored in the node
        Node next; // Reference to the next node
        Node prev; // Reference to the previous node

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

    private Node head; // Head of the doubly linked list
    private Node tail; // Tail of the doubly linked list
    private int size; // Number of nodes in the doubly linked list

    // Constructor to initialize an empty doubly linked list
    public DoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    // Insert at Head: Adds a new node at the beginning
    public void insertAtHead(int value) {
        Node newNode = new Node(value); // Creates a new node
        if (isEmpty()) { // If list is empty, sets both head and tail
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head; // Points new node to current head
            head.prev = newNode; // Points current head back to new node
            head = newNode; // Updates head to new node
        }
        size++; // Increments size
    }

    // Insert at Tail: Adds a new node at the end
    public void insertAtTail(int value) {
        Node newNode = new Node(value); // Creates a new node
        if (isEmpty()) { // If list is empty, sets both head and tail
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode; // Points current tail to new node
            newNode.prev = tail; // Points new node back to current tail
            tail = newNode; // Updates tail to new node
        }
        size++; // Increments size
    }

    // Delete at Head: Removes the first node
    public void deleteAtHead() {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The doubly linked list is empty.");
        }
        head = head.next; // Moves head to the next node
        if (head == null) { // If list becomes empty, updates tail
            tail = null;
        } else {
            head.prev = null; // Sets new head's previous to null
        }
        size--; // Decrements size
    }

    // Delete at Tail: Removes the last node
    public void deleteAtTail() {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The doubly linked list is empty.");
        }
        tail = tail.prev; // Moves tail to the previous node
        if (tail == null) { // If list becomes empty, updates head
            head = null;
        } else {
            tail.next = null; // Sets new tail's next to null
        }
        size--; // Decrements size
    }

    // Search: Checks if a value exists in the doubly linked list
    public boolean search(int value) {
        Node current = head;
        while (current != null) { // Traverses the list
            if (current.value == value) {
                return true; // Returns true if value is found
            }
            current = current.next;
        }
        return false; // Returns false if value is not found
    }

    // isEmpty: Checks if the doubly linked list is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Size: Returns the number of nodes in the doubly linked list
    public int size() {
        return size;
    }
}

How It Works

1. Initialization: The constructor initializes head and tail as null and size as 0, indicating an empty doubly linked list.
2. Insert at Head:
   • The method creates a new node with the given value.
   • If the list is empty, it sets both head and tail to the new node.
   • Otherwise, it links the new node to the current head, updates the head’s previous pointer, sets head to the new node, and increments size.
3. Insert at Tail:
   • The method creates a new node.
   • If the list is empty, it sets both head and tail to the new node.
   • Otherwise, it links the current tail to the new node, sets the new node’s previous pointer to the tail, updates tail to the new node, and increments size.
4. Delete at Head:
   • The method checks if the list is empty. If not, it moves head to the next node, sets the new head’s previous pointer to null (if not null), updates tail if the list becomes empty, and decrements size. If empty, it throws an exception.
5. Delete at Tail:
   • The method checks if the list is empty. If not, it moves tail to the previous node, sets the new tail’s next pointer to null (if not null), updates head if the list becomes empty, and decrements size. If empty, it throws an exception.
6. Search Operation: The method traverses the list from head to tail, returning true if the value is found and false if the end (null) is reached.
7. isEmpty Operation: The method returns true if size equals 0, indicating an empty list, and false otherwise.
8. Size Operation: The method returns size, which tracks the number of nodes.

Complexity Analysis Table

Note: n is the number of nodes in the doubly linked list.

Key Differences / Notes

• Doubly vs. Singly Linked List:
  • The implementation above is a doubly linked list, which allows O(1) insertions and deletions at both head and tail due to the tail pointer and bidirectional links.
  • A singly linked list only has next pointers, making tail operations O(n) unless a tail pointer is maintained, but it uses less memory.
• Doubly Linked List vs. Array:
  • Doubly linked lists support dynamic sizing and O(1) operations at both ends but have O(n) access and search times.
  • Arrays offer O(1) random access but require contiguous memory and have O(n) insertions/deletions in the middle.
• Thread Safety: The implementation is not thread-safe. For concurrent applications, use Java’s ConcurrentLinkedDeque or synchronize access.
• Java’s Built-in Doubly Linked List: Java provides LinkedList in java.util, which is a doubly linked list implementing both List and Deque interfaces.

✅ Tip: Use a doubly linked list when you need efficient insertions and deletions at both ends or bidirectional traversal, such as in navigation systems or deques.

⚠ Warning: Doubly linked lists use more memory than singly linked lists due to the additional previous pointers. Ensure memory constraints are considered for large datasets.

Exercises

1. Reverse a Doubly Linked List: Write a Java program that reverses the doubly linked list using the implementation above. Test it with lists of varying sizes.
2. Bidirectional Traversal: Extend the implementation to include methods for printing the list in both forward (head to tail) and backward (tail to head) directions. Test with a sample list.
3. Insert After Value: Add a method to insert a new node after the first occurrence of a given value. Test it with cases where the value exists and does not exist.
4. Deque Implementation: Use the doubly linked list to implement a double-ended queue (deque) with methods for adding and removing elements at both ends. Test with a sequence of operations.
5. Browser History Simulator: Create a program that simulates a browser’s navigation history using the doubly linked list. Allow users to add pages (insert at tail), navigate back (delete at tail), and navigate forward (re-insert).