Double Ended Queue Deque in DSA Javascript - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Add Front

→Create New Node

↓

New Node.next = head

↓

head.prev = New Node

↓

head = New Node

↓

Done

↓

Add Rear

→Create New Node

↓

tail.next = New Node

↓

New Node.prev = tail

↓

tail = New Node

↓

Done

↓

Remove Front

→Check if empty

↓

head = head.next

↓

head.prev = null

↓

Done

↓

Remove Rear

→Check if empty

↓

tail = tail.prev

↓

tail.next = null

↓

Done

Shows how adding or removing nodes at front or rear updates pointers and the deque ends.

Execution Sample

DSA Javascript

deque.addRear(10);
deque.addFront(20);
deque.addRear(30);
deque.removeFront();
deque.removeRear();

Adds 10 at rear, 20 at front, 30 at rear, then removes front and rear elements.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	addRear(10)	10	head -> 10, tail -> 10	10 <-> null
2	addFront(20)	20, 10	newNode.next = head(10), head.prev = newNode(20), head -> 20	20 <-> 10 <-> null
3	addRear(30)	20, 10, 30	tail.next = newNode(30), newNode.prev = tail(10), tail -> 30	20 <-> 10 <-> 30 <-> null
4	removeFront()	10, 30	head = head.next(10), head.prev = null	10 <-> 30 <-> null
5	removeRear()	10	tail = tail.prev(10), tail.next = null	10 <-> null
6	End	10	No change	10 <-> null

💡 No more operations; deque has one node with value 10.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
head	null	10	20	20	10	10	10
tail	null	10	10	30	30	10	10
size	0	1	2	3	2	1	1

Key Moments - 3 Insights

Why does adding at front update head but not tail?

Because the new node becomes the first node, head must point to it. Tail stays same unless list was empty (see step 2 in execution_table).

Why do we set head.prev to null after removing front?

To disconnect the removed node and keep the list start clean (step 4). Without this, old node still links back, causing errors.

What happens if we remove from an empty deque?

The code checks if head or tail is null before removing. If empty, no pointer changes happen and operation stops safely (not shown in this trace).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the tail node's value?

A 10

B 20

C 30

D null

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3.

At which step does the deque size become 2?

A After step 1

B After step 2

C After step 3

D After step 4

💡 Hint

Look at the 'size' variable in variable_tracker after each step.

If we removeRear() at step 5, what will be the new tail's next pointer?

A Points to 30

B Points to 20

C Null

D Points to 10

💡 Hint

See 'Pointer Changes' at step 5 in execution_table.

Concept Snapshot

Double Ended Queue (Deque):
- Supports adding/removing at both front and rear.
- addFront: new node becomes head, links to old head.
- addRear: new node becomes tail, links from old tail.
- removeFront: head moves to next node, prev cleared.
- removeRear: tail moves to prev node, next cleared.
- Maintains head and tail pointers for O(1) operations.

Full Transcript

A double ended queue, or deque, lets us add or remove items from both ends quickly. When we add at the front, we create a new node and link it before the current head, then update head to this new node. When adding at the rear, we link the new node after the current tail and update tail. Removing from front moves head to the next node and clears the previous link. Removing from rear moves tail to the previous node and clears the next link. This keeps the deque connected and efficient. The example code adds 10 at rear, 20 at front, 30 at rear, then removes front and rear, showing how pointers and size change step by step.

Practice

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

easy

A. A stack where elements are added and removed only from the top.

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

C. A data structure where elements can be added or removed from both front and rear ends.

D. A list that allows random access to elements by index.

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion at both ends, unlike a queue or stack which restrict operations to one end.

2. Step 2: Compare with other data structures

   Queue allows operations only at front and rear separately; stack only at one end; list allows random access but not double-ended insertion/removal.

3. Final Answer:

   A data structure where elements can be added or removed from both front and rear ends. -> Option C

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 simple queue
• Thinking deque allows random access by index
• Assuming deque operations only at one end

2. Which of the following is the correct way to add an element to the front of a deque named dq in JavaScript using an array?

easy

A. dq.unshift(element);

B. dq.pop(element);

C. dq.push(element);

D. dq.shift(element);

Solution

1. Step 1: Identify array methods for front insertion

   In JavaScript, unshift() adds an element to the start (front) of an array.

2. Step 2: Check other methods

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

3. Final Answer:

   dq.unshift(element); -> Option A

4. Quick Check:

   unshift adds front element [OK]

Hint: Use unshift() to add front element in JS array [OK]

Common Mistakes:

• Using push() instead of unshift() for front insertion
• Confusing pop() and shift() as insertion methods
• Passing argument to pop() or shift() which don't take any

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

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

medium

A. [10, 30]

B. [20, 10, 30]

C. [20, 30]

D. [10, 20, 30]

Solution

1. Step 1: Trace each operation on the deque

   Start with empty array [].
   push(10) => [10]
   unshift(20) => [20, 10]
   push(30) => [20, 10, 30]
   shift() removes front element 20 => [10, 30]

2. Step 2: Final state of dq

   After all operations, dq contains [10, 30].

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   After shift(), front 20 removed, left [10, 30] [OK]

Hint: Track each push/unshift/shift step carefully [OK]

Common Mistakes:

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

4. Identify the error in the following code snippet that tries to remove an element from the rear of a deque implemented as an array named dq:

dq.removeLast();

medium

A. dq.pop() should be used instead of removeLast().

B. removeLast() is not a valid JavaScript array method.

C. removeLast() requires an argument to specify the element.

D. dq should be a linked list to use removeLast().

Solution

1. Step 1: Check JavaScript array methods for removing last element

   JavaScript arrays do not have a method named removeLast(). The correct method to remove the last element is pop().

2. Step 2: Analyze other options

   Linked list is unrelated here; removeLast() does not take arguments; pop() is the correct method.

3. Final Answer:

   removeLast() is not a valid JavaScript array method. -> Option B

4. Quick Check:

   pop() removes last element, removeLast() invalid [OK]

Hint: Use pop() to remove last element in JS array [OK]

Common Mistakes:

• Assuming removeLast() exists in JS arrays
• Trying to pass arguments to pop() or removeLast()
• Confusing linked list methods with array methods

5. You want to implement a deque that supports the following operations efficiently: addFront, addRear, removeFront, removeRear. Which data structure is best suited for this and why?

hard

A. Array, because it allows fast insertion and deletion at both ends.

B. Stack, because it supports adding and removing elements efficiently.

C. Singly linked list, because it allows fast insertion and deletion at both ends.

D. Doubly linked list, because it allows fast insertion and deletion at both ends without shifting elements.

Solution

1. Step 1: Analyze operation requirements

   We need fast insertion and deletion at both front and rear ends.

2. Step 2: Compare data structures

   Array requires shifting elements for front operations, making it inefficient.
   Singly linked list allows fast insertion/removal only at one end efficiently.
   Doubly linked list allows fast insertion/removal at both ends without shifting.
   Stack supports operations only at one end.

3. Final Answer:

   Doubly linked list, because it allows fast insertion and deletion at both ends without shifting elements. -> Option D

4. Quick Check:

   Doubly linked list = best for deque operations [OK]

Hint: Use doubly linked list for efficient double-ended ops [OK]

Common Mistakes:

• Choosing array ignoring shifting cost
• Assuming singly linked list supports both ends efficiently
• Confusing stack with deque