Table of Contents

In this article, you will learn how to implement a queue using a Linked List. A queue is an abstract data structure that works on the FIFO (First in First Out) mechanism, i.e., an element that gets inserted first is also removed first. A singly linked list is a data structure that contains a sequence of nodes. A node has data and a pointer to the next node. So, without further ado, let’s get started, and see how we can implement a queue with a singly linked list.

How to Implement a Queue using Linked List?

Here, the Linked List contains two pointers, front, and rear. The front pointer refers to the first node of the linked list, and the rear points to the last. Initially, when the linked list is empty, both front and rear refer to NULL. Moreover, when there is a single node only, the front and the rear pointers point to the same node.

Implementation

This implementation of a queue contains the following functionalities.

Enqueue

It adds an item at the rear of the Queue, i.e., inserts a node at the end of the Linked List. First, we create a new node with the given value. If the linked list (Queue) is empty, i.e., front and rear point to NULL, then the new node to be inserted will be the first one. Therefore, after insertion, both the front and the rear pointers will refer to this node. Otherwise, we assign the new node to the next of the rear, and we also update the rear to refer to the new node.

Dequeue

It removes an item from the front of the Queue, i.e., it deletes a node at the beginning of the linked list. It also returns the deleted value. First, we check if the front and rear are NULL. If this is the case, then the linked list (Queue) is empty, and since we cannot delete from an empty queue, we raise an underflow error. Otherwise, we store the current front (node to be deleted) in a temp variable. We update the front pointer to refer to its next. If the updated front is NULL, i.e., the node deleted was the only node, we also set rear to NULL as the linked list is empty now. Moreover, we store the deleted (temp) node’s value in a variable, delete that node and return the value.

Display

This method prints the queue contents from the front to the rear by traversing the linked list.

The Code

The code is given below.

class UnderflowError(Exception):
  #Raised when an operation such as dequeue is applied on an empty queue
  def __init__(self, message):
    self.message = message
    super().__init__(self.message)

#node for the linked list
class Node:
  def __init__(self, value=None, next=None):
    self.value = value 
    self.next = next #reference to the next node

#implementation of queue using linked list
class QueueLinkedList:
  def __init__(self):
    self.front = None
    self.rear = None
    self.length = 0 #total number of elements in the linked list

  #this method returns the length of the queue
  def len(self):
    return self.length

  #this method adds at the rear of the queue, i.e., at the end of the linked list
  def enqueue(self, value):
    node = Node(value) #creating a new node with the given value
    if self.front==None and self.rear==None: #if the queue is empty
      self.front = node
      self.rear = self.front
    else:
      self.rear.next = node
      self.rear = node
    self.length += 1

  #this method removes a value from the top of the queue, i.e., at the beginning of the linked list, and returns the value
  def dequeue(self):
    if self.front and self.rear: 
      temp  = self.front
      self.front = self.front.next #update the front to refer to the next of the current front
      if self.front == None: #all elements are removed
        self.rear = None
      popped_value = temp.value
      self.length -= 1 #decrement the length
      del temp 
      return popped_value
    else: #stack empty
      raise UnderflowError("Queue is Empty")
  

  #this method displays the contents of queue, i.e., print all values stored in the linked list
  def display(self):
    temp = self.front
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")


queue = QueueLinkedList()

#add values into a queue 
queue.enqueue(1)
queue.enqueue(5)
queue.enqueue(3)
queue.enqueue(9)
queue.enqueue(10)

#display the contents of the queue
print("Display the contents of the queue")
queue.display()

#remove values from the queue
print("Deleted item:", queue.dequeue())
print("Deleted item:", queue.dequeue())

#display the contents of the queue
print("Display the contents of the queue")
queue.display()

Output

Display the contents of the queue
1	5	3	9	10	
Deleted item: 1
Deleted item: 5
Display the contents of the queue
3     9    10

queue = QueueLinkedList()

#add values into a queue 
queue.enqueue(1)
queue.enqueue(5)

#display the contents of the queue
print("Display the contents of the queue")
queue.display()

#remove values from the queue
print("Deleted item:", queue.dequeue())
print("Deleted item:", queue.dequeue())
print("Deleted item:", queue.dequeue())

#display the contents of the queue
print("Display the contents of the queue")
queue.display()