× Home

Queue using Linked Lists

Recap for linked list


Since we are implementing this queue using a linked list, the index variables are no longer integers. These become the pointers to the front and the rear nodes. And the queue somewhat starts looking like this.

Enqueue in a queue linked list:

  • Similar to inserting at the end in a linked list.
  • Check if space is left in heap
  • If available, create a new node dynamically and assign value to its data.
  • Point the next member of this new node n to NULL, and point the next member of the r to n. And make r equal to n.
  • Special case: When we insert the first element, both f and r are pointing to NULL. So, instead of just making r equal to n, we make f equal to n as well

Dequeue in a queue linked list:

  • Deleting the head node
  • Check if the queue list is already not empty
  • If not empty create a new ptr and make it equal to the f node. Store the data of f node in some integer variable.
  • Make the f equal to the next member of f, and free the node ptr. Return the value you stored.

isEmpty

  • f node is NULL, which means there is no beginning, hence no element.

isFull

  • Queue implemented using linked lists never usually become full until the space in the heap memory is exhausted.

Understanding code

Create a struct Node with two of its members, one integer variable data to store the data, and another struct Node pointer next to store the address of the next node.

struct Node
{
int data;
struct Node *next;
};

Globally, create two struct Node pointers f and r, which would be used to mark the front and the rear ends. Declaring globally helps us use them in functions.

struct Node *f = NULL;
struct Node *r = NULL;

Creating Enqueue:

void enqueue(int val){
struct Node *n = (struct Node *) malloc(sizeof(struct Node));
if(n==NULL){
printf("Queue is Full");
}
else{
n->data = val;
n->next = NULL;
if(f==NULL){
f=r=n;
}
else{
r->next = n;
r=n;
}
}
}

Exception case:


All the other cases:

Creating Dequeue

int dequeue()
{
int val = -1;
struct Node *ptr = f;
if(f==NULL){
printf("Queue is Empty\n");
}
else{
f = f->next;
val = ptr->data;
free(ptr);
}
return val;
}

#include <stdio.h>
#include <stdlib.h>

struct Node *f = NULL;
struct Node *r = NULL;

struct Node
{
int data;
struct Node *next;
};

void linkedListTraversal(struct Node *ptr)
{
printf("Printing the elements of this linked list\n");
while (ptr != NULL)
{
printf("Element: %d\n", ptr->data);
ptr = ptr->next;
}
}

void enqueue(int val)
{
struct Node *n = (struct Node *) malloc(sizeof(struct Node));
if(n==NULL){
printf("Queue is Full");
}
else{
n->data = val;
n->next = NULL;
if(f==NULL){
f=r=n;
}
else{
r->next = n;
r=n;
}
}
}

int dequeue()
{
int val = -1;
struct Node *ptr = f;
if(f==NULL){
printf("Queue is Empty\n");
}
else{
f = f->next;
val = ptr->data;
free(ptr);
}
return val;
}

int main()
{
linkedListTraversal(f);
printf("Dequeuing element %d\n", dequeue());
enqueue(34);
enqueue(4);
enqueue(7);
enqueue(17);
printf("Dequeuing element %d\n", dequeue());
printf("Dequeuing element %d\n", dequeue());
printf("Dequeuing element %d\n", dequeue());
printf("Dequeuing element %d\n", dequeue());
linkedListTraversal(f);
return 0;
}