Queue Implementation Using Linked List in DSA Typescript - Time & Space Complexity

Time Complexity: Queue Implementation Using Linked List

O(1)

Understanding Time Complexity

We want to understand how fast queue operations run when using a linked list.

Specifically, how the time to add or remove items changes as the queue grows.

Scenario Under Consideration

Analyze the time complexity of the following queue operations using a linked list.

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

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;
    } else {
      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;
  }
}
    

This code adds items to the end and removes from the front of a linked list to form a queue.

Identify Repeating Operations

Look for loops or repeated steps inside enqueue and dequeue.

• Primary operation: Adding or removing a single node pointer.
• How many times: Each operation does a fixed number of steps, no loops.

How Execution Grows With Input

Each enqueue or dequeue does the same small number of steps no matter how big the queue is.

Input Size (n)	Approx. Operations
10	5-6 steps per operation
100	5-6 steps per operation
1000	5-6 steps per operation

Pattern observation: The time stays about the same no matter how many items are in the queue.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same short time regardless of queue size.

Common Mistake

[X] Wrong: "Removing from the front takes longer as the queue grows because we have to move through nodes."

[OK] Correct: We keep a direct pointer to the front node, so removal is always quick without searching.

Interview Connect

Knowing that queue operations run in constant time shows you understand efficient data structure design.

Self-Check

What if we did not keep a rear pointer and had to find the end each time? How would the time complexity change?

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