Queue using linked list:
To overcome the queue array drawbacks that is
1. Fixed size
2. Garbage values
In queue using linked list the elements are in the form of nodes, a node which contains two
parts, the part is data part which stores a value and second part is address part which stores
the address of another variable
Queue linked list also follows the FIFO mechanism
In queue using linked list adding of an element, we use rear variable and deleting of an
element front variable
Algorithm on Queue using Linked list:
Step -1: create a node in Queue linked list
struct node
{
int data;
struct node*next;
};
struct node *front=NULL;
struct node *rear=NULL;
Step -2: addQ / enQueue:
Adding an element into the queue linked list
Step -1: Create a newNode with given value
Step-2: Check whether list is empty (front==NULL && rear == NULL)
Step -3: If it is Empty then, set newNode->next=NULL and front = newNode, rear =newNode
Step -4: If it is not Empty then, set rear->next=newNode, rear=newNode and newNode-
>next=NULL.
Step – 2: delQ() / deQueue()
Deleting / removing an element from the queue linked list
Step-1: check whether list is Empty (front==NULL && rear == NULL)
Step -2: if it is empty then, display ‘Queue list is empty!!! Deletion is not possible” and
terminate the function
Step -3: if it is not empty then, define a node pointer temp and initialize with front
Step -4: check whether list is having only one node(temp->next ==NULL)
Step -5: if it is true then set front =NULL, rear=NULL and delete temp
Step -6: if it is false then set front= temp->next, temp->next=NULL and delete temp
Step-3: Traversal()
Traversal means visiting each node in sequence.
Step -1: check whether list is empty (front==NULL && rear == NULL)
Step -2: if it is empty then, display ‘Queue list is empty!!!’ and terminate the function
Step -3: if it is not empty then, define a node pointer temp and initialize with front
Step -4: keep displaying temp->data with arrow (--) until temp reaches to the last node
Step -5: finally display temp->data with arrow pointing to NULL (temp->data-NULL)
Program:
// implements queue using linked list
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front =NULL;
struct node *rear =NULL;
void addQ(int ele);
void delQ();
void traverse();
void addQ(int ele)
{
//node memory allocation
struct node *newnode=(struct node*)malloc(sizeof(struct node));
if(front == NULL && rear == NULL)
{
newnode->data =ele;
newnode->next =NULL;
front=newnode;
rear=newnode;
}
else
{
newnode->data=ele;
newnode->next=NULL;
rear->next=newnode;
rear=newnode;
}
printf("insertion successfully...\n");
}
void delQ()
{
struct node *temp;
temp=front;
if(front == NULL && rear == NULL)
{
printf("Queue list is empty!!! Deletion is not possible\n");
}
else if(front->next==NULL) //check whether list is having only one node
{
front = NULL;
rear = NULL;
printf("deletion successfully...\n");
}
else
{
front = temp->next;
temp->next = NULL;
printf("deletion successfully...\n");
}
}
void traverse()
{
struct node * temp;
temp = front;
if(front == NULL && rear == NULL)
{
printf("Queue is empty..\n");
}
else
{
while(temp->next!=NULL)
{
printf("%d-->",temp->data);
temp=temp->next;
}
printf("%d-->NULL\n",temp->data);
}
}
void main() {
int choice,ele;
clrscr();
while(1)
{
printf("************ Queue menu ************\n");
printf("\n 1.addQ \n 2. delQ \n 3. traverse \n 4. exit \n");
printf("Choose one: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter a value to insert");
scanf("%d",&ele);
addQ(ele);
break;
case 2: delQ();
break;
case 3: traverse();
break;
case 4: exit(0);
break;
default: printf("\nInvalid choice (1-4)\n");
}
}
getch();
