How to Implement Queue Using Linked List: Simple Guide

To implement a queue using a linked list, create nodes where each node points to the next. Maintain two pointers: front for dequeue operations and rear for enqueue operations, adding new nodes at the rear and removing from the front.

Syntax

A queue using a linked list typically has a Node class with data and a pointer to the next node. The Queue class maintains two pointers: front (first element) and rear (last element). The main operations are:

• enqueue(data): Add a node at the rear.
• dequeue(): Remove a node from the front.
• isEmpty(): Check if the queue is empty.

javascript

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

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

    enqueue(data) {
        const newNode = new Node(data);
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
    }

    dequeue() {
        if (!this.front) return null;
        const removedData = this.front.data;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        return removedData;
    }

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

Example

This example shows how to create a queue, add elements with enqueue, remove elements with dequeue, and check if the queue is empty.

javascript

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

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

    enqueue(data) {
        const newNode = new Node(data);
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
    }

    dequeue() {
        if (!this.front) return null;
        const removedData = this.front.data;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        return removedData;
    }

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

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
console.log(queue.isEmpty());  // false
console.log(queue.dequeue()); // 30
console.log(queue.isEmpty());  // true

Output

10
20
false
30
true

Common Pitfalls

Common mistakes include:

• Not updating the rear pointer when the queue becomes empty after dequeue.
• Forgetting to set front and rear to null initially.
• Not handling the case when the queue is empty before dequeuing, which can cause errors.

Always check if the queue is empty before removing elements and update pointers carefully.

javascript

/* Wrong: Not updating rear when queue becomes empty */
class QueueWrong {
    constructor() {
        this.front = null;
        this.rear = null;
    }

    enqueue(data) {
        const newNode = { data, next: null };
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
    }

    dequeue() {
        if (!this.front) return null;
        const removedData = this.front.data;
        this.front = this.front.next;
        // Missing: if front is null, rear should also be null
        return removedData;
    }
}

/* Correct: Update rear to null when queue is empty */
class QueueCorrect {
    constructor() {
        this.front = null;
        this.rear = null;
    }

    enqueue(data) {
        const newNode = { data, next: null };
        if (this.rear) {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        if (!this.front) {
            this.front = newNode;
        }
    }

    dequeue() {
        if (!this.front) return null;
        const removedData = this.front.data;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        return removedData;
    }
}

Quick Reference

Queue Using Linked List Cheat Sheet:

Operation	Description
enqueue(data)	Adds an element at the rear of the queue.
dequeue()	Removes and returns the element at the front of the queue.
isEmpty()	Returns true if the queue has no elements.
front	Pointer to the first node in the queue.
rear	Pointer to the last node in the queue.

Operation	Description
enqueue(data)	Adds an element at the rear of the queue.
dequeue()	Removes and returns the element at the front of the queue.
isEmpty()	Returns true if the queue has no elements.
front	Pointer to the first node in the queue.
rear	Pointer to the last node in the queue.

Key Takeaways

Use two pointers, front and rear, to efficiently manage queue operations in a linked list.

Always update rear to null when the queue becomes empty after dequeue.

Check if the queue is empty before dequeuing to avoid errors.

Enqueue adds nodes at the rear; dequeue removes nodes from the front.

A linked list queue dynamically grows and shrinks without fixed size limits.