In previous chapter we have seen how to implement queue using arrays. In this chapter we shall see how to implement queue using linked list [LL].
One major implementation difference here is that, instead of taking taking 2 pointers like “rear” and “front”, using LL we can manage using one “head” pointer, that will always point to the start of the list. And manipulate using that pointer.
We shall see how we insert and delete elements from queue from below steps.
1. Inserting elements into queue.
We know that we insert elements at the rear end of the queue.
Below are the steps to perform inserting elements into queue.
Step 1: Create a temp node.
Step 2: If the list is empty, then make it a head node.
Step 3: If the list is not empty, take a “curr” pointer and navigate till the end of the list.
Step 4: Then point the “next” pointer of “curr” to the “temp” node.
Below images will show the steps:
Creating a temp node
Taking a “curr” pointer and navigating to the end of Queue
Point the “next” of curr to the “temp” node.
2. Deleting elements from the queue
To delete an element from the front end of the queue we perform below steps.
Step 1: Take a temp pointer to the head of the list, so that we don’t loose the head pointer.
Step 2: Move the head pointer to the next element.
Step 3: Delete the node pointed by temp pointer and free the memory to avoid memory leak.
Below images will show you the steps:
Assign a temp pointer to the head pointer.
Move the head pointer to the next node.
Delete the node hold by temp pointer
Implementation of Queue using Linked List in C
#include<stdio.h> #include<stdlib.h> //for memory allocation functions //structure to hold queue elements struct node { int data; struct node *next; }; //global head pointer for easy access struct node *head = NULL; // inserting elements into the queue is called as enqueue void enqueue(int value) { //if the element entered is the first element, then it will be the head element if(head == NULL) { struct node *temp; temp = (struct node*)malloc(sizeof(struct node)); temp->data = value; temp->next = NULL; head = temp; } //else navigate to the rear end of the queue else if(head!=NULL) { //take a temp node to hold the value struct node *temp; temp = (struct node*)malloc(sizeof(struct node)); temp->data = value; temp->next = NULL; //take curr node to navigate till end of the queue struct node *curr; curr = head; while(curr->next != NULL) { curr = curr->next; } curr->next=temp; } } //deleting an element from the queue is called as dequeue void dequeue() { //take a temp pointer pointing to head struct node *temp = head; //move the head pointer head=temp->next; //free temp free(temp); } void display() { struct node *temp = head; if(temp == NULL) { printf("List is Empty\n"); } else { while(temp != NULL) { printf("Displaying Data:\t"); printf("%d \n",temp->data); temp = temp->next; } } } int main() { int choice; while(choice!=4) { printf("\t\tQUEUE Using LinkedList\n"); printf("Choose One\n\n"); printf("1)Enqueue\n"); printf("2)Dequeue\n"); printf("3)Display\n"); printf("4)Logout\n\n"); int option; int value; scanf("%d",&option); switch(option) { case 1: printf("Enter Number:\n"); scanf("%d",&value); enqueue(value); break; case 2: dequeue(); break; case 3: display(); break; case 4: choice=4; break; default: printf("Wrong Input\n\n"); } } return 0; }
Output:
QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 1 Enter Number: 1 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 1 Enter Number: 2 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 1 Enter Number: 3 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 1 Enter Number: 4 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 3 Displaying Data: 1 Displaying Data: 2 Displaying Data: 3 Displaying Data: 4 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 2 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 3 Displaying Data: 2 Displaying Data: 3 Displaying Data: 4 QUEUE Using LinkedList Choose One 1)Enqueue 2)Dequeue 3)Display 4)Logout 4
Further Reading: