Double Ended Queue Deque in DSA Java

Mental Model

A deque lets you add or remove items from both ends easily, like a line where you can join or leave from front or back.

Analogy: Imagine a train with doors at both ends where passengers can get on or off from either the front or the back.

front -> [ ] -> [ ] -> [ ] -> back
↑                   ↑
add/remove front   add/remove back

Dry Run Walkthrough

Input: start empty deque, add 1 at front, add 2 at back, add 3 at front, remove from back

Goal: Show how elements are added and removed from both ends of the deque

Step 1: add 1 at front

front -> [1] -> back

Why: Adding first element at front initializes the deque

Step 2: add 2 at back

front -> [1] -> [2] -> back

Why: Adding element at back extends the deque from the end

Step 3: add 3 at front

front -> [3] -> [1] -> [2] -> back

Why: Adding at front shifts existing elements to the right

Step 4: remove from back

front -> [3] -> [1] -> back

Why: Removing from back deletes the last element

Result:

front -> [3] -> [1] -> back

Annotated Code

DSA Java

import java.util.NoSuchElementException;

class Deque {
    private static class Node {
        int value;
        Node prev, next;
        Node(int val) { value = val; }
    }

    private Node front, back;

    public boolean isEmpty() {
        return front == null;
    }

    public void addFront(int val) {
        Node newNode = new Node(val);
        if (isEmpty()) {
            front = back = newNode;
        } else {
            newNode.next = front; // link new node to current front
            front.prev = newNode; // link current front back to new node
            front = newNode;      // update front pointer
        }
    }

    public void addBack(int val) {
        Node newNode = new Node(val);
        if (isEmpty()) {
            front = back = newNode;
        } else {
            back.next = newNode; // link current back to new node
            newNode.prev = back; // link new node back to current back
            back = newNode;      // update back pointer
        }
    }

    public int removeFront() {
        if (isEmpty()) throw new NoSuchElementException("Deque is empty");
        int val = front.value;
        front = front.next;       // move front pointer forward
        if (front != null) front.prev = null; // disconnect old front
        else back = null;         // deque is empty now
        return val;
    }

    public int removeBack() {
        if (isEmpty()) throw new NoSuchElementException("Deque is empty");
        int val = back.value;
        back = back.prev;         // move back pointer backward
        if (back != null) back.next = null; // disconnect old back
        else front = null;        // deque is empty now
        return val;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node curr = front;
        while (curr != null) {
            sb.append(curr.value).append(" -> ");
            curr = curr.next;
        }
        sb.append("null");
        return sb.toString();
    }

    public static void main(String[] args) {
        Deque deque = new Deque();
        deque.addFront(1);          // step 1
        deque.addBack(2);           // step 2
        deque.addFront(3);          // step 3
        deque.removeBack();          // step 4
        System.out.println(deque);  // print final state
    }
}

newNode.next = front; front.prev = newNode; front = newNode;

link new node before current front and update front pointer

back.next = newNode; newNode.prev = back; back = newNode;

link new node after current back and update back pointer

front = front.next; if (front != null) front.prev = null; else back = null;

remove front node and update pointers accordingly

back = back.prev; if (back != null) back.next = null; else front = null;

remove back node and update pointers accordingly

Output

3 -> 1 -> null

Complexity Analysis

Time: O(1) for all add and remove operations because we only change a few pointers without traversing the deque

Space: O(n) because we store n elements in nodes linked together

vs Alternative: Compared to using arrays where adding/removing at front can be O(n), deque operations are faster and more efficient

Edge Cases

empty deque

removing from empty deque throws exception to prevent invalid operation

DSA Java

if (isEmpty()) throw new NoSuchElementException("Deque is empty");

deque with one element

removing front or back empties the deque and sets both pointers to null

DSA Java

else back = null; // and else front = null;

When to Use This Pattern

When you need to add or remove items from both ends efficiently, think of using a deque because it supports fast operations at front and back.

Common Mistakes

Mistake: Not updating both prev and next pointers when adding or removing nodes
Fix: Always update both sides of the links to keep the deque connected properly

Mistake: Not handling empty deque case when removing elements
Fix: Check if deque is empty before removing and handle pointers carefully

Summary

A deque lets you add or remove elements from both front and back quickly.

Use a deque when you need flexible access to both ends of a list.

The key is to keep track of front and back pointers and update links carefully.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A queue where elements can only be added at the rear

B. A data structure where elements can be added or removed from both ends

C. A stack where elements can only be added or removed from the top

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion from both front and rear ends.

2. Step 2: Compare with other data structures

   Unlike queues or stacks, Deque supports operations at both ends.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option B

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing Deque with stack or simple queue
• Thinking Deque allows random access like arrays
• Assuming Deque only works from one end

2. Which of the following is the correct way to create a Deque in Java using the standard library?

easy

A. Deque<Integer> dq = new ArrayDeque<>();

B. Deque<Integer> dq = new Deque<>();

C. Deque<Integer> dq = new Stack<>();

D. Deque<Integer> dq = new Queue<>();

Solution

1. Step 1: Identify valid Deque implementations in Java

   ArrayDeque implements the Deque interface and is the preferred implementation.

2. Step 2: Check syntax correctness

   ArrayDeque is instantiated with new ArrayDeque<>(), which is correct syntax.

3. Final Answer:

   Deque<Integer> dq = new ArrayDeque<>(); -> Option A

4. Quick Check:

   ArrayDeque is standard Deque implementation [OK]

Hint: Use ArrayDeque for Deque in Java [OK]

Common Mistakes:

• Using Stack which is not a Deque
• Trying to instantiate interface Queue directly
• Trying to instantiate the Deque interface directly

3. What will be the output of the following Java code?

Deque<String> dq = new ArrayDeque<>();
dq.addFirst("A");
dq.addLast("B");
dq.addFirst("C");
System.out.println(dq);

medium

A. [A, C, B]

B. [A, B, C]

C. [C, A, B]

D. [B, A, C]

Solution

1. Step 1: Trace addFirst and addLast operations

   addFirst("A") adds A at front: [A]
   addLast("B") adds B at rear: [A, B]
   addFirst("C") adds C at front: [C, A, B]

2. Step 2: Print the Deque

   Printing dq shows elements in order: [C, A, B]

3. Final Answer:

   [C, A, B] -> Option C

4. Quick Check:

   addFirst adds front, addLast adds rear [OK]

Hint: addFirst puts element at front, addLast at rear [OK]

Common Mistakes:

• Mixing order of addFirst and addLast
• Assuming addFirst adds at rear
• Confusing print output format

4. Identify the error in the following Java code using Deque:

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(10);
dq.addLast(20);
dq.removeLast();
dq.removeFirst();
dq.removeFirst();

medium

A. No error, code runs fine

B. Compilation error due to wrong method names

C. Throws NullPointerException on removeLast()

D. Throws NoSuchElementException on last removeFirst()

Solution

1. Step 1: Trace the Deque operations

   Start: empty
   addFirst(10): [10]
   addLast(20): [10, 20]
   removeLast(): removes 20 -> [10]
   removeFirst(): removes 10 -> []
   removeFirst(): tries to remove from empty Deque

2. Step 2: Identify exception on removing from empty Deque

   removeFirst() on empty Deque throws NoSuchElementException

3. Final Answer:

   Throws NoSuchElementException on last removeFirst() -> Option D

4. Quick Check:

   Removing from empty Deque throws NoSuchElementException [OK]

Hint: Removing from empty Deque throws NoSuchElementException [OK]

Common Mistakes:

• Assuming removeFirst returns null instead of exception
• Confusing method names causing compile error
• Thinking removeLast throws NullPointerException

5. You want to implement a task scheduler that processes tasks in the order they arrive but sometimes needs to prioritize urgent tasks by adding them to the front. Which Deque operation combination is best suited for this scenario?

hard

A. Use addLast() for normal tasks and addFirst() for urgent tasks

B. Use addFirst() for normal tasks and addLast() for urgent tasks

C. Use only addLast() for all tasks

D. Use only addFirst() for all tasks

Solution

1. Step 1: Understand task order requirements

   Normal tasks should be processed in arrival order (queue behavior). Urgent tasks should be processed before normal tasks (front insertion).

2. Step 2: Match Deque operations to requirements

   addLast() adds normal tasks at rear (end), preserving arrival order.
   addFirst() adds urgent tasks at front, prioritizing them.

3. Final Answer:

   Use addLast() for normal tasks and addFirst() for urgent tasks -> Option A

4. Quick Check:

   Normal at rear, urgent at front [OK]

Hint: Normal tasks rear, urgent tasks front with addLast/addFirst [OK]

Common Mistakes:

• Reversing addFirst and addLast roles
• Using only one end for all tasks losing priority
• Confusing queue and stack behavior