Dequeue Using Linked List in DSA Typescript

Mental Model

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

Analogy: Imagine a line of people where you can add or remove someone from the front or the back easily without shifting everyone.

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

Dry Run Walkthrough

Input: Start with empty dequeue, then enqueue 1 at rear, enqueue 2 at rear, enqueue 0 at front, dequeue from rear, dequeue from front

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

Step 1: enqueue 1 at rear

null ← [1] -> null
↑front ↑rear

Why: First element becomes both front and rear

Step 2: enqueue 2 at rear

null ← 1 ↔ [2] -> null
↑front       ↑rear

Why: Add new node after rear and update rear pointer

Step 3: enqueue 0 at front

null ← [0] ↔ 1 ↔ 2 -> null
↑front       ↑rear

Why: Add new node before front and update front pointer

Step 4: dequeue from rear

null ← 0 ↔ [1] -> null
↑front       ↑rear

Why: Remove rear node and update rear pointer to previous node

Step 5: dequeue from front

null ← [1] -> null
↑front ↑rear

Why: Remove front node and update front pointer to next node

Result:

null ← [1] -> null
↑front ↑rear

Annotated Code

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;

  enqueueRear(value: number): void {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = newNode;
      this.rear = newNode;
      return;
    }
    this.rear.next = newNode; // link old rear to new node
    newNode.prev = this.rear; // link new node back to old rear
    this.rear = newNode; // update rear pointer
  }

  enqueueFront(value: number): void {
    const newNode = new Node(value);
    if (!this.front) {
      this.front = newNode;
      this.rear = newNode;
      return;
    }
    newNode.next = this.front; // link new node to old front
    this.front.prev = newNode; // link old front back to new node
    this.front = newNode; // update front pointer
  }

  dequeueFront(): number | null {
    if (!this.front) return null; // empty dequeue
    const val = this.front.value;
    this.front = this.front.next; // move front pointer forward
    if (this.front) this.front.prev = null; // disconnect old front
    else this.rear = null; // empty now
    return val;
  }

  dequeueRear(): number | null {
    if (!this.rear) return null; // empty dequeue
    const val = this.rear.value;
    this.rear = this.rear.prev; // move rear pointer backward
    if (this.rear) this.rear.next = null; // disconnect old rear
    else this.front = null; // empty now
    return val;
  }

  print(): void {
    let curr = this.front;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const dq = new Dequeue();
dq.enqueueRear(1);
dq.enqueueRear(2);
dq.enqueueFront(0);
dq.print(); // 0 -> 1 -> 2 -> null
console.log('Dequeue rear:', dq.dequeueRear()); // 2
dq.print(); // 0 -> 1 -> null
console.log('Dequeue front:', dq.dequeueFront()); // 0
dq.print(); // 1 -> null

if (!this.rear) { this.front = newNode; this.rear = newNode; return; }

handle empty dequeue by setting front and rear to new node

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

link new node after rear and update rear pointer

if (!this.front) { this.front = newNode; this.rear = newNode; return; }

handle empty dequeue by setting front and rear to new node

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

link new node before front and update front pointer

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

remove front node and update front pointer, handle empty case

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

remove rear node and update rear pointer, handle empty case

Output

0 -> 1 -> 2 -> null

Dequeue rear: 2

0 -> 1 -> null

Dequeue front: 0

1 -> null

Complexity Analysis

Time: O(1) for all enqueue and dequeue operations because we only update pointers at ends without traversal

Space: O(n) because each element is stored as a node in the linked list

vs Alternative: Compared to array-based dequeue, linked list avoids shifting elements making operations at both ends faster

Edge Cases

empty dequeue

dequeue operations return null without error

DSA Typescript

if (!this.front) return null; // empty dequeue

single element dequeue

removing front or rear empties the dequeue and resets pointers

DSA Typescript

else this.rear = null; // empty now

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 next and prev pointers when adding or removing nodes
Fix: Always update both next and prev pointers to keep the linked list consistent

Mistake: Not handling empty dequeue case when removing nodes
Fix: Check if front or rear becomes null and reset the other pointer accordingly

Summary

Implements a dequeue using a doubly linked list allowing fast add/remove at both ends.

Use when you want efficient insertion and deletion from front and rear without shifting elements.

The key is to keep track of front and rear pointers and update next and prev links carefully.

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