Doubly Linked Lists: Implementation and Operations

1. The Doubly Linked List: A Two-Way Street

A doubly linked list enhances the simple node structure we used before. Each node now contains three pieces of information:

1. Data: The value stored in the node.
2. Next: A reference to the next node in the sequence.
3. Prev: A reference to the previous node in the sequence.

This prev pointer is the game-changer. It allows us to traverse the list backward, making operations like deleting the last node much faster. The first node's prev is null, and the last node's next is null.

To get a formal introduction to this structure and see how it's defined in Java, please read the first part of the following article.

2. Building the Doubly Linked List in Java

Based on the reading, our initial structure in Java will look like this. We'll use a private inner Node class to keep it encapsulated, just as we did with the singly linked list.

public class DoublyLinkedList {

    private Node head;
    private Node tail;
    private int size;

    public DoublyLinkedList() {
        this.size = 0;
    }

    // Our methods will go here.

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

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

3. Traversal: The Bidirectional Advantage

One of the most apparent benefits of a doubly linked list is the ability to traverse in both directions. We can start from the head and move forward using next, or start from the tail and move backward using prev.

Here are the traversal methods we can add to our class:

    public void displayForward() {
        Node temp = head;
        System.out.print("Forward: HEAD -> ");
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

    public void displayBackward() {
        Node temp = tail;
        System.out.print("Backward: TAIL -> ");
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.prev;
        }
        System.out.println("NULL");
    }

4. Insertion Operations

Inserting a node in a doubly linked list requires more pointer adjustments than in a singly linked list. For an insertion between two nodes (say P and N), you must update four references:

• P.next
• N.prev
• The new node's prev
• The new node's next

Let's explore the three main insertion scenarios.

For a more dynamic, step-by-step explanation of the logic, the "take U forward" video is an excellent supplement.

Let's summarize and implement these methods.

insertAtBeginning (O(1))

1. Create the newNode.
2. If the list is empty, head and tail both point to newNode.
3. Otherwise, set newNode.next to the current head, head.prev to newNode, and update head to newNode.

insertAtEnd (O(1))

1. Create the newNode.
2. If the list is empty, this is the same as inserting at the beginning.
3. Otherwise, set tail.next to newNode, newNode.prev to the current tail, and update tail to newNode.

insertAtPosition (O(N))

This is the most complex case. After traversing to the correct position:

1. Find the node currently at that position (current) and the node before it (previous).
2. Set newNode.next to current and newNode.prev to previous.
3. Update previous.next to newNode.
4. Update current.prev to newNode.

5. Deletion Operations

Deletion is where the prev pointer truly shines. We no longer need to traverse the list to find the second-to-last element to delete the tail.

Let's break down the logic.

deleteAtBeginning (O(1))

1. Handle empty and single-node list edge cases.
2. Set head to head.next.
3. Set the new head.prev to null.

deleteAtEnd (O(1)) - The big win!

1. Handle empty and single-node list edge cases.
2. Set tail to tail.prev.
3. Set the new tail.next to null.

deleteAtPosition (O(N))

1. Traverse to find the node to be deleted (current).
2. The core logic is to "bypass" the node: current.prev.next = current.next;
3. Then, update the backward link: current.next.prev = current.prev;

6. Complexity Analysis

Let's compare the complexities of singly and doubly linked lists.

The main trade-offs for a doubly linked list are:

• Increased Memory: Each node requires extra space for the prev pointer.
• More Complex Operations: Insertions and deletions require updating more pointers, increasing the chance of bugs if not handled carefully.

Conclusion

You have now learned how to implement a doubly linked list, a fundamental data structure that overcomes a major limitation of its singly linked counterpart.

Key Takeaways:

• A doubly linked list node contains data, a next pointer, and a prev pointer.
• The prev pointer enables bidirectional traversal and, most importantly, allows for O(1) deletion from the tail.
• Insertion and deletion operations in the middle of the list involve updating four pointers, requiring careful implementation.
• The primary trade-off is slightly higher memory usage per node and more complex pointer management.

Preview of the next lesson:
Now that we have solid implementations of both singly and doubly linked lists, we will tackle a classic interview problem: reversing a linked list. We will explore both iterative and recursive solutions, which are excellent tests of your pointer manipulation skills.