Queue – Linked List ImplementationIn the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently. Show Linked List implementation of QueueDue to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue. The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1). In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory. In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue. Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty. The linked representation of queue is shown in the following figure. Basic Operation:Following are basic operations of Queue: Main Queue Operations: Auxiliary Queue operation: 1)Front(): Display the data front of the Queue. There are many different operations that we can implement.
EnQueueInserting an element in Queue.
DeQueueDeleting an element from Queue.
Display
Queue using linked listQueue using an array - drawbackIf we implement the queue using an array, we need to specify the array size at the beginning(at compile time). We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements. SolutionWe can implement the queue data structure using the linked list. In the linked list, we can change its size at runtime. How to implement a queue using a linked listA queue is a first-in-first-out (FIFO) data structure. It can be implemented using a linked list. The following are the three main operations that can be performed on a queue:
A queue implemented using a linked list. |