Do you think IIT Guwahati certified course can help you in your career?
No
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; }
// 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
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
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.
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; }
// 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
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
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
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
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.
Live masterclass
Microsoft SDE Roadmap: Use AI Tools to Succeed
by Pranav Malik
19 May, 2025
01:30 PM
Break into MAANG Data Analyst roles from Non-Tech Profession
by Abhishek Soni
20 May, 2025
01:30 PM
SDE LinkedIn & Naukri Hacks to Get More Recruiter Calls
by Shantanu Shubham
21 May, 2025
01:30 PM
Amazon Data Analyst: Advanced Excel & AI Interview Tips
by Megna Roy
22 May, 2025
01:30 PM
Microsoft SDE Roadmap: Use AI Tools to Succeed
by Pranav Malik
19 May, 2025
01:30 PM
Break into MAANG Data Analyst roles from Non-Tech Profession