Implementing Queue using Linked List

Click here to suggest a better video or view suggestions..

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:


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Queue:
    def __init__(self):
        self.head = None  # Initialize head node
        self.tail = None  # Initialize tail node

    def is_empty(self):
        # Queue is empty if head is None
        return self.head is None

    def push(self, value):
        new_node = Node(value)
        
        if self.is_empty():
            # If this is the first node,
            # it becomes the head and tail node
            self.head = new_node
            self.tail = new_node
        else:
            # Make this node as the tail node
            self.tail.next = new_node
            self.tail = new_node

    def pop(self):
        if self.is_empty():
            print("Queue is empty. Cannot pop.")
            return None

        popped_value = self.head.value
        if self.head == self.tail:
            # If the only element is removed,
            # Make the head and node tail as None
            self.head = None
            self.tail = None
        else:
            # Set head to the next node
            self.head = self.head.next

        return popped_value

    def front(self):
        if self.is_empty():
            print("Queue is empty.")
            return None

        return self.head.value

# Let's now test the Queue Implementation:
queue = Queue()

print("Is queue empty?", queue.is_empty())

queue.push(1)
queue.push(2)
queue.push(3)

print("Is queue empty?", queue.is_empty())
print("Front element:", queue.front())

print("Popped element:", queue.pop())
print("Popped element:", queue.pop())
print("Popped element:", queue.pop())

print("Is queue empty?", queue.is_empty())