Introduction to Implementation of Queue using Linked List
A queue is a linear data structure that follows the First in, First out principle(FIFO). Queue
supports operations like enqueue and dequeue. It can be implemented using an array and
linked list. The benefit of implementing a queue using a linked list over arrays is that it allows to
grow the queue as per the requirements, i.e., memory can be allocated dynamically.
What is Queue?
A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which
means that the element which is inserted first in the queue will be the first one to be removed
from the queue. A good example of a queue is a queue of customers purchasing a train ticket,
where the customer who comes first will be served first.
A linked queue is shown here: linked queue
Operation on Linked Queue
Each node of a linked queue consists of two fields: data and next(storing address of next node).
The data field of each node contains the assigned value, and the next points to the node
containing the next item in the queue.
A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front
pointer stores the address of the first element of the queue, and the rear pointer stores the
address of the last element of the queue.
Insertion is performed at the rear end, whereas deletion is performed at the front end of the
queue. If front and rear both points to NULL, it signifies that the queue is empty.
The two main operations performed on the linked queue are:
Insertion
Deletion
Insertion
Insert operation or insertion on a linked queue adds an element to the end of the queue. The
new element which is added becomes the last element of the queue.
Algorithm to perform Insertion on a linked queue:
Create a new node pointer.
ptr = (struct node *) malloc (sizeof(struct node));
Now, two conditions arise, i.e., either the queue is empty, or the queue contains at least one
element.
If the queue is empty, then the new node added will be both front and rear, and the next pointer
of front and rear will point to NULL.
If the queue contains at least one element, then the condition front == NULL becomes false. So,
make the next pointer of rear point to new node ptr and point the rear pointer to the newly
created node ptr
rear -> next = ptr;
rear = ptr;
Hence, a new node(element) is added to the queue.
C Function
#include < stdio.h >
#include < stdlib.h >
struct node {
int data;
struct node * next;
};
struct node * front;
struct node * rear;
void insert(struct node * ptr, int item) {
ptr = (struct node * ) malloc(sizeof(struct node));
if (ptr == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
ptr - > data = item;
if (front == NULL) {
front = ptr;
rear = ptr;
front - > next = NULL;
rear - > next = NULL;
} else {
rear - > next = ptr;
rear = ptr;
rear - > next = NULL;
}
}
}
int main() {
struct node * head = NULL;
insert(head, 10);
insert(head, 20);
printf("front element: %d", front - > data);
return 0;
}
Learn via video course
Topics Covered
Overview
In this article, we will learn about the implementation of queue data structure using a Linked List
in C language. Using a linked list means that we are going to store the information in the form of
nodes following the rules of the queue. The queue rule says that insertion takes place at one
end and deletion takes place at the other end, i.e., First In, First Out(FIFO).
Before reading this article, understand the following C Programming topics:
Linked List in C
Pointers in C
Introduction to Implementation of Queue using Linked List
A queue is a linear data structure that follows the First in, First out principle(FIFO). Queue
supports operations like enqueue and dequeue. It can be implemented using an array and
linked list. The benefit of implementing a queue using a linked list over arrays is that it allows to
grow the queue as per the requirements, i.e., memory can be allocated dynamically.
What is Queue?
A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which
means that the element which is inserted first in the queue will be the first one to be removed
from the queue. A good example of a queue is a queue of customers purchasing a train ticket,
where the customer who comes first will be served first.
A linked queue is shown here: linked queue
Operation on Linked Queue
Each node of a linked queue consists of two fields: data and next(storing address of next node).
The data field of each node contains the assigned value, and the next points to the node
containing the next item in the queue.
A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front
pointer stores the address of the first element of the queue, and the rear pointer stores the
address of the last element of the queue.
Insertion is performed at the rear end, whereas deletion is performed at the front end of the
queue. If front and rear both points to NULL, it signifies that the queue is empty.
The two main operations performed on the linked queue are:
Insertion
Deletion
Insertion
Insert operation or insertion on a linked queue adds an element to the end of the queue. The
new element which is added becomes the last element of the queue.
Algorithm to perform Insertion on a linked queue:
Create a new node pointer.
ptr = (struct node *) malloc (sizeof(struct node));
Now, two conditions arise, i.e., either the queue is empty, or the queue contains at least one
element.
If the queue is empty, then the new node added will be both front and rear, and the next pointer
of front and rear will point to NULL.
*ptr - > data = val;
if (front == NULL) {
front = ptr;
rear = ptr;
front - > next = NULL;
rear - > next = NULL;
}
If the queue contains at least one element, then the condition front == NULL becomes false. So,
make the next pointer of rear point to new node ptr and point the rear pointer to the newly
created node ptr
rear -> next = ptr;
rear = ptr;
Hence, a new node(element) is added to the queue.
C Function
#include < stdio.h >
#include < stdlib.h >
struct node {
int data;
struct node * next;
};
struct node * front;
struct node * rear;
void insert(struct node * ptr, int item) {
ptr = (struct node * ) malloc(sizeof(struct node));
if (ptr == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
ptr - > data = item;
if (front == NULL) {
front = ptr;
rear = ptr;
front - > next = NULL;
rear - > next = NULL;
} else {
rear - > next = ptr;
rear = ptr;
rear - > next = NULL;
}
}
}
int main() {
struct node * head = NULL;
insert(head, 10);
insert(head, 20);
printf("front element: %d", front - > data);
return 0;
}
Output
front element: 10
Deletion
Deletion or delete operation on a linked queue removes the element which was first inserted in
the queue, i.e., always the first element of the queue is removed.
Steps to perform Deletion on a linked queue:
Check if the queue is empty or not.
If the queue is empty, i.e., front==NULL, so we just print 'underflow' on the screen and exit.
If the queue is not empty, delete the element at which the front pointer is pointing. For deleting a
node, copy the node which is pointed by the front pointer into the pointer ptr and make the front
pointer point to the front's next node and free the node pointed by the node ptr. This can be
done using the following statement:
*ptr = front;
front = front -> next;
free(ptr);
C Function
#include < stdio.h >
#include < stdlib.h >
struct node {
int data;
struct node * next;
};
struct node * front;
struct node * rear;
void insert(struct node * ptr, int item) {
ptr = (struct node * ) malloc(sizeof(struct node));
if (ptr == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
ptr - > data = item;
if (front == NULL) {
front = ptr;
rear = ptr;
front - > next = NULL;
rear - > next = NULL;
} else {
rear - > next = ptr;
rear = ptr;
rear - > next = NULL;
}
}
}
void deleteNode(struct node * ptr) {
if (front == NULL) {
printf("Underflow");
return;
} else {
ptr = front;
front = front - > next;
free(ptr);
}
}
int main() {
struct node * head = NULL;
insert(head, 10);
insert(head, 20);
printf("front element: %d\n", front - > data);
deleteNode(head);
printf("front element: %d", front - > data);
return 0;
}
Output
front element: 10
front element: 20
