Dequeue Using Linked List in DSA Java

Mental Model

A dequeue lets you add or remove items from both ends quickly using a linked list.

Analogy: Think of a double-ended queue like a train with cars that can be added or removed from the front or back easily.

null ← 1 ↔ 2 ↔ 3 -> null
↑front                 ↑rear

Dry Run Walkthrough

Input: Start with empty dequeue, then enqueue 10 at rear, enqueue 20 at front, dequeue from rear, enqueue 30 at rear

Goal: Show how elements are added and removed from both ends in a linked list based dequeue

Step 1: enqueue 10 at rear on empty dequeue

null ← [10] -> null
↑front/rear

Why: First element becomes both front and rear

Step 2: enqueue 20 at front

null ← [20] ↔ 10 -> null
↑front       ↑rear

Why: New node added before current front, front pointer updated

Step 3: dequeue from rear

null ← 20 -> null
↑front/rear

Why: Remove rear node (10), rear pointer moves to previous node

Step 4: enqueue 30 at rear

null ← 20 ↔ [30] -> null
↑front       ↑rear

Why: Add new node after rear, rear pointer updated

Result:

null ← 20 ↔ 30 -> null
↑front       ↑rear

Annotated Code

DSA Java

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

class Dequeue {
    Node front, rear;

    Dequeue() {
        front = null;
        rear = null;
    }

    // Add at rear
    void enqueueRear(int data) {
        Node newNode = new Node(data);
        if (rear == null) { // empty dequeue
            front = rear = newNode;
            return;
        }
        rear.next = newNode; // link new node after rear
        newNode.prev = rear; // link back to rear
        rear = newNode;      // update rear pointer
    }

    // Add at front
    void enqueueFront(int data) {
        Node newNode = new Node(data);
        if (front == null) { // empty dequeue
            front = rear = newNode;
            return;
        }
        newNode.next = front; // link new node before front
        front.prev = newNode; // link front back to new node
        front = newNode;      // update front pointer
    }

    // Remove from front
    int dequeueFront() {
        if (front == null) return -1; // empty dequeue
        int val = front.data;
        front = front.next;          // move front forward
        if (front != null) front.prev = null; // disconnect old front
        else rear = null;            // if empty now, rear also null
        return val;
    }

    // Remove from rear
    int dequeueRear() {
        if (rear == null) return -1; // empty dequeue
        int val = rear.data;
        rear = rear.prev;            // move rear backward
        if (rear != null) rear.next = null; // disconnect old rear
        else front = null;           // if empty now, front also null
        return val;
    }

    // Print dequeue from front to rear
    void printDequeue() {
        Node curr = front;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" ↔ ");
            curr = curr.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Dequeue dq = new Dequeue();
        dq.enqueueRear(10);      // step 1
        dq.enqueueFront(20);     // step 2
        dq.dequeueRear();        // step 3
        dq.enqueueRear(30);      // step 4
        dq.printDequeue();       // final state
    }
}

if (rear == null) { front = rear = newNode; return; }

handle empty dequeue by setting front and rear to new node

rear.next = newNode; newNode.prev = rear; rear = newNode;

link new node after rear and update rear pointer

if (front == null) { front = rear = newNode; return; }

handle empty dequeue by setting front and rear to new node

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

link new node before front and update front pointer

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

remove front node and update pointers accordingly

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

remove rear node and update pointers accordingly

Output

20 ↔ 30

Complexity Analysis

Time: O(1) for all operations because adding or removing nodes at front or rear uses direct pointers without traversal

Space: O(n) because each element is stored in a node with pointers

vs Alternative: Compared to array-based dequeue, linked list avoids shifting elements on insertions/removals at front, making operations faster and simpler

Edge Cases

empty dequeue

enqueue sets front and rear to new node; dequeue returns -1

DSA Java

if (rear == null) { front = rear = newNode; return; }

single element dequeue

removing front or rear sets both pointers to null

DSA Java

if (front != null) front.prev = null; else rear = null;

When to Use This Pattern

When you need to add or remove items from both ends efficiently, use a dequeue with a doubly linked list to get O(1) operations.

Common Mistakes

Mistake: Not updating both prev and next pointers when adding or removing nodes
Fix: Always update both pointers to keep the linked list consistent

Mistake: Not handling empty dequeue case when front or rear is null
Fix: Add checks to set front and rear correctly when dequeue becomes empty

Summary

Implements a double-ended queue allowing insertion and deletion at both ends using a doubly linked list.

Use when you want fast O(1) add/remove operations at both front and rear without shifting elements.

The key is maintaining front and rear pointers and updating both next and prev links carefully.

Practice

1. What is the main advantage of using a linked list to implement a Dequeue compared to using an array?

easy

A. It uses less memory than arrays in all cases.

B. It allows dynamic memory allocation and easy insertion/deletion at both ends.

C. It provides faster access to elements by index.

D. It automatically sorts elements when inserted.

Solution

1. Step 1: Understand linked list properties

   A linked list can grow or shrink dynamically without fixed size limits.

2. Step 2: Compare with array limitations

   Arrays have fixed size and inserting/deleting at ends may require shifting elements, which is costly.

3. Final Answer:

   It allows dynamic memory allocation and easy insertion/deletion at both ends. -> Option B

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked list grows dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed with insertion speed
• Assuming linked list sorts elements automatically

2. Which of the following is the correct way to declare a node class for a doubly linked list used in a dequeue in Java?

easy

A. class Node { int data; Node next; }

B. class Node { int data; Node prev; }

C. class Node { int data; Node left; Node right; }

D. class Node { int data; Node next; Node prev; }

Solution

1. Step 1: Identify node requirements for dequeue

   A dequeue needs to insert/delete at both ends, so nodes must link forward and backward.

2. Step 2: Check node class fields

   Only class Node { int data; Node next; Node prev; } has both next and prev pointers for doubly linked list.

3. Final Answer:

   class Node { int data; Node next; Node prev; } -> Option D

4. Quick Check:

   Doubly linked list node = next + prev [OK]

Hint: Doubly linked list nodes have next and prev pointers [OK]

Common Mistakes:

• Using single pointer nodes for dequeue
• Confusing binary tree node pointers with linked list
• Omitting prev pointer needed for backward traversal

3. What will be the output after performing these operations on an empty dequeue implemented using a linked list?

dequeue.insertFront(10);
dequeue.insertRear(20);
dequeue.insertFront(5);
dequeue.deleteRear();
dequeue.display();

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 5 -> 20 -> null

D. 10 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   List becomes: 10 -> 20 -> null

2. Step 2: Perform insertFront(5)

   List becomes: 5 -> 10 -> 20 -> null

3. Step 3: Perform deleteRear()

   Removes 20, list becomes: 5 -> 10 -> null

4. Step 4: Display list

   Output is 5 -> 10 -> null

5. Final Answer:

   5 -> 10 -> null -> Option A

6. Quick Check:

   Front insertions add left, rear deletion removes right [OK]

Hint: Track insertFront and insertRear positions carefully [OK]

Common Mistakes:

• Deleting front instead of rear
• Mixing order of insertions
• Forgetting to update pointers after deletion

4. Consider this buggy method to delete from the front of a dequeue implemented using a linked list:

public void deleteFront() {
  if (front == null) {
    System.out.println("Dequeue is empty");
    return;
  }
  front = front.next;
  front.prev = null;
}

What error can occur when this method is called on a dequeue with only one element?

medium

A. NullPointerException when setting front.prev = null

B. ArrayIndexOutOfBoundsException

C. No error, method works fine

D. Infinite loop in linked list

Solution

1. Step 1: Analyze deleteFront on single element list

   If only one node, after front = front.next, front becomes null.

2. Step 2: Check next line front.prev = null

   Since front is null, accessing front.prev causes NullPointerException.

3. Final Answer:

   NullPointerException when setting front.prev = null -> Option A

4. Quick Check:

   Accessing null pointer causes NullPointerException [OK]

Hint: Check for null before accessing front.prev [OK]

Common Mistakes:

• Assuming front is never null after deletion
• Ignoring edge case of single element
• Confusing exception types

5. You want to implement a dequeue using a linked list that supports these operations efficiently:
1. Insert at front
2. Insert at rear
3. Delete from front
4. Delete from rear
5. Get size of dequeue

Which data members should your dequeue class maintain to achieve all operations in O(1) time?

hard

A. Pointer to rear node only, no size counter

B. Pointer to front node only, and an integer size counter

C. Pointers to front and rear nodes, and an integer size counter

D. Array to store elements and a size counter

Solution

1. Step 1: Identify pointers needed for O(1) insert/delete at both ends

   We need both front and rear pointers to access both ends directly.

2. Step 2: Identify how to get size in O(1)

   Maintain an integer size counter updated on each insert/delete.

3. Final Answer:

   Pointers to front and rear nodes, and an integer size counter -> Option C

4. Quick Check:

   Front + rear pointers + size counter = O(1) ops [OK]

Hint: Keep front, rear pointers and size counter for O(1) operations [OK]

Common Mistakes:

• Using only one pointer for both ends
• Not maintaining size counter for quick size retrieval
• Using array instead of linked list for dequeue