Dequeue Using Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

What is the printed state of the dequeue after the following operations?

Operations:
1. Insert 10 at rear
2. Insert 20 at front
3. Insert 30 at rear
4. Delete from front
5. Insert 40 at front

DSA Java

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

class Dequeue {
    Node front, rear;

    void insertFront(int x) {
        Node newNode = new Node(x);
        if (front == null) {
            front = rear = newNode;
            return;
        }
        newNode.next = front;
        front.prev = newNode;
        front = newNode;
    }

    void insertRear(int x) {
        Node newNode = new Node(x);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        newNode.prev = rear;
        rear = newNode;
    }

    void deleteFront() {
        if (front == null) return;
        if (front == rear) {
            front = rear = null;
            return;
        }
        front = front.next;
        front.prev = null;
    }

    void printDequeue() {
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        Dequeue dq = new Dequeue();
        dq.insertRear(10);
        dq.insertFront(20);
        dq.insertRear(30);
        dq.deleteFront();
        dq.insertFront(40);
        dq.printDequeue();
    }
}

A 10 -> 30 -> null

B 20 -> 10 -> 30 -> null

C 40 -> 10 -> 30 -> null

D 40 -> 20 -> 10 -> 30 -> null

💡 Hint

Trace each operation step-by-step and update the dequeue state.

After inserting 10 at rear: 10 -> null Insert 20 at front: 20 -> 10 -> null Insert 30 at rear: 20 -> 10 -> 30 -> null Delete from front removes 20: 10 -> 30 -> null Insert 40 at front: 40 -> 10 -> 30 -> null

🧠 Conceptual

intermediate

Understanding Dequeue Front and Rear Pointers

In a dequeue implemented using a doubly linked list, what happens to the front and rear pointers when the last element is deleted?

A Both front and rear pointers become null

B Front pointer becomes null, rear remains unchanged

C Rear pointer becomes null, front remains unchanged

D Both pointers point to the deleted node

💡 Hint

Consider what happens when the dequeue becomes empty.

When the last element is deleted, the dequeue becomes empty, so both front and rear pointers must be set to null to indicate no elements.

🔧 Debug

advanced

Identify the Bug in Dequeue Insert Front Method

What error will occur when running this insertFront method in a dequeue implemented with a doubly linked list?

DSA Java

void insertFront(int x) {
    Node newNode = new Node(x);
    if (front == null) {
        front = newNode;
        return;
    }
    newNode.next = front;
    front.prev = newNode;
    front = newNode;
}

A Memory leak due to missing node deletion

B NullPointerException when front.prev is accessed

C No error, code works correctly

D Rear pointer remains null causing errors on rear operations

💡 Hint

Check what happens to rear pointer when inserting the first node.

When the dequeue is empty, only front is set to newNode but rear remains null. This causes errors when rear operations are performed because rear is not initialized.

❓ Predict Output

advanced

Output After Mixed Dequeue Operations

What is the printed state of the dequeue after these operations?

Operations:
1. Insert 5 at rear
2. Insert 15 at rear
3. Insert 25 at front
4. Delete from rear
5. Delete from front

DSA Java

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

class Dequeue {
    Node front, rear;

    void insertFront(int x) {
        Node newNode = new Node(x);
        if (front == null) {
            front = rear = newNode;
            return;
        }
        newNode.next = front;
        front.prev = newNode;
        front = newNode;
    }

    void insertRear(int x) {
        Node newNode = new Node(x);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        newNode.prev = rear;
        rear = newNode;
    }

    void deleteFront() {
        if (front == null) return;
        if (front == rear) {
            front = rear = null;
            return;
        }
        front = front.next;
        front.prev = null;
    }

    void deleteRear() {
        if (rear == null) return;
        if (front == rear) {
            front = rear = null;
            return;
        }
        rear = rear.prev;
        rear.next = null;
    }

    void printDequeue() {
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        Dequeue dq = new Dequeue();
        dq.insertRear(5);
        dq.insertRear(15);
        dq.insertFront(25);
        dq.deleteRear();
        dq.deleteFront();
        dq.printDequeue();
    }
}

A 15 -> null

B 5 -> null

C 25 -> 5 -> null

D null

💡 Hint

Track the list after each operation carefully.

After insertRear(5): 5 -> null insertRear(15): 5 -> 15 -> null insertFront(25): 25 -> 5 -> 15 -> null deleteRear(): removes 15, list is 25 -> 5 -> null deleteFront(): removes 25, list is 5 -> null

🧠 Conceptual

expert

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of insert and delete operations at both ends in a dequeue implemented using a doubly linked list?

A All operations take O(1) time

B Insertions take O(1), deletions take O(n)

C Insertions take O(n), deletions take O(1)

D All operations take O(n) time

💡 Hint

Consider how pointers are updated in a doubly linked list.

In a doubly linked list, both ends are directly accessible via pointers, so insertions and deletions at front and rear happen in constant time O(1).

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