Implementation of Queue Using Linked List in C with Code Example

While developing efficient data structures in C, one challenge developers often face is choosing the right implementation strategy. The Implementation of Queue Using Linked List offers a flexible and dynamic approach, especially useful when dealing with unknown or varying input sizes. This method allows seamless memory management without worrying about overflow as long as the system has memory available.

In many real-world scenarios, queues operate under unpredictable demands. A linked list-based queue ensures that enqueue and dequeue operations remain efficient even as the queue grows or shrinks. This article will walk you through each step of the Implementation of Queue Using Linked List, from understanding the basics to writing a complete program, covering algorithms, examples, outputs, and explanations. Also visit our Software Engineering Courses to get hands-on experience!

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In First Out) principle. It means the element inserted first will be removed first. Queues are useful in task scheduling, handling requests, and many other applications. They allow elements to be added at the rear and removed from the front, ensuring orderly processing. This structure is widely used in operating systems, printers, and customer service systems.

If you’re ready to grow your AI and Data Science skills, check out these programs.

• Master’s in Data Science - LJMU
• PG Diploma in Machine Learning & AI – IIT Bangalore
• Master of Science in AI & Data Science – Jindal Global University

What is a Linked List?

A linked list is a dynamic data structure consisting of nodes. Each node contains data and a pointer to the next node. Linked lists allow flexible memory allocation and easy insertion or deletion without shifting elements. You can explore linked list implementation in C for a deeper understanding.

Advantages of Using Linked List for Queue Implementation

Using a linked list for implementing a queue removes the fixed size limitation of arrays. It enables dynamic memory allocation, avoiding overflow unless the system runs out of memory. Also, insertions and deletions at the front or rear become efficient since no shifting of elements is required.

How to Represent a Queue Using Linked List in C?

A queue using a linked list in C uses nodes connected by pointers. Each node holds a data value and a pointer to the next node. The queue maintains two pointers: front (points to the first node) and rear (points to the last node). New nodes are added at the rear and removed from the front. 

Check out this detailed tutorial on queue implementation.

Structure Definition for Queue Using Linked List

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

Each node stores an integer data and a pointer to the next node. You can modify the data type to store other data as required.

Initialization of Front and Rear Pointers

Initially, both front and rear pointers are set to NULL, indicating an empty queue:

struct Node* front = NULL;

struct Node* rear = NULL;

These pointers help in performing enqueue and dequeue operations efficiently.

How to Implement Enqueue Operation in Queue Using Linked List?

The enqueue operation inserts an element at the rear of the queue. A new node is dynamically allocated and linked to the existing rear.

Algorithm for Enqueue Operation

1. Create a new node with given data.
2. If the queue is empty, set both front and rear to the new node.
3. Else, link the new node at the rear and update the rear pointer.

C Code Example for Enqueue Operation

void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (rear == NULL) {
        front = rear = newNode;
        return;
    }
    rear->next = newNode;
    rear = newNode;
}

Output:

enqueue(10);

enqueue(20);

enqueue(30);

Explanation: After enqueueing 10, 20, and 30, the queue contains 10 at front and 30 at rear. The nodes are linked in the order: 10 -> 20 -> 30.

Refer to this tutorial on stack implementation using linked lists.

How to Implement Dequeue Operation in Queue Using Linked List?

The dequeue operation removes an element from the front of the queue. It frees the memory of the removed node and updates the front pointer. 

Algorithm for Dequeue Operation

1. Check if the queue is empty.
2. Store the current front node in a temporary pointer.
3. Move the front pointer to the next node.
4. Free the removed node.
5. If front becomes NULL, set rear to NULL.

C Code Example for Dequeue Operation

void dequeue() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", temp->data);
    front = front->next;

    if (front == NULL) rear = NULL;

    free(temp);
}

Output:

dequeue(); // Dequeued: 10

dequeue(); // Dequeued: 20

Explanation: First call removes 10, second removes 20. After dequeuing twice, the front points to 30, and rear remains at 30.

How to Implement Peek and isEmpty Operations in Queue Using Linked List?

Peek returns the front element without removing it. isEmpty checks if the queue is empty.

Algorithm for Peek Operation

1. If front is NULL, queue is empty.
2. Else, return front->data.

Algorithm for isEmpty Operation

1. Return true if front is NULL.
2. Else, return false.

C Code Examples for Peek and isEmpty Operations

int peek() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    return front->data;
}

int isEmpty() {
    return front == NULL;
}

Output:

printf("Front element: %d\n", peek()); // Front element: 30

printf("Is queue empty? %s\n", isEmpty() ? "Yes" : "No"); // Is queue empty? No

Explanation: Peek returns 30, which is at the front. isEmpty returns No since queue still has elements.

Complete C Program for Queue Implementation Using Linked List

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

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

struct Node* front = NULL;
struct Node* rear = NULL;

void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (rear == NULL) {
        front = rear = newNode;
        return;
    }
    rear->next = newNode;
    rear = newNode;
}

void dequeue() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", temp->data);
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
}

int peek() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    return front->data;
}

int isEmpty() {
    return front == NULL;
}

int main() {
    enqueue(50); // Ram arrives
    enqueue(60); // Shyam arrives
    enqueue(70); // Aniket arrives
    printf("Front: %d\n", peek());
    dequeue();
    dequeue();
    printf("Front: %d\n", peek());
    dequeue();
    dequeue();
    return 0;
}

Output

Front: 50

Dequeued: 50

Dequeued: 60

Front: 70

Dequeued: 70

Queue is empty

Explanation: Ram (50), Shyam (60), Aniket (70) enter the queue. First peek returns 50 (front). After dequeuing Ram and Shyam, peek shows 70. Final dequeue removes Aniket. Further dequeue reports queue is empty.

Check out this guide on dynamic memory in C.

What are the Advantages of Implementing Queue Using Linked List in C?

• No need to define maximum size.
• Efficient memory use; nodes allocated as needed.
• Enqueue and dequeue operations take O(1) time.

What are the Limitations of Queue Implementation Using Linked List in C?

• Requires extra memory for pointer storage.
• Slower access to middle elements (sequential traversal only).
• Memory allocation and deallocation overhead.

Real-World Applications of Queue Implemented Using Linked List in C

• Print job scheduling in printers.
• Task scheduling in operating systems.
• Customer service request handling.
• Simulation of real-world queues (e.g., railway ticket counters).

Time and Space Complexity Analysis of Queue Operations Using Linked List

• Enqueue: The time complexity of the enqueue operation is O(1) because inserting a new element at the rear takes constant time, regardless of the number of elements already present. The space complexity per insertion is also O(1) since each insertion only needs memory for a new node.
• Dequeue: The time complexity of the dequeue operation is O(1) because removing an element from the front pointer takes constant time. The space complexity per deletion is O(1) as no extra memory is used during removal.
• Peek: The peek operation checks the value at the front without removing it, so its time complexity is O(1) since it’s a direct pointer access.
• Overall space complexity: The total space complexity of the queue grows linearly with the number of elements, represented as O(n), where n is the number of nodes stored in the linked list. Each node requires additional space to store both the data and the pointer to the next node.

Learn more about the stack in C and its operations in this detailed guide on stack implementation.

Conclusion

The Implementation of Queue Using Linked List in C provides a dynamic and flexible approach to handle data in a first-in-first-out manner. It eliminates the limitations of fixed-size queues and enables efficient memory management for varying workloads. By mastering this implementation, developers can handle queue-based problems with confidence and adaptability.

FAQ’s 

1. What is the main advantage of implementing a queue using a linked list?

The main advantage of implementing a queue using a linked list is dynamic memory allocation. It allows flexible growth and shrinkage of the queue without worrying about a fixed size or memory wastage like in arrays.

2. Why is time complexity O(1) for enqueue and dequeue operations in a linked list queue?

Both enqueue and dequeue operations update the front or rear pointers directly. Since no traversal or shifting is required, each operation takes constant time, resulting in an O(1) time complexity for insertion and deletion.

3. How does memory allocation work in a queue implemented using a linked list?

In a linked list queue, memory is allocated dynamically for each new node. Every time an element is added, a new node is created in memory. This continues until memory is full or the program ends.

4. Can a queue using a linked list overflow?

A queue implemented using a linked list does not experience overflow in the traditional sense. It can keep growing as long as memory is available. Overflow occurs only when system memory is exhausted.

5. What happens if we dequeue from an empty queue in a linked list implementation?

If we attempt to dequeue from an empty queue, an underflow condition occurs. Usually, a message or error is displayed indicating the queue is empty, and no element is removed or returned.

6. How is peek operation performed in a queue using a linked list?

The peek operation retrieves the value at the front node without deleting it. It simply accesses the data stored at the front pointer, allowing the user to see the next element to be dequeued.

7. How does the queue handle multiple data types using a linked list?

To handle multiple data types, the linked list node’s data field can be defined using a union or void pointer. This allows storing different types of data, making the queue more flexible in applications.

8. Is memory freed automatically after dequeuing an element from the linked list queue?

No, memory must be freed manually in languages like C. After deleting a node during dequeue, the program should explicitly call free() to release memory and avoid memory leaks in the system.

9. What are common use cases of queue implemented using a linked list?

Common use cases include CPU task scheduling, print job management, handling server requests, and buffering data streams. The linked list-based queue ensures dynamic memory handling for variable-sized workloads efficiently.

10. How do we initialize front and rear pointers in a queue using linked list?

Initially, both front and rear pointers are set to NULL, indicating the queue is empty. When the first element is enqueued, both pointers point to the same newly created node in the linked list.

11. How does space complexity compare between array-based and linked list-based queues?

A linked list-based queue uses extra memory per node for storing pointers. While it avoids unused slots like arrays, the pointer overhead makes space complexity slightly higher per element compared to array-based implementations.

12. Why is a linked list preferred over an array for implementing queues?

A linked list is preferred because it eliminates the need to predefine a fixed size. It allows the queue to grow and shrink dynamically, avoiding the need to shift elements or deal with wasted memory.

13. How does a circular queue differ from a queue using a linked list?

A circular queue uses an array with wrapping indices to reuse space, while a linked list queue grows dynamically without wrapping. Both follow FIFO, but memory handling and overflow behavior differ significantly.

14. Can we implement a double-ended queue (deque) using a linked list?

Yes, a deque can be implemented using a doubly linked list. It allows insertion and deletion from both front and rear ends, providing greater flexibility compared to a simple queue implementation.

15. What happens to the rear pointer after dequeuing the last element in a linked list queue?

After dequeuing the last element, both front and rear pointers are reset to NULL. This marks the queue as empty and prevents dangling pointers from accessing deleted or invalid memory locations.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz