Dequeue Using Linked List in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add an element at the front of the dequeue.

DSA Java

public void addFront(int data) {
    Node newNode = new Node(data);
    if (front == null) {
        front = rear = newNode;
    } else {
        newNode.next = [1];
        front = newNode;
    }
}

Drag options to blanks, or click blank then click option'

Afront

BnewNode

Cnull

Drear

Attempts:

3 left

💡 Hint

Common Mistakes

Setting newNode.next to rear instead of front

Not updating newNode.next at all

To add at the front, the new node's next should point to the current front node.

2fill in blank

medium

Complete the code to remove an element from the rear of the dequeue.

DSA Java

public int removeRear() {
    if (rear == null) {
        throw new NoSuchElementException();
    }
    int value = rear.data;
    if (front == rear) {
        front = rear = null;
    } else {
        Node temp = front;
        while (temp.next != [1]) {
            temp = temp.next;
        }
        rear = temp;
        rear.next = null;
    }
    return value;
}

Drag options to blanks, or click blank then click option'

Atemp.next

Brear

Crear.next

Dfront

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing temp.next to front instead of rear

Using rear.next which is null

To find the node before rear, we check where temp.next equals rear.

3fill in blank

hard

Fix the error in the code to add an element at the rear of the dequeue.

DSA Java

public void addRear(int data) {
    Node newNode = new Node(data);
    if (rear == null) {
        front = rear = newNode;
    } else {
        rear.next = [1];
        rear = newNode;
    }
}

Drag options to blanks, or click blank then click option'

Afront

Bnull

Crear

DnewNode

Attempts:

3 left

💡 Hint

Common Mistakes

Setting rear.next to null which breaks the link

Setting rear.next to front which is incorrect

The current rear's next should point to the new node being added.

4fill in blank

hard

Fill both blanks to complete the method that checks if the dequeue is empty.

DSA Java

public boolean isEmpty() {
    return [1] == [2];
}

Drag options to blanks, or click blank then click option'

Afront

Brear

Cnull

DnewNode

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing rear to newNode which is undefined here

Using front == rear which is not always empty

The dequeue is empty if the front pointer is null.

5fill in blank

hard

Fill all three blanks to complete the method that prints all elements from front to rear.

DSA Java

public void display() {
    Node temp = [1];
    while (temp != [2]) {
        System.out.print(temp.[3] + " -> ");
        temp = temp.next;
    }
    System.out.println("null");
}

Drag options to blanks, or click blank then click option'

Afront

Bnull

Cdata

Drear

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from rear instead of front

Checking temp != rear which misses last node

Printing temp.next instead of temp.data

Start from front, loop until temp is null, print temp.data each time.

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