How to Implement Queue using Linked List in C

Back to: Data Structures and Algorithms Tutorials

How to Implement Queue using Linked List in C Language:

In this article, I will discuss how to Implement a Queue using a Linked List in C Language with Examples. Please read our previous article discussing how to Implement a Circular Queue in C Language with Examples. We are already familiar with linked lists, so we just need to understand how to implement a queue using them. A queue is a logical data structure that operates on a FIFO (First In, First Out) principle. Let us demonstrate the implementation with an example.

Queue Mechanism Using a Linked List:

The front pointer points to the first node, and the rear pointer points to the last node. The rear pointer is used for insertion, adding elements to the end of the queue. The front pointer is used for deletion, removing elements from the front of the queue.

In a typical linked list, we usually have a single pointer pointing to the first node, called the top. However, for a queue, we also need a rear pointer to help us insert a new node in constant time. The rear pointer always points to the last node. For example, if the first element is 7 and the last element is 9, we need to learn how to perform insertion and deletion (enqueue and dequeue) operations in a queue using a linked list. But first, let’s look at a few important conditions.

Queue Empty Condition in a Linked List:

The first condition is when the queue is initially empty. Where do the front and rear pointers point? In this case, both pointers will be null.

If (front == NULL) // queue is empty

So, the front being equal to null indicates that the queue is empty.

Steps to Create the First Node of a Linked List in a Queue:

The second condition is when we are creating the first node. What do we need to do? Let us create a new node t and insert a value into it.

We have created a node. How do we make this the first node of the linked list? We need to point both the rear and front pointers to this node.

This is a special case that we need to address carefully. When the first node is inserted, both the front and rear should point to this node.

Queue Full Condition in a Linked list:

The third condition is when we have implemented a queue using a linked list. Unless we impose a size limit, the number of elements is not restricted. We can keep adding nodes indefinitely as there is no fixed size. However, when the heap is full, and we are unable to create more nodes, we can consider the queue to be full.

Node* t = new Node;

if (t == NULL) // Queue is full

So, if a node cannot be created, then the queue is full. Actually, the heap is full, so the queue is also full. Now, let us write the Enqueue function and explain the mechanism.

Enqueue Function Using a Linked List:

void Enqueue (int x) {
    Node *t = new Node;
    
    if(t == NULL) {
        printf("Queue is Full");
    }
    else {
        t->data = x;
        t->next = NULL;
        if(front == NULL) front = rear = t;
        else {
            rear->next = t;
            rear = t;
        }
    }
}

This function takes an integer parameter, x. Assume that the front and rear are globally accessible. For insertion, we need to check the queue’s full condition.

Node *t = new Node;

This statement creates a new node in the linked list. After this, we check whether t is null.

if(t == NULL) {
    printf("Queue is Full");
}

If this is the case, we print “Queue is Full”. But if the condition fails, it means the node is created, and it is not null, so the queue is not full. Thus, the else part will be executed. In the else part, we set the data and the next pointer to null. For example,

As this is a special case, we need to check whether it is the first node. If the front is null, then it is the first node. In this case, we will move the front and rear to point to this node.

If this is not the first node:

else {
       rear->next = t;
       rear = t;
}

In this else part, rear’s next is assigned to t, and rear itself is assigned to t. Whenever a new node is inserted, we move the rear pointer to the new node. We ensure that the rear always points to the last node, allowing us to complete the insertion process in just two steps.

How much time does this function take? Insertion is done in constant time with the help of the rear pointer. Otherwise, we would have to traverse the whole linked list and then insert the element, which would take O(n) time. Here, the time taken is O(1), which is constant. Now, let’s see the Dequeue function.

Dequeue Function Using a Linked List:

int Dequeue () {
    int x = -1;
    Node *t;
    
    if(front == NULL) {
        printf("Queue is Empty");
    }
    else {
        t = front;
        front = front->next;
        x = t->data;
        free(p);
    }
    return x;
}

This function deletes the first node and returns the data of the deleted node. To delete an element, we use a variable x initialized to -1. We also use a temporary pointer t of type Node. Before deletion, we need to check whether there are any nodes in the linked list. If the linked list is empty or there are no nodes, we cannot delete it.

If (front == NULL)

This is the queue empty condition. If it is true, we print “Queue is Empty”. If this is not the case, the else part will be executed.

else {
        t = front;
        front = front->next;
        x = t->data;
        free(p);
}

We want to delete the front node. To do this, we set t to point to the front node. Then, we move front to point to the front’s next node. We store the data of t in x and free the memory occupied by t. This deletes the node t. At the end of the function, we return the value of x. If the queue is empty, it returns -1. We are deleting the first node of the linked list, so it takes constant time, O(1). You can also write other functions like Display(), Peek(), etc.

Implementation of Queue using a Linked List in C Language:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node * next;
}* front = NULL, * rear = NULL;

void enqueue(int x) {
    struct Node * t;
    t = (struct Node * ) malloc(sizeof(struct Node));
    
    if (t == NULL)
        printf("Queue is FUll\n");
    else {
        t -> data = x;
        t -> next = NULL;
        if (front == NULL)
            front = rear = t;
        else {
            rear -> next = t;
            rear = t;
        }
        printf("%d element is inserted.\n", x);
    }
}

int dequeue() {
    int x = -1;
    struct Node * t;

    if (front == NULL)
        printf("Queue is Empty\n");
    else {
        x = front -> data;
        t = front;
        front = front -> next;
        free(t);
    }
    return x;
}

void Display() {
    struct Node * p = front;
    
    printf("\nQueue:");
    while (p) {
        printf("%d ", p -> data);
        p = p -> next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    enqueue(50);

    Display();
    printf("Deleted Element: %d", dequeue());
    Display();

    return 0;
}

Output:

In the next article, I will discuss how to Implement a Double-Ended Queue in C Language with Examples. In this article, I explain how to Implement a Queue using a Linked List in C Language with Examples. I hope you enjoy this Queue using Linked List in the C Language article.