Table of contents

Introduction

Operation on Linked Queue

2.1.

1. Insertion operation

2.1.1.

Algorithm of Insertion operation

2.1.2.

Code Implementation

2.2.

2.3.

C++

2.4.

Java

2.5.

Python

2.6.

2. Deletion Operation

2.6.1.

Algorithm of Deletion Operation

2.6.2.

Code Implementation

2.7.

2.8.

C++

2.9.

Java

2.10.

Python

Implementation of queue using linked list

3.1.

Algorithm for Queue Implementation Using Linked List

3.2.

Code Implementation

3.3.

3.4.

C++

3.5.

Java

3.6.

Python

3.7.

Complexity Analysis

Frequently Asked Questions

4.1.

Is it possible to implement a stack using a queue?

4.2.

What is the difference between circular queue and linked list queue?

4.3.

Which node is removed during the deletion operation in a linked list implementation of a queue?

4.4.

Is it better to implement queue with linked list or array?

Conclusion

Last Updated: Oct 7, 2024

Easy

Implementation of Queue using Linked list

Author Amarjeet kumar

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

A queue is a linear Data Structure that operates on the concept of first-in, first-out (FIFO). Enqueue and dequeue activities are supported by Queue. The advantage of utilizing linked lists instead of arrays to create a queue is that it allows the Queue to grow as needed, i.e., memory may be allocated dynamically.

In this article, we will look at the implementation of queue using linked list in data structure. Using a linked list implies that we'll be storing data in the form of nodes that match the Queue's rules. According to the queue rule, insertion occurs at one end, and deletion occurs at the other, i.e., First In, First Out (FIFO).

Operation on Linked Queue

There are two operations which can be implemented on the linked queues:-

Insert operation
Deletion operation

Now lets learn about them in detail

1. Insertion operation

In a linked queue, the insertion operation adds an element to the rear (tail) of the queue. It involves creating a new node with the element and updating the rear pointer to this new node. If the queue is empty, both the front and rear pointers are set to the new node. This ensures that elements are added in FIFO order.

Algorithm of Insertion operation

Make a new pointer for a node.
Now there are two possibilities: either the queue is empty or the queue has at least one piece.
If the queue is empty, the new node will be both front and rear, with the next pointer of both front and rear pointing to NULL.
The condition front == NULL becomes false if the queue has at least one element. As a result, direct the next pointer of the rear to the newly generated node ptr and the rear pointer to the newly created node ptr.

Code Implementation

C
C++
Java
Python

C

#include <stdio.h>
#include <stdlib.h>

struct node {
int val;
struct node* next;
};
/* Creating structure for rear and front*/
struct node* rear;
struct node* front;


/* creating separate inserting function */
void insertfun(struct node *pt, int item) {

pt = (struct node *) malloc (sizeof(struct node));
if (pt == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
pt -> val = item;
if (front == NULL) {
front = pt;
rear = pt;
front -> next = NULL;
rear -> next = NULL;
} else {
rear -> next = pt;
rear = pt;
rear->next = NULL;
}
}
}

int main() {
struct node* head = NULL;
insertfun(head, 10);
insertfun(head, 20);
/* Printing function use to show the output*/
printf("front element: %d", front->val);
return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>

struct Node {
    int val;
    Node* next;
};

// Global pointers for the front and rear of the queue
Node* rear = nullptr;
Node* front = nullptr;

// Function to insert an element into the queue
void insertFun(int item) {
    Node* pt = new Node;
    if (!pt) {
        std::cout << "\nOVERFLOW\n";
        return;
    } else {
        pt->val = item;
        pt->next = nullptr;
        if (front == nullptr) {
            front = pt;
            rear = pt;
        } else {
            rear->next = pt;
            rear = pt;
        }
    }
}

int main() {
    insertFun(10);
    insertFun(20);
    // Printing the front element
    std::cout << "Front element: " << front->val << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class Node {
    int val;
    Node next;
}

// LinkedQueue class with front and rear pointers
class LinkedQueue {
    Node rear = null;
    Node front = null;

    // Method to insert an element into the queue
    void insertFun(int item) {
        Node pt = new Node();
        pt.val = item;
        pt.next = null;
        if (front == null) {
            front = pt;
            rear = pt;
        } else {
            rear.next = pt;
            rear = pt;
        }
    }

    // Method to get the front element
    int getFront() {
        if (front != null) {
            return front.val;
        }
        throw new RuntimeException("Queue is empty");
    }

    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        queue.insertFun(10);
        queue.insertFun(20);
        // Printing the front element
        System.out.println("Front element: " + queue.getFront());
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.rear = None
        self.front = None

    def insert_fun(self, item):
        pt = Node(item)
        if self.front is None:
            self.front = pt
            self.rear = pt
        else:
            self.rear.next = pt
            self.rear = pt

    def get_front(self):
        if self.front is not None:
            return self.front.val
        raise Exception("Queue is empty")

# Example usage
queue = LinkedQueue()
queue.insert_fun(10)
queue.insert_fun(20)
# Printing the front element
print(f"Front element: {queue.get_front()}")

You can also try this code with Online Python Compiler

Run Code

Output

front element: 10

You can also try this code with Online C Compiler

Run Code

2. Deletion Operation

In a linked queue, the deletion operation removes an element from the front of the queue. It involves updating the front pointer to the next node and freeing the memory of the removed node. If the queue becomes empty, both the front and rear pointers are set to NULL.

Algorithm of Deletion Operation

Check to see if the queue is empty.
We just print 'underflow' on the screen and quit if the Queue is empty, i.e., front==NULL.
Delete the element at which the front pointer is pointing if the queue is not empty. To delete a node, copy the front pointer's node into the pointer ptr, make the front pointer refer to the front's next node, and release the node indicated by the node ptr. The following sentence may be used to do this:

Code Implementation

C
C++
Java
Python

C

#include <stdio.h>
#include <stdlib.h>

struct node {
int val;
struct node* next;
};

struct node* front;
struct node* rear;

/* creating separate inserting function */
void insertfun(struct node *pt, int item) {

pt = (struct node *) malloc (sizeof(struct node));
if (pt == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
pt -> val = item;
if (front == NULL) {
front = pt;
rear = pt;
front -> next = NULL;
rear -> next = NULL;
} else {
rear -> next = pt;
rear = pt;
rear->next = NULL;
}
}
}
/* creating septate function for deletion of node*/
void deleteNode (struct node *pt) {  
    if (front == NULL) {  
        printf("Underflow");  
        return;  
    } else {  
        pt = front;  
        front = front -> next;  
        free(pt);  
    }  
}  
/*main function */ 
int main() {
struct node* head = NULL;
insertfun(head, 10);
insertfun(head, 20);
/* Printing function use to show the output*/
      printf("front element: %d\n", front->val);
deleteNode(head); 
printf("front element: %d", front->val);
return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>

struct Node {
    int val;
    Node* next;
};

// Global pointers for the front and rear of the queue
Node* rear = nullptr;
Node* front = nullptr;

// Function to insert an element into the queue
void insertFun(int item) {
    Node* pt = new Node;
    if (!pt) {
        std::cout << "\nOVERFLOW\n";
        return;
    } else {
        pt->val = item;
        pt->next = nullptr;
        if (front == nullptr) {
            front = pt;
            rear = pt;
        } else {
            rear->next = pt;
            rear = pt;
        }
    }
}

// Function to delete an element from the queue
void deleteNode() {
    if (front == nullptr) {
        std::cout << "Underflow\n";
        return;
    } else {
        Node* pt = front;
        front = front->next;
        delete pt;
        if (front == nullptr) { // If the queue becomes empty
            rear = nullptr;
        }
    }
}

int main() {
    insertFun(10);
    insertFun(20);

    // Printing the front element
    std::cout << "Front element: " << front->val << std::endl;

    deleteNode();

    // Printing the new front element after deletion
    if (front != nullptr) {
        std::cout << "Front element after deletion: " << front->val << std::endl;
    } else {
        std::cout << "Queue is empty\n";
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class Node {
    int val;
    Node next;
}

class LinkedQueue {
    Node rear = null;
    Node front = null;

    // Method to insert an element into the queue
    void insertFun(int item) {
        Node pt = new Node();
        pt.val = item;
        pt.next = null;
        if (front == null) {
            front = pt;
            rear = pt;
        } else {
            rear.next = pt;
            rear = pt;
        }
    }

    // Method to delete an element from the queue
    void deleteNode() {
        if (front == null) {
            System.out.println("Underflow");
        } else {
            front = front.next;
            if (front == null) { // If the queue becomes empty
                rear = null;
            }
        }
    }

    // Method to get the front element
    int getFront() {
        if (front != null) {
            return front.val;
        }
        throw new RuntimeException("Queue is empty");
    }

    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        queue.insertFun(10);
        queue.insertFun(20);

        // Printing the front element
        System.out.println("Front element: " + queue.getFront());

        queue.deleteNode();

        // Printing the new front element after deletion
        try {
            System.out.println("Front element after deletion: " + queue.getFront());
        } catch (RuntimeException e) {
            System.out.println("Queue is empty");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.rear = None
        self.front = None

    def insert_fun(self, item):
        pt = Node(item)
        if self.front is None:
            self.front = pt
            self.rear = pt
        else:
            self.rear.next = pt
            self.rear = pt

    def delete_node(self):
        if self.front is None:
            print("Underflow")
        else:
            self.front = self.front.next
            if self.front is None:  # If the queue becomes empty
                self.rear = None

    def get_front(self):
        if self.front is not None:
            return self.front.val
        raise Exception("Queue is empty")

# Example usage
queue = LinkedQueue()
queue.insert_fun(10)
queue.insert_fun(20)

# Printing the front element
print(f"Front element: {queue.get_front()}")

queue.delete_node()

# Printing the new front element after deletion
try:
    print(f"Front element after deletion: {queue.get_front()}")
except Exception as e:
    print(e)

You can also try this code with Online Python Compiler

Run Code

Output

front element: 10
front element: 20

Implementation of queue using linked list

Algorithm for Queue Implementation Using Linked List

Node Definition: Define a node structure with data and a pointer to the next node.
Queue Initialization: Initialize two pointers, front and rear, to NULL.
Enqueue Operation (Insertion):
1. Create a new node with the given data.
2. If the queue is empty (front is NULL), set both front and rear to the new node.
3. Otherwise, link the new node to the current rear, and update rear to the new node.
Dequeue Operation (Deletion):
1. If the queue is empty (front is NULL), report an underflow condition.
2. Otherwise, remove the node at the front, update front to the next node, and free the old node.
3. If the queue becomes empty after the operation, set rear to NULL.
Peek Operation (Optional):
1. Return the data from the front node without removing it.

Code Implementation

C
C++
Java
Python

C

#include <stdio.h>
#include <stdlib.h>

// Define the node structure
struct Node {
    int data;
    struct Node* next;
};

// Initialize front and rear pointers
struct Node* front = NULL;
struct Node* rear = NULL;

// Enqueue operation
void enqueue(int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Overflow\n");
        return;
    }
    newNode->data = item;
    newNode->next = NULL;
    if (rear == NULL) {
        front = newNode;
        rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

// Dequeue operation
void dequeue() {
    if (front == NULL) {
        printf("Underflow\n");
        return;
    }
    struct Node* temp = front;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
}

// Peek operation
int peek() {
    if (front != NULL) {
        return front->data;
    }
    return -1; // Indicating queue is empty
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Front element: %d\n", peek());
    dequeue();
    printf("Front element after dequeue: %d\n", peek());
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() : front(nullptr), rear(nullptr) {}

    void enqueue(int item) {
        Node* newNode = new Node(item);
        if (rear == nullptr) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (front == nullptr) {
            std::cout << "Underflow\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }

    int peek() {
        if (front != nullptr) {
            return front->data;
        }
        return -1; // Indicating queue is empty
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    std::cout << "Front element: " << q.peek() << std::endl;
    q.dequeue();
    std::cout << "Front element after dequeue: " << q.peek() << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class Queue {
    Node front, rear;

    Queue() {
        front = rear = null;
    }

    void enqueue(int item) {
        Node newNode = new Node(item);
        if (rear == null) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (front == null) {
            System.out.println("Underflow");
            return;
        }
        front = front.next;
        if (front == null) {
            rear = null;
        }
    }

    int peek() {
        if (front != null) {
            return front.data;
        }
        throw new RuntimeException("Queue is empty");
    }
}

public class Main {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        System.out.println("Front element: " + q.peek());
        q.dequeue();
        System.out.println("Front element after dequeue: " + q.peek());
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            print("Underflow")
            return
        self.front = self.front.next
        if self.front is None:
            self.rear = None

    def peek(self):
        if self.front is not None:
            return self.front.data
        raise Exception("Queue is empty")

# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
print(f"Front element: {queue.peek()}")
queue.dequeue()
print(f"Front element after dequeue: {queue.peek()}")

You can also try this code with Online Python Compiler

Run Code

Output

Front element: 10 
Front element after dequeue: 20

Complexity Analysis

Time Complexity:

Enqueue: O(1)O(1)O(1) – Inserting at the rear takes constant time.
Dequeue: O(1)O(1)O(1) – Removing from the front takes constant time.

Space Complexity: O(n)

Space required for nnn nodes in the queue, where nnn is the number of elements. Each node consumes space for data and a pointer.

Frequently Asked Questions

Is it possible to implement a stack using a queue?

The first element is withdrawn from the stack (Out) and might be the final thing inserted at the top of the stack (In). A Queue class extends the Collection interface and offers first-in-first-out insert and delete actions (FIFO). In the program below, we may also implement a Stack using Queue.

What is the difference between circular queue and linked list queue?

A circular queue uses a fixed-size array where the rear connects back to the front, allowing efficient space utilization. In contrast, a linked list queue uses dynamically allocated nodes, which avoids size limitations but incurs overhead for node management.

Which node is removed during the deletion operation in a linked list implementation of a queue?

During the deletion operation in a linked list queue, the node at the front of the queue is removed. This node is the one that was added earliest and is the next to be processed.

Is it better to implement queue with linked list or array?

Implementing a queue with a linked list avoids fixed size limitations and dynamic resizing issues but has additional memory overhead. An array-based queue is simpler but requires resizing or has a fixed size, leading to potential space inefficiency.

Conclusion

This article has gone through The First in, First Out Principle that governs a queue, a linear data structure (FIFO). Concept of first-in, first-out (FIFO). Queue supports Enqueue and dequeue activities.