How to Implement Queue using Linked List

Last Updated on September 22, 2023 by Mayank Dham

In this article, we will learn what is the queue, the algorithm to implement queue using linked list, the algorithm of the queue with an example dry-run, the program to implement queue using linked list, and the applications of the queue.

What is the Queue?

A queue is a linear data structure in which there are two sides: the front side and the rear side. It follows the first in first out (FIFO) methodology. This is why it has two sides. From the front side, we will delete the data and from the rear side, we will insert the data in a queue. For example, people who stand in the queue at a bus station to buy a ticket.

Algorithm to Implement Queue Using Linked List

For insertion:

Step 1: Create a new linked list node with the given value.

Step 2: If the rear value is None then set the front and rear to the newly created node.

Step 3: Else set next of rear to the newly created node and move rear to that newly created node

For a deletion:

Step 1: If the front is NULL then return ‘queue is empty’

Step 2: else return the value at the front node and move the front to next of it.

Step 3: If the front is Null then set the rear to Null

Understand Queue with an example

We understood the concept of the queue. Now, we will learn about queues with the algorithm of a queue with an example.

Initialize the front and rear variables with NULL.

Operation 1: enqueue(10)

In this operation, first, we will create a new linked list node with the value 10. Now we will check if the rear is pointing to None or not. In this case, the rear is pointing to None so we will assign the front and rear both to the newly created node 10.

Operation 2: enqueue(20)

In this operation, first, we will create a new linked list node with the value 20. Now we will check if the rear is pointing to None or not. In this case, the rear is not pointing to None so we will assign the next of rear to the newly created node 20 and move the rear to 20. The front will remain the same.

Operation 3: dequeue()

In this operation, first, we will check if the front is not pointing to None. If the front is pointing to None it means the queue is empty. In this case, the front is pointing to 10 so we will return the value 10 and move the front pointer to the next of 10 and delete the node 10. The rear pointer will remain the same.

Operation 4: enqueue(30)

In this operation, first, we will create a new linked list node with the value 30. Now we will check if the rear is pointing to None or not. In this case, the rear is not pointing to None so we will assign the next of rear to the newly created node 30 and move the rear to 30. The front will remain the same.

Operation 5: enqueue(40)

In this operation, first, we will create a new linked list node with the value 40. Now we will check if the rear is pointing to None or not. In this case, the rear is not pointing to None so we will assign the next of rear to the newly created node 40 and move the rear to 40. The front will remain the same.

Operation 6: dequeue()

In this operation, first, we will check if the front is not pointing to None. If the front is pointing to None it means the queue is empty. In this case, the front is pointing to 20 so we will return the value 20 and move the front pointer to the next of 20 and delete the node 20. The rear pointer will remain the same.

Program to implement queue using linked list:

We have already seen how a linked list can be used to implement a queue. Now, let’s see how to write a program to implement queue using linked list.

// Java program to implement queue using linked list
public class PrepBytes {
    public static void main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
        System.out.printf("\nQueue after operation enqueue(10)\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
        
        q.enqueue(20);
        System.out.printf("\nQueue after operation enqueue(20)\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
        
        q.dequeue();
        System.out.printf("\nQueue after operation dequeue()\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
        
        q.enqueue(30);
        System.out.printf("\nQueue after operation enqueue(30)\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
        
        q.enqueue(40);
        System.out.printf("\nQueue after operation enqueue(40)\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
        
        q.dequeue();
        System.out.printf("\nQueue after operation dequeue()\n");
        System.out.println("Queue Front : " + q.front.key+" Queue Rear : " + q.rear.key);
    }
}

class QueueNode {
    int key;
    QueueNode next;

    // constructor to create a new linked list node
    public QueueNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
class Queue {
    QueueNode front, rear;

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

    void enqueue(int key)
    {

        // Create a new LL node
        QueueNode temp = new QueueNode(key);

        // If queue is empty, then new node is front and
        // rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }

        // Add the new node at the end of queue and change
        // rear
        this.rear.next = temp;
        this.rear = temp;
    }

    // Method to remove an key from queue.
    void dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
            return;

        // Store previous front and move front one node
        // ahead
        QueueNode temp = this.front;
        this.front = this.front.next;

        // If front becomes NULL, then change rear also as
        // NULL
        if (this.front == null)
            this.rear = null;
    }
}

Output:

Queue after operation enqueue(10)
Queue Front: 10 Queue Rear: 10

Queue after operation enqueue(20)
Queue Front: 10 Queue Rear: 20

Queue after operation dequeue()
Queue Front: 20 Queue Rear: 20

Queue after operation enqueue(30)
Queue Front: 20 Queue Rear: 30

Queue after operation enqueue(40)
Queue Front: 20 Queue Rear: 40

Queue after operation dequeue()
Queue Front: 30 Queue Rear: 40

Time complexity: O(1)
Space complexity: O(1)

Application of queue

• The queue is used for CPU scheduling and disk scheduling
• The queue is used for handling website traffic
• The queue is used to perform Breadth First Search (BFS) traversal
• The queue is used as a buffer on MP3 players and portable CD players.

FAQs related to queue using Linked List

1. Why to use a linked list to implement a queue over any other data structures?
We can use data structures such as array, linked list, or stack to implement a queue. The main benefit of using a linked list over other data structures is that we don’t need to worry about the capacity of the queue it can grow as per our requirements. The linked list provides dynamic memory.

2. Which operation is used in the queue?
A queue is an object used to manipulate an ordered collection of various data types. Below are the operations which we can perform on the queue.

3. Which is better stack or queue?
The stack can be used to solve recursive problems such as pre-order, post-order, and in-order traversal of the binary tree, whereas the queue can be used to solve problems such as the producer-consumer problem, which involves sequential processing of underlying data. Stack follows LIFO methodology while queue follows FIFO methodology.