The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

A queue is an example of a linear data structure, or more abstractly a sequential collection. It can only be modified by the insertion of data-entities at one end of the sequence and the removal of data-entities from the other end of the sequence. Because of this limitation, implementation of the queue is comparatively trickier than other data structures. So, in this tutorial, we are going to focus on the linked list implementation of queue data structure.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

What Is the Need for Queue Implementation Using Linked List?

The implementation of the queue using static data structure (1-D Array) comes up with some bizarre limitations in terms of memory wastage. And while designing solutions or algorithms, we should always protect these crucial resources by analyzing all developmental implications. The technique of queue implementation using an array arises with the following drawbacks developing the need for another queue implementation methodology: 

• Problem of Fixed Size: Array is a static data structure. This means we have to predetermine the size of an array before the execution of a program. Additionally, that size cannot be updated at run-time. This fact about arrays violates the primary feature of a queue that it can be extended at run-time.

• Memory Wastage while Resolving Fixed Size Problem: When the array gets exhausted, we cannot update its size at the run time. This scenario leaves us with only one option: to create a new extensive array and copy the contents of the previously exhausted array into it. But, this approach also brings more disadvantages to the table:

1.  Copy operation costs O(N)
2.  Loss of more memory due to the creation of a larger array

For example, consider the scenario shown in figure below. The first array in the figure is an exhausted or fully utilized array having size 4. And another one is a new larger array having size 10. When the contents of an exhausted array get stored in a new larger array, the plenty of space of the new larger array remains empty.

• Memory Wastage Due to Deletion of Data-Elements: After performing Dequeue() operations queue will have some empty spaces. And the value of the rear might be so high that those empty spaces can never be re-utilized.

For example, consider the array shown in the figure above. The size of the queue is 10. The front pointer has also reached location 5, and the rear pointer is at location 9, wasting newly created empty spaces.

Due to these drawbacks, the usage of arrays is not an ideal approach for queue implementation. 

But, in the case of queue implementation using linked list, all the drawbacks mentioned above get resolved as the linked list is a dynamic data structure whose size can be changed at run-time. Additionally, the time required to implement queue operations using a linked list is O(1). 

Now that you have understood the need for queue implementation using a linked list, let’s apprehend how we can represent a queue using a linked list.

Queue Representation Using Linked List 

In a linked queue, each node of the queue consists of two fields, i.e., data field and reference field. Each entity of the linked queue points to its immediate next entity in the memory. Furthermore, to keep track of the front and rear node, two pointers are preserved in the memory. The first pointer stores the location where the queue starts, and another pointer keeps track of the last data element of a queue.

The diagram above consists of a linked list representation of queue comprising 3 data fields and addresses of the subsequent entities in a queue.

The insertion in a linked queue is performed at the rear end by updating the address value of the previous node where a rear pointer is pointing. For example, consider the linked queue of size 3. We need to insert a new node located at address 350 and consisting 7 in its data field. For that to happen, we will just update the value of the rear pointer and address field of the previous node. 

The value of the rear pointer will become 350 now, whereas the front pointer remains the same. After deleting an element from the linked queue, the value of the front pointer will change from 100 to 200. The linked queue will look like below: 

Now that you have understood how a queue can be represented using a linked list, let’s implement primary queue operations.

Become an Automation Test Engineer in 11 Months!

Automation Testing Masters ProgramExplore Program

Implementation of Queue Operations

Enqueue() and Dequeue() are the primary operations of the queue, which allow us to manipulate the data flow. These functions do not depend on the number of elements inside the queue or its size; that is why these operations take constant execution time, i.e., O(1) [time-complexity]. Here we will implement these primary operations:

1. Enqueue() Operation

The process of inserting elements into the queue is known as Enqueue operation. This operation is performed at the rear node of the queue. In this function, firstly, we will allocate the memory for a new node using the following statement.

After creating a new node, we will also insert values into both data and reference fields. Data will be an argument provided by the user, and the reference field will be set to null initially.

There can be two conditions of making insertion of a new node into the linked queue.

In the first condition, we will insert a new node into an empty queue. In this case, both the front and rear pointer must be Null. We will check that using the condition front = NULL. If it becomes true, the new element will be added as the first element of the queue, and both the front and rear pointer will also be updated to point to this new node. 

In the second case, the queue already contains more than one data element. Now, the condition front = NULL becomes false. In this scenario, we will just update the rear pointer to point to the new node. And will also change the address field of the previous node to establish a new link.

Function in C:

2. Dequeue() Operation

The Dequeue operation is a process of removing elements from the queue. An element can only be deleted when there is at least an element to delete, i.e., Rear > 0 (Queue shouldn’t be empty). If the queue is empty, then we simply write an underflow error and make an exit.

Further, if there is only one element in the queue, we will set both the front and rear pointer to NULL.

Otherwise, we will update the value of the front pointer to point to the next node. And will also deallocate the memory of deleted node with the help of the free() function in C.

Function in C:

We will also look into the implementation of supportive queue operations named Peek() and Print(). The Print() function is an additional function which we are implementing to visualize the state of our queue.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

3. Peek() Operation

This function helps in extracting the data element where front is pointing without removing it from the queue. In this function, firstly, we will check if front = NULL. If it becomes true, we will return Queue is Empty to the console.

Otherwise, we will return the data element present at the front node.

Function in C:

4. Print() Function

This function is responsible for printing all the data elements in our program for queue implementation using linked list. In this function, we will initialize the temp pointer pointing to the front node. And with the help of the while condition, we will traverse through the linked queue.

Function in C: 

Program in C for Queue Implementation Using Linked List

Let’s have a look at the results of our C program for queue implementation using linked list. In this program, we are performing enqueue operations by making four different calls. And we are also performing one dequeue operation. Finally, we are printing states of the queue after each operation with the help of Print() function.

Conclusion

In this article, you learned about queue implementation using linked list. A linked list is a dynamic data structure that can store data elements with multiple data types. Further, the dynamic nature of linked lists allows resolving memory wastage problems in queue implementation. Here, you have gone through the development of primary queue operations with the help of a drive-through coding explanation. Following which, you have encountered coding implementation of queue using the C programming language.

Check out Simplilearn’s Post Graduate Program in Full Stack Web Development. The program familiarizes you with front-end, middleware, and back-end Java web developer technologies. You’ll learn how to build a complete application from end-to-end, test and deploy code, store data with MongoDB, and more. 

On that note, do you have any questions related to this article on queue implementation using linked list? If you have, please don’t hesitate to place them as comments towards the end of this page; we will respond to them soon!