Queue using linked list

A queue has two ends front and the rear end. In a queue elements are added from the rear end and they are deleted from the front end of the queue. Implementing queue using a linked list requires it to follow the same principle ie; deletion from front and insertion from the rear end.

Initially in the program Front and Rear are both initialized to NULL.
If the value of front is equal to NULL then it means queue is empty.
if(front == NULL)
{
/**empty queue**/
}
You may see in the above image the front pointer variable stores the address (1002) of the first node  and the rear pointer variable stores the address of the last node in the list.
If there exists only one node then that node is the first as well as the last node in the list.

Since we know the address of the first node which is stored in variable front we can delete nodes at the beginning of the list which would mean deletion from the front end of the queue.
Similarly we know the address of the last node which is held by pointer variable rear so we can add nodes at the end of the linked list which would mean insertion at the rear end of the queue.

 void insert(int num)
{
     struct node *temp;
     temp=(struct node *)malloc(sizeof(struct node));
     temp->info=num;
     temp->link=NULL;
     if(front==NULL)
      {
       front=temp;
      }
     else
      {
      rear->link=temp;
      }
       rear=temp;
   }

Above is the function for insertion.
Every time this function gets executed temp will hold the address of the newly created node.
temp->link=NULL;  set the link part of the newly created node to NULL because nodes will be added at the end of the linked list rear end means the end of the list and the link part of the last node is always null.

  
   if(front==NULL)
{
front=temp;
}

if the value of front is null and the insert function is called then front should be assigned the address of temp which is the newly created node because front should store the address of the first node in the list. Front == null means empty list and if we insert a node into an empty list then that node is the first as well as last node in the list.
     else
{
rear->link=temp;
}

If the above if statement is not true then it means we are inserting node into a list which already contains at least one node in that case the value of front doesn’t change, so the else condition will become true. rear->link=temp; the link part of the last node should be assigned the address of the newly created node ie; temp thus making the newly inserted node the last node in the list added from the rear end.
rear=temp; update the value of rear, assign rear the address of the new node which is the last node in the list. View one of the image above rear should store the address of  the last node in the list.

Deletion from the front end of the queue

int del()

     {

          int num;

          struct node *temp;

          if(front==NULL)

          {

                         printf("underflown");

                         return;

          }

          temp=front;
          num=temp->info;
          front=front->link;
          free(temp);
          return num;       

     }

The del() function is very simple everytime this function is called and if the list is not empty then the first node is going to get deleted.
temp=front; assign temp the value of front which is the address of the node which would get deleted.
front=front->link; front->link means the link part of the first node which has the address of the second node or null if there is only one node in the list. The second node becomes the first node when a node from the front or beginning of the list is deleted and front should store the address of the new first node.
free(temp); temp stores the address of the node which is to be deleted and free function frees the memory and deletes that node completely from the memory.
return num; del function is of type int and an integer value should be returned.

void display()
      {
                     struct node *p;
                     if(front==NULL)
                     {
                      printf("underflown");
                      return;
                      }
                     p=front;
                     printf("nQueue:n");
                     while(p!=NULL)
                     {
                      printf("%d ",p->info);
                      p=p->link;
                     }
                                         
                                  
        }
Previous Post
C program implementing Stack using a Linked List
Next Post
Queue using linked list c program

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Menu