Dequeue Using Linked List in DSA Javascript

Mental Model

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

Analogy: Think of a train where you can add or remove cars from the front or back easily without rearranging the whole train.

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

Dry Run Walkthrough

Input: Start with empty dequeue, then add 1 at front, add 2 at back, add 3 at front, remove from back

Goal: Show how items are added and removed from both ends using linked list pointers

Step 1: Add 1 at front

front -> [1] -> null ← back

Why: First node becomes both front and back

Step 2: Add 2 at back

front -> [1] -> [2] -> null ← back

Why: Add new node after back and update back pointer

Step 3: Add 3 at front

front -> [3] -> [1] -> [2] -> null ← back

Why: Add new node before front and update front pointer

Step 4: Remove from back

front -> [3] -> [1] -> null ← back

Why: Remove last node and update back pointer to previous node

Result:

front -> [3] -> [1] -> null ← back

Annotated Code

DSA Javascript

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

class Dequeue {
  constructor() {
    this.front = null;
    this.back = null;
  }

  addFront(value) {
    const newNode = new Node(value);
    if (!this.front) {
      this.front = newNode;
      this.back = newNode;
      return;
    }
    newNode.next = this.front; // link new node to current front
    this.front.prev = newNode; // link current front back to new node
    this.front = newNode; // update front pointer
  }

  addBack(value) {
    const newNode = new Node(value);
    if (!this.back) {
      this.front = newNode;
      this.back = newNode;
      return;
    }
    this.back.next = newNode; // link current back to new node
    newNode.prev = this.back; // link new node back to current back
    this.back = newNode; // update back pointer
  }

  removeFront() {
    if (!this.front) return null; // empty dequeue
    const value = this.front.value;
    this.front = this.front.next; // move front pointer forward
    if (this.front) this.front.prev = null; // remove backward link
    else this.back = null; // if empty now, reset back
    return value;
  }

  removeBack() {
    if (!this.back) return null; // empty dequeue
    const value = this.back.value;
    this.back = this.back.prev; // move back pointer backward
    if (this.back) this.back.next = null; // remove forward link
    else this.front = null; // if empty now, reset front
    return value;
  }

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

// Driver code using dry_run input
const dq = new Dequeue();
dq.addFront(1); // step 1
dq.addBack(2);  // step 2
dq.addFront(3); // step 3
dq.removeBack(); // step 4

dq.print();

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

link new node before current front to insert at front

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

connect current front back pointer to new node

this.front = newNode; // update front pointer

update front pointer to new node

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

link current back forward pointer to new node

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

connect new node back pointer to current back

this.back = newNode; // update back pointer

update back pointer to new node

this.front = this.front.next; // move front pointer forward

remove front node by moving front pointer forward

this.front.prev = null; // remove backward link

disconnect backward link from new front

this.back = this.back.prev; // move back pointer backward

remove back node by moving back pointer backward

this.back.next = null; // remove forward link

disconnect forward link from new back

Output

3 -> 1 -> null

Complexity Analysis

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

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

vs Alternative: Compared to using arrays where adding/removing at front can be O(n), linked list dequeue is faster with O(1) operations

Edge Cases

empty dequeue when removing

removeFront or removeBack returns null without error

DSA Javascript

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

single element dequeue when removing

removing front or back resets both front and back to null

DSA Javascript

else this.back = null; // if empty now, reset back

adding first element to empty dequeue

front and back both point to the new node

DSA Javascript

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

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: Forgetting to update both front and back pointers when the dequeue becomes empty
Fix: Set both front and back to null when removing the last element

Mistake: Not updating the prev or next pointers correctly when adding or removing nodes
Fix: Always update both forward and backward links to keep the list consistent

Summary

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

Use when you want quick insertions and deletions from front and back without shifting elements.

The key is to keep track of front and back 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 automatically sorts the elements as they are inserted.

B. It allows efficient insertion and deletion from both ends without shifting elements.

C. It uses less memory than an array for the same number of elements.

D. It prevents duplicate elements from being added.

Solution

1. Step 1: Understand linked list operations

   A linked list allows adding or removing nodes at the front or back in constant time without moving other elements.

2. Step 2: Compare with array behavior

   Arrays require shifting elements when inserting or deleting at the front, which is less efficient.

3. Final Answer:

   It allows efficient insertion and deletion from both ends without shifting elements. -> Option B

4. Quick Check:

   Linked list = efficient ends operations [OK]

Hint: Linked list avoids shifting elements for front/back operations [OK]

Common Mistakes:

• Thinking arrays are always more memory efficient
• Assuming linked list sorts elements automatically
• Believing linked list prevents duplicates

2. Which of the following is the correct way to add a new node at the front of a dequeue implemented using a linked list in JavaScript?

easy

A. Create new node, set its prev to current tail, update tail to new node.

B. Create new node, set its prev to current head, update head to new node.

C. Create new node, set its next to null, update tail to new node.

D. Create new node, set its next to current head, update head to new node.

Solution

1. Step 1: Understand adding at front in linked list

   To add at front, new node's next points to current head, then head updates to new node.

2. Step 2: Check options for correctness

   Create new node, set its next to current head, update head to new node. matches this logic; others incorrectly use prev or tail.

3. Final Answer:

   Create new node, set its next to current head, update head to new node. -> Option D

4. Quick Check:

   Add front = newNode.next = head; head = newNode [OK]

Hint: New front node points next to old head [OK]

Common Mistakes:

• Confusing prev and next pointers
• Updating tail instead of head when adding front
• Setting next to null incorrectly

3. Consider the following JavaScript code for a dequeue using a doubly linked list:

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

class Dequeue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  addFront(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  addRear(value) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

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

const dq = new Dequeue();
dq.addRear(10);
dq.addFront(20);
dq.addRear(30);
const removed = dq.removeFront();
console.log(removed);
console.log(dq.head.value + ' -> ' + dq.tail.value);

What will be the output?

medium

A. 10
20 -> 30

B. 20
30 -> 10

C. 20
10 -> 30

D. 10
30 -> 20

Solution

1. Step 1: Trace insertions

   addRear(10): list is 10 addFront(20): list is 20 -> 10 addRear(30): list is 20 -> 10 -> 30

2. Step 2: Trace removal

   removeFront() removes 20, returns 20. List becomes 10 -> 30.

3. Final Answer:

   20 10 -> 30 -> Option C

4. Quick Check:

   Remove front returns 20; list head=10, tail=30 [OK]

Hint: Track head/tail changes step-by-step [OK]

Common Mistakes:

• Confusing addFront and addRear order
• Forgetting to update prev pointers
• Mixing removed value with current head

4. The following code snippet is intended to remove the rear node from a dequeue implemented using a doubly linked list. What is the error?

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

medium

A. It does not handle the case when the list becomes empty after removal.

B. It incorrectly updates the head pointer instead of tail.

C. It should set this.tail.prev to null instead of this.tail.next.

D. It returns the wrong value after removal.

Solution

1. Step 1: Analyze removal logic

   After setting tail to tail.prev, if tail becomes null (list empty), accessing tail.next causes error.

2. Step 2: Identify missing check

   Code must check if tail is null before setting tail.next = null to avoid runtime error.

3. Final Answer:

   It does not handle the case when the list becomes empty after removal. -> Option A

4. Quick Check:

   Check empty list after removal to avoid null pointer [OK]

Hint: Check for empty list before pointer updates [OK]

Common Mistakes:

• Not checking if tail is null after update
• Confusing head and tail pointers
• Setting wrong pointer to null

5. You want to implement a function reverseDequeue() that reverses the order of nodes in a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue?

hard

A. Traverse each node, swap its next and prev pointers, then swap head and tail pointers.

B. Traverse each node, set next to null, and prev to head, then update head to tail.

C. Create a new dequeue and addRear nodes from the original dequeue's front to rear.

D. Swap values of head and tail nodes only.

Solution

1. Step 1: Understand reversal in doubly linked list

   Reversing means each node's next and prev pointers must be swapped to reverse direction.

2. Step 2: Update head and tail pointers

   After swapping pointers in all nodes, head and tail pointers must be swapped to reflect new ends.

3. Final Answer:

   Traverse each node, swap its next and prev pointers, then swap head and tail pointers. -> Option A

4. Quick Check:

   Swap next/prev in nodes + swap head/tail [OK]

Hint: Swap next and prev pointers in all nodes [OK]

Common Mistakes:

• Only swapping head and tail values
• Setting next to null incorrectly
• Creating new dequeue instead of reversing in place