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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

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

Operations:
1. Add 10 at rear
2. Add 20 at front
3. Add 30 at rear
4. Remove from front
5. Add 40 at front
6. Remove from rear

DSA Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class Dequeue {
  front: Node | null = null;
  rear: Node | null = null;

  addFront(value: number) {
    const newNode = new Node(value);
    if (!this.front) {
      this.front = this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
  }

  addRear(value: number) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode;
    } else {
      newNode.prev = this.rear;
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

  removeFront() {
    if (!this.front) return null;
    const val = this.front.value;
    this.front = this.front.next;
    if (this.front) this.front.prev = null;
    else this.rear = null;
    return val;
  }

  removeRear() {
    if (!this.rear) return null;
    const val = this.rear.value;
    this.rear = this.rear.prev;
    if (this.rear) this.rear.next = null;
    else this.front = null;
    return val;
  }

  print() {
    let curr = this.front;
    const values = [];
    while (curr) {
      values.push(curr.value);
      curr = curr.next;
    }
    console.log(values.join(' -> ') + ' -> null');
  }
}

const dq = new Dequeue();
dq.addRear(10);
dq.addFront(20);
dq.addRear(30);
dq.removeFront();
dq.addFront(40);
dq.removeRear();
dq.print();

A 10 -> 30 -> null

B 20 -> 10 -> 30 -> null

C 40 -> 10 -> null

D 40 -> 20 -> 10 -> null

💡 Hint

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

After all operations, the dequeue contains 40 at front and 10 at rear, so the printed state is '40 -> 10 -> 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 removed?

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 removed node

💡 Hint

Think about what the dequeue looks like when empty.

When the last element is removed, 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 removeRear Method

What error will occur when running this removeRear method if the dequeue has only one element?

DSA Typescript

removeRear() {
  if (!this.rear) return null;
  const val = this.rear.value;
  this.rear = this.rear.prev;
  this.rear.next = null;
  return val;
}

A No error, returns the value correctly

B TypeError: Cannot read property 'next' of null

C ReferenceError: this.rear is not defined

D SyntaxError due to missing semicolon

💡 Hint

Consider what happens when this.rear.prev is null.

If the dequeue has one element, this.rear.prev is null, so setting this.rear.next causes a TypeError because this.rear is null.

❓ Predict Output

advanced

Resulting Dequeue After Mixed Operations

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

Operations:
addFront(5), addRear(15), addFront(25), removeRear(), addRear(35), removeFront()

DSA Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class Dequeue {
  front: Node | null = null;
  rear: Node | null = null;

  addFront(value: number) {
    const newNode = new Node(value);
    if (!this.front) {
      this.front = this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
  }

  addRear(value: number) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode;
    } else {
      newNode.prev = this.rear;
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

  removeFront() {
    if (!this.front) return null;
    const val = this.front.value;
    this.front = this.front.next;
    if (this.front) this.front.prev = null;
    else this.rear = null;
    return val;
  }

  removeRear() {
    if (!this.rear) return null;
    const val = this.rear.value;
    this.rear = this.rear.prev;
    if (this.rear) this.rear.next = null;
    else this.front = null;
    return val;
  }

  print() {
    let curr = this.front;
    const values = [];
    while (curr) {
      values.push(curr.value);
      curr = curr.next;
    }
    console.log(values.join(' -> ') + ' -> null');
  }
}

const dq = new Dequeue();
dq.addFront(5);
dq.addRear(15);
dq.addFront(25);
dq.removeRear();
dq.addRear(35);
dq.removeFront();
dq.print();

A 5 -> 15 -> 35 -> null

B 25 -> 5 -> 35 -> null

C 15 -> 35 -> null

D 5 -> 35 -> null

💡 Hint

Track the dequeue state after each operation carefully.

After all operations, the dequeue contains 5 at front and 35 at rear, so the printed state is '5 -> 35 -> null'.

🧠 Conceptual

expert

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of adding or removing elements from both front and rear in a dequeue implemented with a doubly linked list?

A O(1) for all operations

B O(n) for addFront and removeRear, O(1) for others

C O(n) for all operations

D O(1) for addRear and removeFront, O(n) for others

💡 Hint

Consider how pointers are updated in a doubly linked list.

All add and remove operations at front and rear are done by updating pointers directly, so they take constant time O(1).

Practice

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

easy

A. It allows insertion and deletion from both ends in constant time.

B. It uses less memory than arrays.

C. It automatically sorts the elements.

D. It prevents duplicate elements.

Solution

1. Step 1: Understand dequeue operations

   A dequeue supports insertion and deletion from both front and rear ends.

2. Step 2: Compare linked list and array

   Linked lists allow adding/removing nodes at both ends in constant time, unlike arrays which may require shifting elements.

3. Final Answer:

   It allows insertion and deletion from both ends in constant time. -> Option A

4. Quick Check:

   Linked list dequeue = O(1) insert/delete both ends [OK]

Hint: Linked list supports fast add/remove at both ends [OK]

Common Mistakes:

• Thinking arrays allow constant time insert/delete at front
• Confusing memory usage advantage
• Assuming automatic sorting

2. Which of the following is the correct TypeScript method signature to insert an element at the front of a dequeue implemented using a linked list?

easy

A. insertFront(value: number): void

B. addRear(value: number): number

C. pushFront(): void

D. enqueueFront(value: string): string

Solution

1. Step 1: Identify method purpose and parameter

   Inserting at front requires a method that takes a value (number) and returns nothing (void).

2. Step 2: Match signature with correct naming and types

   insertFront(value: number): void matches: method name 'insertFront', parameter 'value: number', return type 'void'. Others have wrong names, return types, or parameter types.

3. Final Answer:

   insertFront(value: number): void -> Option A

4. Quick Check:

   Insert front method = insertFront(value: number): void [OK]

Hint: Method to add front takes value and returns void [OK]

Common Mistakes:

• Using wrong method names like pushFront
• Wrong return types like number or string
• Incorrect parameter types

3. Consider the following TypeScript code snippet for a dequeue using linked list:

const dq = new Dequeue();
dq.insertRear(10);
dq.insertFront(20);
dq.insertRear(30);
dq.deleteFront();
dq.insertFront(40);
dq.deleteRear();
dq.display();

What will be the printed output?

medium

A. 10 -> 20 -> 30 -> null

B. 40 -> 10 -> null

C. 20 -> 10 -> 30 -> null

D. 40 -> 20 -> null

Solution

1. Step 1: Trace each operation on dequeue

   Start empty. insertRear(10): 10 insertFront(20): 20 -> 10 insertRear(30): 20 -> 10 -> 30 deleteFront(): removes 20, now 10 -> 30 insertFront(40): 40 -> 10 -> 30 deleteRear(): removes 30, now 40 -> 10

2. Step 2: Display final dequeue state

   Prints elements from front to rear: 40 -> 10 -> null

3. Final Answer:

   40 -> 10 -> null -> Option B

4. Quick Check:

   After operations, dequeue = 40 -> 10 -> null [OK]

Hint: Trace each insert/delete step carefully [OK]

Common Mistakes:

• Forgetting deleteFront removes front element
• Mixing order of insertFront and insertRear
• Not updating links after deleteRear

4. The following TypeScript method for deleting the rear node in a dequeue implemented using a singly linked list has a bug. What is the bug?

deleteRear(): number | null {
  if (!this.rear) return null;
  let temp = this.front;
  while (temp.next !== this.rear) {
    temp = temp.next;
  }
  const value = this.rear.value;
  this.rear = temp;
  this.rear.next = null;
  return value;
}

medium

A. It causes an infinite loop when the list is empty.

B. It incorrectly updates the front pointer.

C. It returns the wrong value after deletion.

D. It does not handle the case when there is only one node.

Solution

1. Step 1: Analyze loop and pointers

   The loop finds the node before rear by checking temp.next !== rear. If only one node exists, temp.next is null, so loop condition fails immediately.

2. Step 2: Check single node case

   If only one node, front and rear point to same node. The code does not update front or rear to null, causing incorrect state after deletion.

3. Final Answer:

   It does not handle the case when there is only one node. -> Option D

4. Quick Check:

   Single node deleteRear needs special handling [OK]

Hint: Check single-node edge case in deleteRear [OK]

Common Mistakes:

• Ignoring single-node list case
• Assuming front pointer updates automatically
• Overlooking null pointer exceptions

5. You want to implement a dequeue using a doubly linked list in TypeScript. Which of the following changes will improve the efficiency of deleting the rear node compared to a singly linked list implementation?

hard

A. Traverse from front to find the node before rear each time.

B. Use an array instead of linked list for rear deletion.

C. Maintain a rear pointer and use the previous pointer to delete rear in O(1) time.

D. Delete rear by shifting all elements forward.

Solution

1. Step 1: Understand doubly linked list structure

   Each node has pointers to next and previous nodes, allowing backward traversal.

2. Step 2: Use rear pointer and previous link

   With rear pointer and previous link, deleting rear node is direct and takes constant time without traversal.

3. Final Answer:

   Maintain a rear pointer and use the previous pointer to delete rear in O(1) time. -> Option C

4. Quick Check:

   Doubly linked list rear delete = O(1) using prev pointer [OK]

Hint: Use prev pointer in doubly linked list for fast rear delete [OK]

Common Mistakes:

• Traversing from front wastes time
• Using array shifts is inefficient
• Ignoring doubly linked list advantages