Queue Implementation Using Linked List in DSA Python - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line of people waiting to buy tickets. The first person who comes in is the first to get the ticket and leave the line. This is how a queue works in computers.

🎯 Goal: You will build a queue using a linked list. You will add people to the end of the line and remove them from the front, just like in real life.

📋 What You'll Learn

Create a Node class to hold data and a link to the next node

Create a Queue class with methods to add (enqueue) and remove (dequeue) nodes

Keep track of the front and rear of the queue

Print the queue contents after operations

💡 Why This Matters

🌍 Real World

Queues are used in real life for waiting lines, printer job scheduling, and handling requests in order.

💼 Career

Understanding queues and linked lists is important for software development roles that involve data processing, task scheduling, and system design.

1

Create the Node class

Create a class called Node with an __init__ method that takes data and sets self.data = data and self.next = None.

DSA Python

# Create the Node class with __init__ method
# Your code here

Hint

Think of Node as a box holding a value and a pointer to the next box.

2

Create the Queue class with front and rear

Create a class called Queue with an __init__ method that sets self.front = None and self.rear = None.

DSA Python

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

# Create the Queue class with __init__ method
# Your code here

Hint

The queue needs to know where the line starts (front) and ends (rear).

3

Add enqueue and dequeue methods

In the Queue class, add a method enqueue(self, data) that adds a new Node with data to the rear. Also add a method dequeue(self) that removes the front node and returns its data. Handle empty queue cases.

DSA Python

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

# Add enqueue and dequeue methods below
# Your code here

Hint

Enqueue adds to the rear. Dequeue removes from the front. Remember to update front and rear carefully.

4

Print the queue contents after enqueue and dequeue

Create a print_queue(queue) function that prints the queue elements from front to rear separated by -> and ending with null. Then create a Queue object called q, enqueue 10, 20, 30, dequeue once, and print the queue using print_queue(q).

DSA Python

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

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

    def dequeue(self):
        if self.front is None:
            return None
        removed_data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return removed_data

# Define print_queue function
# Create Queue object q
# Enqueue 10, 20, 30
# Dequeue once
# Print queue
# Your code here

Hint

Traverse from front to rear and collect data to print. After dequeue, the first element (10) is removed.