Dequeue Using Linked List in DSA Java - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is dequeue empty?

Yes→Set head and tail to new node

|No↓

Insert at front or rear?

↓

Front Insert

↓

Update head

↓

Done

↓

Remove from front or rear?

↓

Front Remove

↓

Update head

↓

If empty, set head and tail to null

↓

Done

Shows how nodes are added or removed from front or rear in a dequeue using a linked list.

Execution Sample

DSA Java

Dequeue dq = new Dequeue();
dq.insertRear(10);
dq.insertFront(20);
dq.removeRear();
dq.insertFront(30);
dq.removeFront();

This code inserts and removes elements at both ends of a dequeue implemented with a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	insertRear(10)	10	head=10, tail=10	10 -> null
2	insertFront(20)	20, 10	head=20, tail=10	20 -> 10 -> null
3	removeRear()	20	tail=20, tail.next=null	20 -> null
4	insertFront(30)	30, 20	head=30, tail=20	30 -> 20 -> null
5	removeFront()	20	head=20	20 -> null
6	End	20	No change	20 -> null

💡 No more operations; final list has one node with value 20.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
head	null	10	20	20	30	20	20
tail	null	10	10	20	20	20	20
list size	0	1	2	1	2	1	1

Key Moments - 3 Insights

Why do we update both head and tail when the list is empty?

When the list is empty (Step 1), inserting the first node means head and tail both point to that node, as shown in execution_table row 1.

Why does removeRear update tail and set tail.next to null?

In Step 3, removing the rear node means tail moves to the previous node and tail.next must be null to mark the end, as shown in pointer changes.

What happens if we remove the last node from the list?

If the last node is removed, both head and tail become null to indicate the list is empty, as explained in the concept flow and shown after removals.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the visual state of the list?

A 10 -> 20 -> null

B 10 -> null

C 20 -> 10 -> null

D 20 -> null

💡 Hint

Check the Visual State column at Step 2 in execution_table.

At which step does the tail pointer change from 10 to 20?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the Pointer Changes column in execution_table to see when tail updates.

If we removeFront at Step 5, what will be the head pointer value after the operation?

A 20

B 30

C null

D 10

💡 Hint

Check variable_tracker for head value after Step 5.

Concept Snapshot

Dequeue Using Linked List:
- Insert at front: new node points to head, update head
- Insert at rear: tail.next points to new node, update tail
- Remove front: move head to head.next
- Remove rear: traverse to node before tail, update tail
- If empty after removal, set head and tail to null

Full Transcript

This visual execution shows how a dequeue works using a linked list. We start with an empty list. When inserting at rear or front, we create a new node and update head or tail pointers accordingly. Removing from front moves head forward, removing from rear moves tail backward. If the list becomes empty, both head and tail are set to null. The execution table tracks each operation, the nodes present, pointer changes, and the visual linked list state. Variable tracker shows how head, tail, and size change step by step. Key moments clarify why head and tail update together when empty, why tail.next is set to null after removing rear, and what happens when the last node is removed. The quiz tests understanding of list states and pointer updates at specific steps.

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