Queue Implementation Using Linked List in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a queue and how does it work?

A queue is a data structure that works like a line of people waiting. The first person to get in line is the first to be served. This is called FIFO (First In, First Out).

beginner

What is the role of a linked list in implementing a queue?

A linked list helps to build a queue by connecting nodes one after another. Each node holds data and a link to the next node, making it easy to add at the end and remove from the front.

beginner

What are the main operations of a queue implemented with a linked list?

The main operations are enqueue (add to the end), dequeue (remove from the front), peek (see the front item), and isEmpty (check if the queue has no items).

intermediate

Why is it efficient to keep track of both front and rear pointers in a linked list queue?

Keeping front and rear pointers allows quick access to both ends. Enqueue adds at rear quickly, and dequeue removes from front quickly, both in constant time.

beginner

What happens when you dequeue from an empty queue implemented with a linked list?

If the queue is empty, dequeue should handle it safely by returning null or an error message, because there is no item to remove.

In a queue implemented using a linked list, where do you add new elements?

A In the middle of the linked list

B At the front (start) of the linked list

C At the rear (end) of the linked list

D Anywhere in the linked list

New elements are added at the rear to maintain the FIFO order.

What does the dequeue operation do in a linked list queue?

A Removes the element at the rear

B Removes the element at the front

C Adds a new element at the front

D Adds a new element at the rear

Dequeue removes the element at the front, following FIFO.

Why do we need a rear pointer in a linked list queue?

A To quickly add new elements at the end

B To quickly remove elements from the front

C To find the middle element

D To reverse the queue

The rear pointer helps add new elements quickly at the end.

What is the time complexity of enqueue and dequeue operations in a linked list queue?

A Both are O(1)

B Enqueue is O(n), Dequeue is O(1)

C Enqueue is O(1), Dequeue is O(n)

D Both are O(n)

Both enqueue and dequeue operations take constant time O(1) with front and rear pointers.

What should happen if you try to dequeue from an empty queue?

A Crash the program

B Add a new element automatically

C Remove the last element

D Return null or indicate the queue is empty

Dequeue from an empty queue should safely return null or an empty indication.

Explain how a queue works when implemented using a linked list. Include how enqueue and dequeue operations are done.

Think about how people line up and leave in order.

Describe why keeping track of both front and rear pointers is important in a linked list queue.

Imagine you want to add or remove people quickly from a line.

Practice

1. What is the main advantage of implementing a Queue using a linked list over an array?

easy

A. Dynamic size without fixed capacity

B. Faster random access to elements

C. Uses less memory than arrays

D. Elements are stored in sorted order automatically

Solution

1. Step 1: Understand array limitations

   Arrays have fixed size or require resizing which is costly.

2. Step 2: Linked list flexibility

   Linked lists grow dynamically without fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity -> Option A

4. Quick Check:

   Linked list queues grow dynamically = A [OK]

Hint: Linked list queues grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking linked lists allow faster random access
• Assuming linked lists use less memory always
• Believing queues sort elements automatically

2. Which of the following is the correct TypeScript syntax to define a node class for a linked list queue?

easy

A. class Node { value: number; next: null; constructor(value: number) { this.value = value; this.next = null; } }

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

C. class Node { val: number; next: Node | null; constructor(val: number) { this.val = val; this.next = null; } }

D. class Node { value: number; next: Node; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check property types

   Node must have a value and next pointer which can be null.

2. Step 2: Validate constructor initialization

   Constructor sets value and initializes next to null.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option B

4. Quick Check:

   Node next can be null, initialized in constructor = D [OK]

Hint: Node next pointer must allow null for end of list [OK]

Common Mistakes:

• Setting next to undefined instead of null
• Using wrong property names like val instead of value
• Declaring next as only Node without null option

3. Consider this TypeScript code snippet for a linked list queue:

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

class Queue {
  front: Node | null = null;
  rear: Node | null = null;

  enqueue(value: number) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode;
      return;
    }
    this.rear.next = newNode;
    this.rear = newNode;
  }

  dequeue(): number | null {
    if (!this.front) return null;
    const value = this.front.value;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    return value;
  }
}

const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);
q.dequeue();
q.enqueue(40);
q.enqueue(50);
q.dequeue();

What is the value returned by the last dequeue() call?

medium

A. 50

B. 40

C. 30

D. 20

Solution

1. Step 1: Trace enqueue and dequeue operations

   Queue after operations: - enqueue 10: front=10, rear=10 - enqueue 20: front=10, rear=20 - dequeue(): removes 10, front=20 - enqueue 30: rear=30 - dequeue(): removes 20, front=30 - enqueue 40: rear=40 - enqueue 50: rear=50 - dequeue(): removes 30, front=40

2. Step 2: Identify last dequeue return value

   The last dequeue removes 30 and returns it.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Last dequeue returns 30 = A [OK]

Hint: Track front pointer after each dequeue [OK]

Common Mistakes:

• Confusing rear value with dequeued value
• Not updating front after dequeue
• Assuming dequeue returns rear value

4. The following TypeScript code attempts to implement dequeue() for a linked list queue:

dequeue(): number | null {
  if (!this.front) return null;
  const value = this.front.value;
  this.front = this.front.next;
  return value;
}

What is the bug in this code?

medium

A. It returns the wrong value from the queue

B. It incorrectly sets front to null always

C. It does not check if front is null before accessing value

D. It does not update rear when queue becomes empty

Solution

1. Step 1: Analyze dequeue logic

   It removes front node and updates front pointer correctly.

2. Step 2: Check rear pointer update

   If queue becomes empty (front is null), rear must also be set to null but code misses this.

3. Final Answer:

   It does not update rear when queue becomes empty -> Option D

4. Quick Check:

   Rear must be null if front is null after dequeue = B [OK]

Hint: Set rear to null when front becomes null after dequeue [OK]

Common Mistakes:

• Ignoring rear pointer update on empty queue
• Assuming front check is enough
• Returning wrong value from dequeue

5. You want to implement a peek() method for your linked list queue that returns the front element without removing it. Which of the following implementations is correct?

hard

A. peek(): number | null { return this.front ? this.front.value : null; }

B. peek(): number | null { return this.rear ? this.rear.value : null; }

C. peek(): number | null { if (!this.front) throw new Error('Empty'); return this.front.next.value; }

D. peek(): number | null { return this.front.next ? this.front.next.value : null; }

Solution

1. Step 1: Understand peek purpose

   Peek returns front element value without removing it.

2. Step 2: Check each option

   A throws error and returns front.next value, wrong.
   B returns rear value, incorrect.
   C returns front value or null if empty, correct.
   D returns front.next value or null, wrong.

3. Final Answer:

   peek(): number | null { return this.front ? this.front.value : null; } -> Option A

4. Quick Check:

   Peek returns front value safely = C [OK]

Hint: Peek returns front value without changing queue [OK]

Common Mistakes:

• Returning rear value instead of front
• Accessing front.next without checking front
• Throwing error instead of returning null on empty