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

Queue Implementation Using Linked List

📖 Scenario: Imagine you are managing a line of customers waiting to buy tickets. You want to keep track of who is next in line and who just joined the line. A queue is perfect for this because it works like a real line: first come, first served.

🎯 Goal: You will build a queue using a linked list in JavaScript. This queue will let you add customers to the end of the line and remove customers from the front, just like a real queue.

📋 What You'll Learn

Create a Node class to hold each customer's name and a pointer to the next customer.

Create a Queue class with methods to add (enqueue) and remove (dequeue) customers.

Keep track of the front and rear of the queue.

Print the queue contents showing the order of customers.

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like customers waiting or tasks waiting to be processed.

💼 Career

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

1

Create Node Class for Queue Elements

Create a class called Node with a constructor that takes a parameter value. Inside the constructor, set this.value to value and this.next to null.

DSA Javascript

# Your code here
// Create Node class with constructor(value) setting this.value and this.next

Hint

Think of each node as a person in line holding their name and a pointer to the next person.

2

Create Queue Class with Front and Rear

Create a class called Queue with a constructor that sets this.front and this.rear to null.

DSA Javascript

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

# Your code here
// Create Queue class with constructor setting this.front and this.rear to null

Hint

The queue needs to know who is first (front) and who is last (rear) in line.

3

Add Enqueue and Dequeue Methods

Inside the Queue class, add a method called enqueue(value) that creates a new Node with value. If the queue is empty, set both front and rear to the new node. Otherwise, set rear.next to the new node and update rear to the new node. Also add a method called dequeue() that removes the front node and returns its value. If the queue becomes empty after dequeue, set rear to null.

DSA Javascript

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

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

    # Your code here
    // Add enqueue(value) and dequeue() methods
}

Hint

Enqueue adds to the end, dequeue removes from the front. Remember to update front and rear carefully.

4

Print Queue Contents

Add a method called printQueue() inside the Queue class that prints the queue values from front to rear separated by -> and ending with null. Then create a queue, enqueue 'Alice', 'Bob', and 'Charlie', dequeue once, and print the queue.

DSA Javascript

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

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

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

    dequeue() {
        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;
    }

    # Your code here
    // Add printQueue() method
}

// Create queue, enqueue 'Alice', 'Bob', 'Charlie', dequeue once, print queue

Hint

Traverse from front to rear, adding each value to a string with arrows, then print it.

Practice

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

easy

A. Simpler syntax for insertion and deletion

B. Faster random access to elements

C. Uses less memory than arrays

D. Dynamic size without fixed capacity limits

Solution

1. Step 1: Understand queue size limitations in arrays

   Arrays have fixed size or require resizing, which can be costly.

2. Step 2: Linked list dynamic size advantage

   Linked lists grow and shrink dynamically without fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity limits -> Option D

4. Quick Check:

   Linked list queues grow dynamically [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow faster random access
• Assuming linked lists always use less memory
• Confusing syntax simplicity with performance

2. Which of the following is the correct way to add a new node to the end of a linked list queue in JavaScript?

easy

A. tail.next = newNode; tail = newNode;

B. head.next = newNode; head = newNode;

C. newNode.next = tail; tail = newNode;

D. newNode.next = head; head = newNode;

Solution

1. Step 1: Identify tail pointer usage in queue enqueue

   New nodes are added at the tail; tail.next points to new node.

2. Step 2: Update tail to new node

   After adding, tail must point to the new node to keep queue end updated.

3. Final Answer:

   tail.next = newNode; tail = newNode; -> Option A

4. Quick Check:

   Enqueue adds at tail [OK]

Hint: Enqueue adds at tail: tail.next = newNode; tail = newNode [OK]

Common Mistakes:

• Adding new node at head instead of tail
• Not updating tail pointer after insertion
• Confusing head and tail pointers

3. You want to implement a method peek() for a linked list queue that returns the front element without removing it. Which is the correct implementation?

easy

A. return this.head ? this.head.value : null;

B. return this.tail ? this.tail.value : null;

C. return this.head.next ? this.head.next.value : null;

D. return this.tail.next ? this.tail.next.value : null;

Solution

1. Step 1: Understand peek operation in queue

   Peek returns front element without removing it, which is at head in linked list queue.

2. Step 2: Check correct pointer for front element

   Head points to front node; tail points to end node. So return head.value if head exists.

3. Final Answer:

   return this.head ? this.head.value : null; -> Option A

4. Quick Check:

   Peek returns head value [OK]

Hint: Peek returns head value without dequeue [OK]

Common Mistakes:

• Returning tail value instead of head
• Accessing next of tail which is always null
• Returning head.next value which skips front

4. Consider this JavaScript code for a linked list queue:

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  enqueue(value) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }
  dequeue() {
    if (!this.head) return null;
    const val = this.head.value;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    return val;
  }
}

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();
console.log(q.head.value);

What will be printed?

medium

A. 20

B. 40

C. 50

D. 30

Solution

1. Step 1: Trace enqueue and dequeue operations

   Queue after operations: - enqueue 10: head=10, tail=10 - enqueue 20: head=10->20, tail=20 - dequeue: removes 10, head=20 - enqueue 30: head=20->30, tail=30 - dequeue: removes 20, head=30 - enqueue 40: head=30->40, tail=40 - enqueue 50: head=30->40->50, tail=50 - dequeue: removes 30, head=40

2. Step 2: Identify current head value

   After last dequeue, head points to node with value 40.

3. Final Answer:

   40 -> Option B

4. Quick Check:

   Final head value after operations = 40 [OK]

Hint: Track head after each dequeue to find current front [OK]

Common Mistakes:

• Forgetting to update tail when queue becomes empty
• Mixing up enqueue and dequeue order
• Assuming head value is unchanged after dequeue

5. The following dequeue method for a linked list queue has a bug:

dequeue() {
  if (!this.head) return null;
  const val = this.head.value;
  this.head = this.head.next;
  return val;
}

What is the problem?

medium

A. It removes the tail instead of the head

B. It returns the wrong value

C. It does not update tail when queue becomes empty

D. It causes infinite loop

Solution

1. Step 1: Analyze dequeue method behavior

   It removes head by moving head pointer to next node and returns old head value.

2. Step 2: Identify missing tail update

   If after removal head becomes null (queue empty), tail still points to old node causing inconsistency.

3. Final Answer:

   It does not update tail when queue becomes empty -> Option C

4. Quick Check:

   Empty queue must reset tail = null [OK]

Hint: Reset tail to null when head becomes null after dequeue [OK]

Common Mistakes:

• Ignoring tail pointer update on empty queue
• Confusing head and tail roles
• Assuming dequeue removes tail node