Queue Implementation Using Linked List in DSA Typescript

Mental Model

A queue is a line where the first person in is the first person out. Using a linked list means each person holds a note pointing to the next person.

Analogy: Imagine a line of people waiting to buy tickets. The first person to get in line is the first to get the ticket and leave. Each person holds the hand of the next person, so you can move along the line easily.

front -> [1] -> [2] -> [3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue once

Goal: Show how elements are added at the rear and removed from the front using linked list pointers

Step 1: enqueue 1: create node with value 1, front and rear point to it

front -> [1] -> null
rear ↑

Why: First element added, so front and rear both point here

Step 2: enqueue 2: create node with value 2, rear.next points to new node, rear moves to new node

front -> [1] -> [2] -> null
rear ↑

Why: Add new element at rear, update rear pointer

Step 3: enqueue 3: create node with value 3, rear.next points to new node, rear moves to new node

front -> [1] -> [2] -> [3] -> null
rear ↑

Why: Add new element at rear, update rear pointer

Step 4: dequeue: remove front node (value 1), front moves to next node

front -> [2] -> [3] -> null
rear ↑

Why: Remove element from front, update front pointer

Result:

front -> [2] -> [3] -> null
rear ↑

Annotated Code

DSA Typescript

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

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

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

  enqueue(value: number): void {
    const newNode = new Node(value);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
      return;
    }
    this.rear.next = newNode; // link new node at rear
    this.rear = newNode; // move rear pointer
  }

  dequeue(): number | null {
    if (this.front === null) {
      return null; // queue empty
    }
    const dequeuedValue = this.front.value;
    this.front = this.front.next; // move front pointer
    if (this.front === null) {
      this.rear = null; // queue became empty
    }
    return dequeuedValue;
  }

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

// Driver code
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.printQueue();
queue.dequeue();
queue.printQueue();

if (this.rear === null) { this.front = newNode; this.rear = newNode; return; }

handle empty queue by setting front and rear to new node

this.rear.next = newNode; this.rear = newNode;

link new node at rear and update rear pointer

if (this.front === null) { return null; }

check if queue is empty before dequeue

this.front = this.front.next; if (this.front === null) { this.rear = null; }

move front pointer forward; if queue empty, reset rear

Output

1 -> 2 -> 3 -> null

2 -> 3 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only update pointers without traversing the list

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

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making dequeue O(1) instead of O(n)

Edge Cases

dequeue from empty queue

returns null safely without error

DSA Typescript

if (this.front === null) { return null; }

enqueue first element into empty queue

front and rear both point to the new node

DSA Typescript

if (this.rear === null) { this.front = newNode; this.rear = newNode; return; }

dequeue last element making queue empty

front and rear both become null

DSA Typescript

if (this.front === null) { this.rear = null; }

When to Use This Pattern

When you need a first-in-first-out structure with efficient add and remove operations, use a queue with linked list to keep both operations fast.

Common Mistakes

Mistake: Not updating rear pointer after enqueue, causing rear to point to old node
Fix: Always move rear pointer to the new node after linking it

Mistake: Not resetting rear to null when queue becomes empty after dequeue
Fix: Check if front is null after dequeue and set rear to null to avoid dangling pointer

Summary

Implements a queue using a linked list where elements are added at the rear and removed from the front.

Use when you want a queue with efficient O(1) enqueue and dequeue operations without shifting elements.

The key is to keep track of both front and rear pointers to add and remove nodes quickly.

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