Queue implementation using linked list

 
A queue is an linear data structure that serves as a collection of elements, with three main operations: enqueue, dequeue and peek. We have discussed about these operations in previous post and covered array implementation of queue data structure. In this post, linked list implementation of queue is discussed.
 

A queue can be easily implemented using a linked list. In singly linked list implementation, enqueueing happens at the tail of the list and dequeueing of items happens at head of the list. We need to maintain pointer to the last node to keep O(1) efficiency for insertion.

Since a doubly linked list offers O(1) insertion and deletion at both ends, it can be used if we want enqueueing to happen in the beginning and dequeueing to happen at the tail of the linked list.

C

Download   Run Code


Output:

Inserting 1
Inserting 2
Inserting 3
Inserting 4
Front element is 1
Removing 1
Removing 2
Removing 3
Removing 4
Queue is empty

 

The advantage of using linked list over arrays is that it is possible to implement a queue that can grow or shrink as much as needed. Since each new node will be dynamically allocated, overflow is not possible unless heap memory is exhausted. Using static array will put a restriction to the maximum capacity of the array which can lead to queue overflow.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz