Write code to implement a queue using linked list.

I. Introduction

A queue is a data structure that follows the FIFO (First-In, First-Out) principle. Think of a real-world queue – the first person in line is the first person served. A linked list is a linear data structure where elements are stored in nodes, with each node pointing to the next.

This blog post shows how to build a queue using a linked list in Python. Linked lists make queues efficient because adding and removing items is fast, even if you have many items.

II. Understanding the Node Structure

Each item in our linked list will be a node. A node has two parts: the data (the item itself) and a pointer (next) to the next node in the list.

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

III. Implementing the Queue Class

Our Queue class will keep track of the front and rear of the queue using pointers.

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

enqueue(data)

Adds an item to the rear (end) of the queue.

    def enqueue(self, data):
        new_node = Node(data)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

dequeue()

Removes and returns the item at the front of the queue.

    def dequeue(self):
        if self.isEmpty():
            return None
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return data

isEmpty()

Checks if the queue is empty.

    def isEmpty(self):
        return self.head is None

peek()

Shows the front item without removing it.

    def peek(self):
        if self.isEmpty():
            return None
        return self.head.data

IV. Code Example: Complete Queue Implementation

Here's the full Python code:

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

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

    def enqueue(self, data):
        new_node = Node(data)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def dequeue(self):
        if self.isEmpty():
            return None
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return data

    def isEmpty(self):
        return self.head is None

    def peek(self):
        if self.isEmpty():
            return None
        return self.head.data


# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue())  # Output: 10
print(queue.peek())   # Output: 20
print(queue.isEmpty()) # Output: False

V. Time and Space Complexity

Most operations (enqueue, dequeue, isEmpty, peek) have a time complexity of O(1) – they take constant time. The space complexity is O(n), where n is the number of items in the queue, because we need to store all the nodes.

VI. Advantages and Disadvantages

Advantages:

• Dynamic sizing: The queue automatically grows or shrinks as needed.
• Efficient insertion/deletion at both ends.

Disadvantages:

• Extra memory overhead for pointers in each node.

VII. Conclusion

We've successfully created a queue using a linked list in Python. This approach gives us a dynamic queue with fast insertion and deletion. Explore other queue implementations (like using arrays) and how queues are used in real-world applications (like task scheduling or breadth-first search).