Double Ended Queue Deque in DSA Typescript

Mental Model

A deque lets you add or remove items from both the front and the back easily.

Analogy: Think of a deque like a line of people where you can join or leave from either the front or the back.

front -> [ ] -> [ ] -> [ ] -> back
↑ (can add or remove here)
                ↑ (can add or remove here)

Dry Run Walkthrough

Input: start with empty deque, add 1 at front, add 2 at back, remove from front, add 3 at front

Goal: Show how items are added and removed from both ends step-by-step

Step 1: add 1 at front

front -> [1] -> back
↑
↑

Why: We add 1 at the front because the deque is empty

Step 2: add 2 at back

front -> [1] -> [2] -> back
↑
                ↑

Why: We add 2 at the back to show adding at the other end

Step 3: remove from front

front -> [2] -> back
↑
↑

Why: Removing from front removes 1, leaving 2 at front

Step 4: add 3 at front

front -> [3] -> [2] -> back
↑
                ↑

Why: Adding 3 at front puts it before 2

Result:

front -> [3] -> [2] -> back

Annotated Code

DSA Typescript

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

class Deque {
  private head: DequeNode | null = null;
  private tail: DequeNode | null = null;

  addFront(value: number): void {
    const newNode = new DequeNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    newNode.next = this.head; // link new node forward to current front
    this.head.prev = newNode; // link current front backward to new node
    this.head = newNode; // update front pointer to new node
  }

  addBack(value: number): void {
    const newNode = new DequeNode(value);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    newNode.prev = this.tail; // link new node backward to current back
    this.tail.next = newNode; // link current back forward to new node
    this.tail = newNode; // update back pointer to new node
  }

  removeFront(): number | null {
    if (!this.head) return null;
    const val = this.head.value;
    this.head = this.head.next; // remove front by moving front pointer forward
    if (this.head) this.head.prev = null; // disconnect backward link from new front
    else this.tail = null; // empty deque
    return val;
  }

  removeBack(): number | null {
    if (!this.tail) return null;
    const val = this.tail.value;
    this.tail = this.tail.prev; // remove back by moving back pointer backward
    if (this.tail) this.tail.next = null; // disconnect forward link from new back
    else this.head = null; // empty deque
    return val;
  }

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

// Driver code using dry_run input
const deque = new Deque();
deque.addFront(1);
deque.addBack(2);
deque.removeFront();
deque.addFront(3);
deque.printDeque();

newNode.next = this.head; // link new node to current head

link new node forward to current front

this.head.prev = newNode; // link current head back to new node

link current front backward to new node

this.head = newNode; // update head to new node

update front pointer to new node

newNode.prev = this.tail; // link new node back to current tail

link new node backward to current back

this.tail.next = newNode; // link current tail forward to new node

link current back forward to new node

this.tail = newNode; // update tail to new node

update back pointer to new node

this.head = this.head.next; // move head forward

remove front by moving front pointer forward

if (this.head) this.head.prev = null; // remove backward link

disconnect backward link from new front

this.tail = this.tail.prev; // move tail backward

remove back by moving back pointer backward

if (this.tail) this.tail.next = null; // remove forward link

disconnect forward link from new back

Output

3 -> 2 -> null

Complexity Analysis

Time: O(1) for add and remove operations because we only change a few pointers without traversing the deque

Space: O(n) because we store n nodes in the deque

vs Alternative: Compared to arrays where adding/removing at front can be O(n), deque operations are faster with O(1) at both ends

Edge Cases

empty deque when removing

removeFront and removeBack return null safely without error

DSA Typescript

if (!this.head) return null;

deque with single element when removing

removing front or back empties the deque and sets head and tail to null

DSA Typescript

else this.tail = null; // empty deque

When to Use This Pattern

When you need to add or remove items quickly from both ends of a list, use a deque because it supports fast operations at front and back.

Common Mistakes

Mistake: Forgetting to update both next and prev pointers when adding or removing nodes
Fix: Always update both forward and backward links to keep the deque consistent

Summary

A deque lets you add or remove items from both front and back efficiently.

Use it when you need flexible access to both ends of a list without slow shifts.

The key is updating pointers carefully to keep the double links correct.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A data structure where elements can be added or removed from both ends

B. A queue where elements can only be added at the rear and removed from the front

C. A stack where elements can only be added or removed from the top

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of a deque

   A deque allows insertion and deletion from both front and rear ends, unlike a queue or stack.

2. Step 2: Compare with other data structures

   Queue allows operations only at one end for insertion and the other for deletion; stack only at one end.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque allows random access
• Assuming insertion only at one end

2. Which of the following is the correct TypeScript method to add an element at the front of a deque implemented as an array named deque?

easy

A. deque.shift(element);

B. deque.push(element);

C. deque.pop(element);

D. deque.unshift(element);

Solution

1. Step 1: Recall array methods for front insertion

   In TypeScript/JavaScript, unshift() adds an element at the start of an array.

2. Step 2: Verify other methods

   push() adds at the end, pop() removes from end, shift() removes from front.

3. Final Answer:

   deque.unshift(element); -> Option D

4. Quick Check:

   unshift() adds front [OK]

Hint: Use unshift() to add front in arrays [OK]

Common Mistakes:

• Using push() instead of unshift() for front
• Confusing pop() and shift() as insertion
• Passing arguments to pop() or shift()

3. What will be the output of the following TypeScript code?

const deque: number[] = [];
deque.push(10);
deque.unshift(20);
deque.push(30);
deque.shift();
console.log(deque);

medium

A. [20, 10, 30]

B. [20, 30]

C. [10, 30]

D. [30, 20]

Solution

1. Step 1: Trace each operation on deque

   Start: []
   push(10) -> [10]
   unshift(20) -> [20, 10]
   push(30) -> [20, 10, 30]
   shift() removes front -> removes 20 -> [10, 30]

2. Step 2: Final state of deque

   After all operations, deque is [10, 30].

3. Final Answer:

   [10, 30] -> Option C

4. Quick Check:

   After shift(), front removed -> [10, 30] [OK]

Hint: Remember shift() removes front element [OK]

Common Mistakes:

• Forgetting shift() removes front
• Mixing order of push and unshift
• Assuming shift() removes last element

4. Identify the error in the following TypeScript code that implements a deque using an array:

const deque: number[] = [];
deque.push(5);
deque.unshift(10);
deque.pop(5);
console.log(deque);

medium

A. push() cannot be used on arrays

B. pop() should not have any arguments

C. unshift() removes elements, not adds

D. console.log syntax is incorrect

Solution

1. Step 1: Check usage of pop() method

   pop() removes the last element and does not take any arguments. Passing 5 is incorrect.

2. Step 2: Verify other methods and syntax

   push() adds element at end, unshift() adds at front, console.log syntax is correct.

3. Final Answer:

   pop() should not have any arguments -> Option B

4. Quick Check:

   pop() takes no arguments [OK]

Hint: pop() never takes arguments [OK]

Common Mistakes:

• Passing argument to pop()
• Confusing unshift() as removal
• Thinking push() is invalid on arrays

5. You want to implement a deque that supports adding and removing elements from both ends efficiently. Which data structure is best suited for this in TypeScript, and why?

hard

A. Use a linked list because it allows O(1) insertion and deletion at both ends

B. Use an array because it provides O(1) insertion and deletion at both ends

C. Use a binary tree because it supports fast search and insertion

D. Use a stack because it supports adding/removing from both ends

Solution

1. Step 1: Analyze efficiency of array for deque operations

   Arrays have O(1) insertion/deletion at the end but O(n) at the front due to shifting elements.

2. Step 2: Consider linked list advantages

   Linked lists allow O(1) insertion and deletion at both front and rear by adjusting pointers.

3. Step 3: Evaluate other options

   Binary trees are for search, not efficient deque operations; stacks only allow one end operations.

4. Final Answer:

   Use a linked list because it allows O(1) insertion and deletion at both ends -> Option A

5. Quick Check:

   Linked list = efficient deque [OK]

Hint: Linked list supports fast front and rear operations [OK]

Common Mistakes:

• Assuming arrays are efficient at front insertion
• Confusing stack with deque
• Choosing binary tree for deque operations