Implementation of Queue Using Linked List

Implementing a queue using a linked list in C involves utilizing the properties and functionality of linked lists to create a data structure that follows the First-In-First-Out (FIFO) principle. In this comprehensive guide, we have compiled the meaning of queue, linked list, and implementation of queue using linked list in C with examples. So without further ado, dig out this post.

What is Queue?

In data structures, a queue is a significant entity that adheres to an age-old principle known as "First-In-First-Out" or FIFO. Just like people patiently forming a line, a queue orchestrates a collection of elements in a specific order, granting the earliest arrival the privilege of leaving first.

Imagine a set-up where you're waiting in a queue to board a rollercoaster. As each person joins the queue, they occupy a position at the end, extending the line further. Similarly, a queue embraces this concept flawlessly in the digital realm of data structures.

A queue offers two fundamental actions:

1. Enqueue: Picture a new adventurer eagerly joining the line for the rollercoaster. Enqueueing embodies the process of adding an element to the rear of the queue, often referred to as "push" or "insert." The fresh addition graciously assumes its position as the last element in the queue, ready for its turn to come.

2. Dequeue: Eventually, the exhilarating moment arrives when the first person in line steps forward to experience the thrilling rollercoaster ride. Likewise, the dequeue operation corresponds to removing the element at the front of the queue. This act, also known as "pop" or "remove," gracefully eliminates the frontmost element. After its departure, the element succeeding the dequeued one gracefully ascends to occupy the prestigious leading spot.

Queues are invaluable, from scheduling tasks in operating systems and managing network traffic to modeling real-world scenarios like processing print jobs or handling requests in web servers.

What is a Linked List?

Simply put- A linked list is a collection of nodes, each containing a reference to the subsequent node, forming a captivating sequence. A linked list with each node comprising two essential components:

1. Data: At the core of every node lies a precious piece of information, be it an integer, a character, an object, or any other data type that fits the application's needs.

2. Pointer: Serving as a crucial link in the chain, a pointer within each node graciously points to the next node in the sequence. Through this delicate connection, the elements of a linked list forge an orderly procession, unveiling their inherent connectivity.

A linked list embraces a dynamic and flexible nature, offering a captivating way to organize and connect elements. Here are two common variants:

1. Singly Linked List: In this variant, each node contains a data element and a pointer that directs to the subsequent node in the sequence. The last node, also known as the tail, gracefully points to null, signifying the end of the linked list.

2. Doubly Linked List: Elevating the connectivity to new heights, a doubly linked list augments the nodes with an additional pointer. In addition to the forward connection, each node possesses a backward pointer, linking it to the preceding node. This bidirectional path enhances traversal flexibility but incurs a slightly higher memory overhead.

The functionality of linked lists lies in their ability to grow and shrink dynamically. New nodes can be effortlessly inserted or removed, gracefully accommodating the ever-changing demands of the application.

Operation on Linked Queue

You can carry out the following operations in a connected queue:

Enqueue: By performing this action, an element is added to the back of the queue. It entails building a new node, establishing its element, and updating the rear node and rear pointer's references. Here is an illustration of a Python implementation:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

Dequeue: In this operation, the element at the front of the queue is taken out and returned. It entails deleting the front node by changing the front node and the front pointer to point to the subsequent node in the queue. Here is an illustration of a Python implementation:

class Queue:
    # ... (previous code)
    def dequeue(self):
        if self.front is None:
            return None
        dequeued_data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued_data

IsEmpty: This operation checks to see if the front pointer is null to see if the queue is empty. If it is null, the queue is thought to be empty and without any elements. Here is an illustration of a Python implementation:

class Queue:
    # ... (previous code)
    def is_empty(self):
        return self.front is None

The fundamental operations you can carry out on a connected queue are as follows. In addition, you can use additional operations like traversing the linked list to calculate the size of the queue or peeking (accessing the front element without removing it).

Algorithm to perform Insertion on a linked queue:

You may use the following algorithm to perform an insertion (enqueue) operation on a linked queue:

1. With the provided data, create a new node.

2. The queue will be empty if both the front and back pointers are null.

• Set the new node's front and rear points there.

3. If not (the queue is not empty), then:

• Set the new node as the next pointer for the existing back node.
• Incorporate the new node into the rear pointer.

4. The queue's back node is now the new node.

Here's an example implementation of the enqueue operation in Python, assuming you have a Node class and a Queue class with front and rear attributes:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

This approach makes it efficient to add elements to the linked queue's back end. Since updating just the rear pointer is required, the enqueue operation in a linked queue has an O(1) time complexity.

Implementation of queue using linked list in C

Here's an implementation of a queue using a linked list in C, along with an explanation of each step:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
struct Queue {
    struct Node* front;
    struct Node* rear;
};
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}
int isEmpty(struct Queue* queue) {
    return queue->front == NULL;
}
void enqueue(struct Queue* queue, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (isEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }
    struct Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}
int main() {
    struct Queue* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    printf("%d dequeued from the queue\n", dequeue(queue));
    printf("%d dequeued from the queue\n", dequeue(queue));
    printf("%d dequeued from the queue\n", dequeue(queue));
    return 0;
}

Explanation of each step:

• The struct Node represents a node in the linked list. It contains integer data to store the element and a next pointer to point to the next node.
• The struct Queue represents the queue and contains front and rear pointers to indicate the front and rear nodes of the queue, respectively.
• The createQueue function creates an empty queue by allocating memory for the Queue structure and initializing the front and rear pointers to NULL.
• The isEmpty function checks if the queue is empty by comparing the front pointer to NULL. If the front pointer is NULL, the queue is empty, and the function returns 1 (true). Otherwise, it returns 0 (false).
• A new element is added to the back of the queue by the enqueue function. Memory is allocated for a new node whose data field is set to the supplied data and whose next pointer is set to NULL. Both the front and rear pointers are adjusted to point to the new node if the queue is empty. If not, the rear pointer is updated to the new node, and the next pointer of the existing rear node is updated to point to the new node.
• The element at the front of the queue is taken out and returned by the dequeue function. A sentinel value (in this case, -1) and an error message are printed if the queue is empty. If not, changing the front pointer to the following node removes the front node. The rear pointer is also set to NULL if the front becomes NULL, indicating that the queue is now empty. The deleted node is released, and its information is given back.
• CreateQueue is used to build a queue in the main function.
• The enqueue function is used to enqueue elements.
• Using the dequeue function, elements are unqueued, and their values are printed.

With this solution, you can quickly conduct enqueue and dequeue operations and establish a queue using a linked list.

Code for implementing queue using linked list in C

Here's the code for implementing a queue using a linked list in C:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
struct Queue {
    struct Node* front;
    struct Node* rear;
};
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}
int isEmpty(struct Queue* queue) {
    return queue->front == NULL;
}
void enqueue(struct Queue* queue, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Error: Queue is empty\n");
        return -1;
    }
    struct Node* temp = queue->front;
    int data = temp->data;
    if (queue->front == queue->rear) {
        queue->front = NULL;
        queue->rear = NULL;
    } else {
        queue->front = queue->front->next;
    }
    free(temp);
    return data;
}
void displayQueue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return;
    }
    struct Node* current = queue->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
int main() {
    struct Queue* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    displayQueue(queue);
    printf("%d dequeued from the queue\n", dequeue(queue));
    printf("%d dequeued from the queue\n", dequeue(queue));
    displayQueue(queue);
    return 0;
}

• A structure Node and a structure Queue are defined in this code to represent a node in a linked list and a queue, respectively.
• By allocating memory for the Queue structure and setting the front and rear pointers to NULL, the createQueue function creates an empty queue.
• The front pointer is compared to NULL in the isEmpty method to determine whether the queue is empty.
• The enqueue function adds A new element to the back of the queue. A new node's memory is allocated, its data field is set to the supplied information, and the front and rear pointers are updated appropriately.
• The element at the front of the queue is taken out and returned by the dequeue function. The memory of the removed node is released while the front pointer is updated.
• The queue's components are printed using the displayQueue function.
• In the main function, a queue is established with createQueue, elements are added to it with enqueue, the queue is shown with displayQueue, elements are removed with dequeue, and the queue is updated and shown again.

Conclusion

The implementation of queue using linked lists in C++ and C offers a productive and adaptable data structure that complies with the First-In-First-Out (FIFO) concept. A queue is a key component of data structures that arranges elements in a certain order, prioritizing the earliest arrival. On the other hand, linked lists are dynamic structures that are made up of nodes connected by pointers and allow for dynamic growth and contraction.

FAQs

1. What is the benefit of creating a queue using a linked list?

Constructing a queue using a linked list is advantageous because it offers dynamic memory allocation, enabling the queue to expand or contract as necessary. In situations where the size of the queue is unknown in advance or could alter over time, this flexibility is especially helpful.

2. Can a queue implemented using a linked list handle a large number of elements efficiently?

Yes, a queue that uses a linked list can effectively manage a lot of entries. The enqueue and dequeue operations have an O(1) time complexity, which means they execute in a fixed amount of time regardless of the queue's element count. Because of this, linked list-based queues are appropriate for applications that need quick addition and deletion of entries.

3. Are there any limitations or trade-offs associated with implementing a queue using a linked list?

A linked list implementation of a queue has the drawback of requiring more memory than an array-based solution. Due to the requirement for keeping pointers, each node in the linked list has memory overhead. Additionally, array-based queues may be more cache-friendly than linked list-based queues, which can impact performance in some circumstances.

4. Can a linked list-based queue handle both numeric and non-numeric data types?

Yes, a queue based on linked lists can handle both number and non-numeric data types. The queue can store elements of various types since any data type can be declared for the data field of each node in the linked list. Due to their adaptability, linked list-based queues can be used in a variety of applications that deal with various data types.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz