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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

Consider a dequeue implemented using a linked list. The following operations are performed in order:

1. Insert 10 at rear
2. Insert 20 at front
3. Insert 30 at rear
4. Delete from front
5. Insert 40 at front
6. Delete from rear

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

DSA Javascript

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

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

  insertFront(data) {
    const newNode = new Node(data);
    if (!this.front) {
      this.front = this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
  }

  insertRear(data) {
    const newNode = new Node(data);
    if (!this.rear) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      newNode.prev = this.rear;
      this.rear = newNode;
    }
  }

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

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

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

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

A 40 -> 10 -> null

B 20 -> 10 -> null

C 10 -> 30 -> null

D 40 -> 20 -> 10 -> null

💡 Hint

Trace each operation step-by-step and update the linked list accordingly.

After all operations, the dequeue contains 40 at front and 10 at rear. The sequence is 40 -> 10 -> null.

🧠 Conceptual

intermediate

Understanding Dequeue Front and Rear Pointers

In a dequeue implemented using a doubly linked list, which statement is TRUE about the front and rear pointers after deleting the last element?

A Both front and rear pointers become null.

B Front pointer points to the last node, rear pointer becomes null.

C Both front and rear pointers point to the deleted node.

D Rear pointer points to the last node, front pointer becomes null.

💡 Hint

Think about what happens when the dequeue becomes empty.

When the last element is deleted, the dequeue is empty, so both front and rear pointers must be null.

🔧 Debug

advanced

Identify the Bug in Dequeue Rear Deletion

What error will occur when running the following code snippet for deleting from rear in a dequeue implemented with a doubly linked list?

DSA Javascript

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

// Assume dequeue has only one element before calling deleteRear()

A TypeError: Cannot set property 'next' of null

B ReferenceError: this.rear is not defined

C No error, returns the correct value

D SyntaxError: Unexpected token

💡 Hint

Check the condition when front and rear are the same node.

The code correctly handles the case when there is only one element by setting front and rear to null, so no error occurs.

❓ Predict Output

advanced

Result of Mixed Insertions and Deletions

Given a dequeue implemented with a doubly linked list, what is the output after these operations?

insertFront(5)
insertRear(15)
insertFront(3)
deleteRear()
insertRear(20)
deleteFront()
print()

DSA Javascript

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

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

  insertFront(data) {
    const newNode = new Node(data);
    if (!this.front) {
      this.front = this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
  }

  insertRear(data) {
    const newNode = new Node(data);
    if (!this.rear) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      newNode.prev = this.rear;
      this.rear = newNode;
    }
  }

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

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

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

const dq = new Dequeue();
dq.insertFront(5);
dq.insertRear(15);
dq.insertFront(3);
dq.deleteRear();
dq.insertRear(20);
dq.deleteFront();
console.log(dq.print());

A 15 -> 20 -> null

B 3 -> 5 -> 20 -> null

C 5 -> 15 -> 20 -> null

D 5 -> 20 -> null

💡 Hint

Track the list after each operation carefully.

After all operations, the dequeue contains 5 at front and 20 at rear, so the output is '5 -> 20 -> null'.

🧠 Conceptual

expert

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of insertions and deletions at both ends (front and rear) in a dequeue implemented using a doubly linked list?

A O(1) for insertions at front, O(n) for deletions at rear

B O(1) for all insertions and deletions

C O(n) for all operations

D O(n) for insertions at rear, O(1) for deletions at front

💡 Hint

Consider how pointers are updated in a doubly linked list.

Using a doubly linked list with front and rear pointers allows all insertions and deletions at both ends in 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 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