Implementation of Queue using Linked List in C

Last Updated on May 31, 2023 by Mayank Dham

Linked lists provide a flexible and dynamic way to represent data structures. Unlike arrays, linked lists can easily grow or shrink as needed, making them ideal for implementing dynamic data structures such as queues. By leveraging the power of linked lists, we can create a queue that efficiently manages elements and supports operations like enqueue (adding an element to the queue) and dequeue (removing an element from the queue).
Throughout this article, we will delve into the intricacies of implementing a queue using a linked list in C. We will discuss the underlying principles, step-by-step implementation details, and the key operations involved in manipulating the queue. Additionally, we will analyze the time and space complexities of these operations to understand the efficiency of our implementation.

What is Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which means that the element which is inserted first in the queue will be the first one to be removed from the queue. A good example of a queue is a queue of customers purchasing a train ticket, where the customer who comes first will be served first.
A linked queue is shown here:

Operation on Linked Queue

Each node of a linked queue consists of two fields: data and next(storing address of next node). The data field of each node contains the assigned value, and the next points to the node containing the next item in the queue.
A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front pointer stores the address of the first element of the queue, and the rear pointer stores the address of the last element of the queue.
Insertion is performed at the rear end, whereas deletion is performed at the front end of the queue. If front and rear both point to NULL, it signifies that the queue is empty.

The two main operations performed on the linked queue are:

Insertion
Deletion

Insertion

Insert operation or insertion on a linked queue adds an element to the end of the queue. The new element which is added becomes the last element of the queue.

Algorithm to perform Insertion on a linked queue:

Create a new node pointer.

 ptr = (struct node *) malloc (sizeof(struct node));

Now, two conditions arise, i.e., either the queue is empty, or the queue contains at least one element.
If the queue is empty, then the new node added will be both front and rear, and the next pointer of front and rear will point to NULL.
```
 *ptr - > data = val;
 if (front == NULL) {
 front = ptr;
 rear = ptr;
 front - > next = NULL;
 rear - > next = NULL;
```
}
If the queue contains at least one element, then the condition front == NULL becomes false. So, make the next pointer of rear point to new node ptr and point the rear pointer to the newly created node ptr
```
rear -> next = ptr;  
 rear = ptr;
```
Hence, a new node(element) is added to the queue.

Code Implementation

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

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

struct node * front;
struct node * rear;

void insert(struct node * ptr, int item) {

    ptr = (struct node * ) malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("\nOVERFLOW\n");
        return;
    } else {
        ptr -> data = item;
        if (front == NULL) {
            front = ptr;
            rear = ptr;
            front -> next = NULL;
            rear -> next = NULL;
        } else {
            rear -> next = ptr;
            rear = ptr;
            rear -> next = NULL;
        }
    }
}

int main() {
    struct node * head = NULL;
    insert(head, 10);
    insert(head, 20);

    printf("front element: %d", front -> data);
    return 0;
}

Output

    Front element: 10

Deletion

Deletion or delete operation on a linked queue removes the element which was first inserted in the queue, i.e., always the first element of the queue is removed.
Steps to perform Deletion on a linked queue:

Check if the queue is empty or not.
If the queue is empty, i.e., front==NULL, so we just print ‘underflow’ on the screen and exit.
If the queue is not empty, delete the element at which the front pointer is pointing. For deleting a node, copy the node which is pointed by the front pointer into the pointer ptr and make the front pointer point to the front’s next node and free the node pointed by the node ptr. This can be done using the following statement:
```
*ptr = front;  
 front = front -> next;  
 free(ptr);  
```

Code Implementation

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

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

struct node * front;
struct node * rear;

void insert(struct node * ptr, int item) {

    ptr = (struct node * ) malloc(sizeof(struct node));
    if (ptr == NULL) {
        printf("\nOVERFLOW\n");
        return;
    } else {
        ptr -> data = item;
        if (front == NULL) {
            front = ptr;
            rear = ptr;
            front -> next = NULL;
            rear -> next = NULL;
        } else {
            rear -> next = ptr;
            rear = ptr;
            rear -> next = NULL;
        }
    }
}

void deleteNode(struct node * ptr) {
    if (front == NULL) {
        printf("Underflow");
        return;
    } else {
        ptr = front;
        front = front -> next;
        free(ptr);
    }
}

int main() {
    struct node * head = NULL;
    insert(head, 10);
    insert(head, 20);

    printf("front element: %d\n", front -> data);
    deleteNode(head);
    printf("front element: %d", front -> data);
    return 0;
}

Output

    front element: 10
    front element: 20

Implementation of queue using linked list in C

When a queue is implemented using a linked list, it can be expanded in response to demand, allowing for dynamic memory allocation.
A queue that is implemented using a linked list will continue to operate in accordance with the FIFO principle.
Steps for implementing queue using linked list in C:

Enqueue Function

The enqueue function adds a new element to the queue’s end. O(1) time is required. The last pointer can be used to follow the last item.

First, build a new node with given data.
Check if the queue is empty or not.
If a queue is empty then, a new node is assigned to the front and rear.
Else make next of rear as new node and rear as a new node.

Dequeue Function

The first element of the queue is always removed by the dequeue function. O(1) time is required. There must be at least one element in the queue for dequeue; else, underflow situations would arise.

Check if the queue is empty or not.
If the queue is empty, then dequeue is not possible.
Else store front in temp
And make the next of front as the front.
Delete temp, i.e, free(temp).

Print

The queue’s content is shown using the print function. The print function’s time complexity is O(n), where n is the number of nodes in the queue, because we must iterate through each element of the queue in order to print it.

Check if queue contains at least one element or not.
If the queue is empty print “No elements in the queue.”
Else, define a node pointer and initialize it with the front.
Display data of node pointer until the next node pointer becomes NULL.

Code Implementation for queue using linked list in C

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

// Structure to create a node with data and the next pointer
struct node {
    int data;
    struct node * next;
};

struct node * front = NULL;
struct node * rear = NULL;

// Enqueue() operation on a queue
void enqueue(int value) {
    struct node * ptr;
    ptr = (struct node * ) malloc(sizeof(struct node));
    ptr -> data = value;
    ptr -> next = NULL;
    if ((front == NULL) && (rear == NULL)) {
        front = rear = ptr;
    } else {
        rear -> next = ptr;
        rear = ptr;
    }
    printf("Node is Inserted\n\n");
}

// Dequeue() operation on a queue
int dequeue() {
    if (front == NULL) {
        printf("\nUnderflow\n");
        return -1;
    } else {
        struct node * temp = front;
        int temp_data = front -> data;
        front = front -> next;
        free(temp);
        return temp_data;
    }
}

// Display all elements of the queue
void display() {
    struct node * temp;
    if ((front == NULL) && (rear == NULL)) {
        printf("\nQueue is Empty\n");
    } else {
        printf("The queue is \n");
        temp = front;
        while (temp) {
            printf("%d--->", temp -> data);
            temp = temp -> next;
        }
        printf("NULL\n\n");
    }
}

int main() {
    int choice, value;
    printf("\nImplementation of Queue using Linked List\n");
    while (choice != 4) {
        printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n");
        printf("\nEnter your choice : ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("\nEnter the value to insert: ");
                scanf("%d", &value);
                enqueue(value);
                break;
            case 2:
                printf("Popped element is :%d\n", dequeue());
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
                break;
            default:
                printf("\nWrong Choice\n");
        }
    }
    return 0;
}

Input

Output:

Enqueue Operation:
Implementation of Queue using Linked List in C
1. Enqueue
2. Dequeue
3. Display
4. Exit

Enter your choice: 1

Enter the value to insert: 12
Node is Inserted

1.Enqueue
2.Dequeue
3.Display
4.Exit

Enter your choice: 1

Enter the value to insert: 45
Node is Inserted

1.Enqueue
2.Dequeue
3.Display
4.Exit

Enter your choice: 1

Enter the value to insert: 56
Node is Inserted

1.Enqueue
2.Dequeue
3.Display
4.Exit

Enter your choice : 3
The queue is
12--->45--->56--->NULL

1.Enqueue
2.Dequeue
3.Display
4.Exit

Enter your choice: 2
Popped element is:12
1. Enqueue
2. Dequeue
3. Display
4. Exit

Enter your choice: 2
Popped element is:45
1. Enqueue
2. Dequeue
3. Display
4. Exit

Enter your choice : 3
The queue is
56--->NULL

1.Enqueue
2.Dequeue
3.Display
4.Exit

Enter your choice: 2
Popped element is:56
1. Enqueue
2. Dequeue
3. Display
4. Exit

Conclusion
Throughout this article, we have explored the step-by-step process of implementing a queue using a linked list in C. We discussed the fundamental principles behind linked lists and their advantages over static data structures like arrays. By employing pointers and dynamic memory allocation, we were able to construct a linked list-based queue that can handle a variable number of elements.

We examined essential operations such as enqueue and dequeue, which allow us to add elements to the end of the queue and remove elements from the front, respectively. Through careful implementation and manipulation of pointers, we ensured that these operations execute in constant time, making our queue efficient and suitable for real-time applications.

FAQ’s

Q1: Why would I choose to implement a queue using a linked list instead of an array?
Linked lists offer several advantages over arrays when implementing a queue. Unlike arrays, linked lists can dynamically grow or shrink, allowing for efficient memory utilization. This flexibility is particularly useful when the number of elements in the queue is unknown or may change frequently. Additionally, linked lists make it easier to insert or remove elements at the beginning or end of the queue without the need for shifting elements, as required in an array.

Q2: What are the key operations in a queue implemented using a linked list?
The main operations in a queue implemented using a linked list are:

Enqueue: Adds an element to the end of the queue.
Dequeue: Removes the element from the front of the queue.
IsEmpty: Checks if the queue is empty.
Peek: Retrieves the element at the front of the queue without removing it.

Q3: How is memory managed in a linked list-based queue implementation?
Memory management in a linked list-based queue is typically handled dynamically using pointers and dynamic memory allocation. Each node in the linked list represents an element in the queue and contains a data value and a pointer to the next node. Memory is allocated dynamically using functions like malloc() to create new nodes, and free() is used to release memory when nodes are removed.

Q4: What is the time complexity of enqueue and dequeue operations in a linked list-based queue?
In a properly implemented linked list-based queue, both enqueue and dequeue operations have a time complexity of O(1), which means they execute in constant time regardless of the number of elements in the queue. This efficiency is achieved by maintaining a reference to both the front and rear of the queue, allowing for efficient insertion and removal operations.

Implementation of Queue using Linked List in C

What is Queue?

Operation on Linked Queue

Insertion

Code Implementation

Deletion

Code Implementation

Implementation of queue using linked list in C

Enqueue Function

Dequeue Function

Print

Code Implementation for queue using linked list in C

FAQ’s

Leave a Reply Cancel reply

Integrated Services Digital Network (ISDN)

VLAN ACL (VACL) in Computer Networks

Inter-VLAN Routing Using a Layer 3 Switch

Access and Trunk Ports in Computer Networks

Role-Based Access Control (RBAC) in Computer Networks

Display Processor in Computer Graphics

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

What is Queue?

Operation on Linked Queue

Insertion

Code Implementation

Deletion

Code Implementation

Implementation of queue using linked list in C

Enqueue Function

Dequeue Function

Print

Code Implementation for queue using linked list in C

FAQ’s

Leave a Reply Cancel reply