Implementing a Deque with a Doubly Linked List

1. What is a Deque?

A deque is a linear collection of elements that allows insertion and deletion at both ends—the front and the rear. This flexibility makes it a powerful tool.

The primary operations are:

• insertFront(): Adds an item to the front of the deque.
• insertRear(): Adds an item to the back of the deque.
• deleteFront(): Removes an item from the front of the deque.
• deleteRear(): Removes an item from the back of the deque.

Why is a doubly linked list the perfect choice for this? Because each node in a doubly linked list holds pointers to both the next and the previous node. By maintaining pointers to the first (front) and last (rear) nodes of the list, we can access both ends directly and perform all four operations in constant time, O(1).

2. Building the Deque: The Node and Class Structure

First, let's define the building blocks. We need a Node class that can store data and link to its neighbors in both directions. We also need a Deque class that will hold references to the front and rear nodes.

Here's the essential structure in Java:

// The node of a doubly linked list
class Node {
    int data;
    Node prev;
    Node next;

    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// A Deque class implemented using a doubly linked list
class MyDeque {
    private Node front;
    private Node rear;
    private int size; // Good practice to keep track of size

    public MyDeque() {
        front = null;
        rear = null;
        size = 0;
    }
}

Now, let's implement the core operations one by one.

3. Implementing the Deque Operations

We will now walk through the logic for each of the four main operations. The key is to correctly manage the front, rear, next, and prev pointers for each case.

a) Insertion at the Front (insertFront)

1. Create a newNode with the given data.
2. If the deque is empty (front == null), both front and rear should point to the newNode.
3. If the deque is not empty, we need to wire the newNode in at the beginning:
   • newNode.next points to the old front.
   • The old front.prev points back to the newNode.
   • Finally, update front to be the newNode.

b) Insertion at the Rear (insertRear)

This is the mirror image of insertFront.

1. Create a newNode.
2. If the deque is empty, both front and rear point to the newNode.
3. If the deque is not empty:
   • newNode.prev points to the old rear.
   • The old rear.next points forward to the newNode.
   • Update rear to be the newNode.

c) Deletion from the Front (deleteFront)

1. Check for underflow: If the deque is empty (front == null), there's nothing to delete.
2. If there is only one element (front == rear), set both front and rear to null.
3. If there are multiple elements:
   • Move front to the next node: front = front.next.
   • The new front's prev pointer must be set to null to sever the link to the old front node.

d) Deletion from the Rear (deleteRear)

Symmetrically, for deletion from the rear:

1. Check for underflow.
2. If there is only one element, set both front and rear to null.
3. If there are multiple elements:
   • Move rear to the previous node: rear = rear.prev.
   • The new rear's next pointer must be set to null.

4. Code Consolidation and a Pro Tip for Interviews

Putting it all together, we get a complete MyDeque class. The resource from GeeksforGeeks provides a full implementation including helper methods, which is a great reference.

Pro Tip: Simplifying Edge Cases with a Dummy Node

You might have noticed that our insertion and deletion logic requires if/else statements to handle empty lists or single-element lists. In an interview, demonstrating a way to write cleaner, more robust code is a huge plus. This is where the dummy node (or sentinel node) technique, which you specifically asked about, comes in.

A dummy node is a placeholder node that is never removed from the list. It doesn't hold any meaningful data. We can structure our list as a circular doubly linked list where the dummy node's next pointer points to the front of the deque, and its prev pointer points to the rear. The front's prev and the rear's next both point back to the dummy node.

Why is this better?

• No more nulls: Every "real" node always has a non-null prev and next (they point to another real node or the dummy node).
• No more edge cases: An "empty" list is one where the dummy node just points to itself. The logic for insertion and deletion becomes the same whether the list is empty, has one element, or has many elements. This eliminates almost all if (front == null) checks.

With a dummy node, insertFront becomes a call to addBefore(dummy.next, data) and insertRear becomes addBefore(dummy, data). This is a very elegant solution that showcases a deep understanding of linked list manipulations.

Conclusion

Great job! You have now learned how to implement a deque from first principles using a doubly linked list. This is a foundational skill that reinforces your understanding of pointers and data structure design.

Key Takeaways:

• A Deque allows O(1) insertion and deletion at both the front and rear.
• A doubly linked list is the natural data structure to implement a deque, using front and rear pointers for direct access.
• Careful pointer manipulation is required for the insert and delete operations, especially handling the prev and next links.
• The dummy node technique is a powerful way to simplify code and eliminate edge-case handling for linked list operations, a valuable pattern to know for technical interviews.

Preview of the next lesson:
Now that you have built a deque and understand its O(1) efficiency, it's time to put it to use. In the next lesson, we will tackle a classic and challenging interview problem: "Sliding Window Maximum". You will see how the unique properties of the deque make it the perfect tool to solve this problem efficiently.