Queue Implementation Using Linked List in DSA Typescript - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line at a coffee shop where customers wait their turn. We want to create a queue data structure that works like this line, using a linked list to keep track of customers.

🎯 Goal: Build a queue using a linked list in TypeScript. You will create nodes, add customers to the queue, remove them in order, and finally print the queue state.

📋 What You'll Learn

Create a Node class with value and next properties

Create a Queue class with front and rear properties

Implement enqueue method to add nodes to the rear

Implement dequeue method to remove nodes from the front

Print the queue contents showing all values from front to rear

💡 Why This Matters

🌍 Real World

Queues are used in real life for managing lines, like customers waiting for service, print jobs, or tasks waiting to be processed.

💼 Career

Understanding queues and linked lists is essential for software developers working on scheduling, resource management, and real-time systems.

1

Create Node and Queue classes

Create a class called Node with a constructor that takes a value of type string and a next property initialized to null. Then create a class called Queue with front and rear properties both initialized to null.

DSA Typescript

class Node {
  value: string;
  next: Node | null;
  constructor(value: string) {
    // Your code here
  }
}

class Queue {
  front: Node | null;
  rear: Node | null;
  constructor() {
    // Your code here
  }
}

Hint

Remember to set next to null in the Node constructor and initialize front and rear to null in the Queue constructor.

2

Add enqueue method to Queue

Add a method called enqueue to the Queue class. It takes a value of type string, creates a new Node, and adds it to the rear of the queue. If the queue is empty, set both front and rear to the new node. Otherwise, link the current rear node's next to the new node and update rear.

DSA Typescript

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

class Queue {
  front: Node | null;
  rear: Node | null;
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(value: string): void {
    // Your code here
  }
}

Hint

Check if rear is null to handle empty queue, else link new node at the end.

3

Add dequeue method to Queue

Add a method called dequeue to the Queue class. It removes the node at the front of the queue and returns its value. If the queue is empty, return null. Update front to the next node. If after removal the queue becomes empty, set rear to null.

DSA Typescript

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

class Queue {
  front: Node | null;
  rear: Node | null;
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(value: string): void {
    const newNode = new Node(value);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

  dequeue(): string | null {
    // Your code here
  }
}

Hint

Remember to check if the queue is empty before removing, and update rear if queue becomes empty after removal.

4

Print the queue contents

Add a method called printQueue to the Queue class. It prints all the values in the queue from front to rear separated by -> and ending with null. Then create a Queue instance, enqueue "Alice", "Bob", and "Charlie", dequeue one element, and print the queue.

DSA Typescript

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

class Queue {
  front: Node | null;
  rear: Node | null;
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(value: string): void {
    const newNode = new Node(value);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

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

  printQueue(): void {
    // Your code here
  }
}

const queue = new Queue();
queue.enqueue("Alice");
queue.enqueue("Bob");
queue.enqueue("Charlie");
queue.dequeue();
queue.printQueue();

Hint

Traverse from front to rear, appending each value and -> . End with null. Then print the string.

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