Dequeue Using Linked List in DSA Typescript - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is dequeue empty?

↓

Set head & tail

↓

For insertRear: tail.next = new_node; new_node.prev = tail; tail = new_node

↓

For deleteFront: head = head.next; if head != null head.prev = null

↓

For deleteRear: tail = tail.prev; if tail != null tail.next = null

↓

Update size

↓

Done

Shows how nodes are added or removed from front or rear in a doubly linked list representing a dequeue.

Execution Sample

DSA Typescript

class Node {
  constructor(public data: number, public prev: Node | null = null, public next: Node | null = null) {}
}

class Dequeue {
  head: Node | null = null;
  tail: Node | null = null;
  size = 0;

  insertFront(data: number) {
    // insert at front logic
  }
}

Defines a doubly linked list node and a dequeue class with insertFront method to add nodes at front.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	insertFront(10)	10	head = new_node(10), tail = new_node(10)	10 <-> null
2	insertRear(20)	10 -> 20	tail.next = new_node(20), new_node.prev = tail, tail = new_node(20)	10 <-> 20 <-> null
3	insertFront(5)	5 -> 10 -> 20	new_node(5).next = head(10), head.prev = new_node(5), head = new_node(5)	5 <-> 10 <-> 20 <-> null
4	deleteFront()	10 -> 20	head = head.next(10), head.prev = null	10 <-> 20 <-> null
5	deleteRear()	10	tail = tail.prev(10), tail.next = null	10 <-> null
6	deleteFront()	empty	head = null, tail = null	null
7	deleteFront()	empty	No change, list empty	null

💡 Step 7 stops because list is empty, no nodes to delete.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7
head	null	Node(10)	Node(10)	Node(5)	Node(10)	Node(10)	null	null
tail	null	Node(10)	Node(20)	Node(20)	Node(20)	Node(10)	null	null
size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does deleteFront set head.prev to null after moving head?

Because after removing the first node, the new head has no previous node, so head.prev must be null to avoid dangling links (see Step 4 in execution_table).

What happens if we try to delete from an empty dequeue?

No changes occur because head and tail are already null, so deletion is skipped safely (see Step 7 in execution_table).

Why do we update tail.next to null after deleteRear?

Because the new tail node should not point to any next node, so tail.next is set to null to mark the end (see Step 5 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the visual state of the list?

A 5 <-> 10 <-> 20 <-> null

B 10 <-> 5 <-> 20 <-> null

C 20 <-> 10 <-> 5 <-> null

D 5 <-> 20 <-> 10 <-> null

💡 Hint

Check the Visual State column at Step 3 in execution_table.

At which step does the dequeue become empty?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the Nodes in List column for 'empty' state in execution_table.

If we insertRear(30) after Step 6, what will be the new tail data?

A 10

B 20

C 30

D null

💡 Hint

After Step 6, list is empty, so new node becomes both head and tail.

Concept Snapshot

Dequeue Using Linked List:
- Use doubly linked list nodes with prev and next pointers.
- insertFront: add node before head, update head.
- insertRear: add node after tail, update tail.
- deleteFront: remove head, update head and head.prev.
- deleteRear: remove tail, update tail and tail.next.
- Handle empty list by setting head and tail to null.

Full Transcript

This visualization shows how a dequeue is implemented using a doubly linked list. Nodes have pointers to previous and next nodes. Inserting at front adds a new node before the current head and updates the head pointer. Inserting at rear adds a new node after the tail and updates the tail pointer. Deleting from front removes the head node and updates the head pointer and its prev to null. Deleting from rear removes the tail node and updates the tail pointer and its next to null. The dequeue size updates accordingly. If the list is empty, deletion operations do nothing. The execution table traces each operation step-by-step, showing the nodes in the list, pointer changes, and the visual linked list state. The variable tracker shows how head, tail, and size change after each operation. Key moments clarify why pointers are updated to null after deletions and what happens when deleting from an empty list. The quiz tests understanding of the list state at various steps and effects of operations.

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