Implementing Queue using Linked List

The core property of a Queue data structure is that it allows adding new elements only from one end and allows removal of elements only from the other end. The endpoint at which new elements are added is the tail/rear end of queue and the endpoint from which the elements are removed is the front end of queue.

A Linked list can be used to create a queue abstract data structure by restricting addition of new elements only after the last node or tail node While removing an element, we remove the head node and set the next node as head node of the linked list. For retrieving the front element, we just return the head node. Below illustrations showcase this behavior:

• Initialize an empty queue using an empty linked list
  • None
• Push element 4 into the queue
  • [4]->None
  • Now the front of the queue is 4
• Push element 6 into the queue
  • [4]->[6]->None
  • Now the front of the queue still 4
  • Think of element 6 as behind element 4
• Pop front/first element from the queue
  • [6]->None
  • Now the front element becomes 6
• Add elements 8 and 9 to the queue
  • [6]->[8]->[9]->None
  • Element 6 is still the front of queue
• Let’s pop front/first element from the queue
  • [8]->[9]->None
  • Now element 8 is the front element of queue

Below is the implementation of Queue using a Linked List: