Dequeue Using Linked List in DSA Python - Build from Scratch

Dequeue Using Linked List

📖 Scenario: Imagine you are managing a line of people waiting for a ride. Sometimes people join the line at the front, sometimes at the back. Also, people can leave from either end. This is like a double-ended queue, or dequeue, which we will build using a linked list.

🎯 Goal: You will create a dequeue data structure using a linked list. You will add people to the front and back, remove people from the front and back, and finally show the current line.

📋 What You'll Learn

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

Create a Dequeue class with methods to add to front and back

Create methods to remove from front and back

Print the current state of the dequeue after operations

💡 Why This Matters

🌍 Real World

Dequeue is used in real-world scenarios like task scheduling, undo operations in editors, and managing buffers where insertion and deletion happen at both ends.

💼 Career

Understanding dequeue implementation helps in software development roles that require efficient data handling, such as backend development, systems programming, and algorithm design.

1

Create Node and Dequeue Classes

Create a class called Node with an __init__ method that takes data and sets self.data = data and self.next = None. Then create a class called Dequeue with an __init__ method that sets self.front = None and self.rear = None.

DSA Python

# Create Node and Dequeue classes with __init__ methods
# Your code here

Hint

Think of Node as a box holding a person and a pointer to the next box. The Dequeue keeps track of the first and last boxes.

2

Add Methods to Insert at Front and Rear

In the Dequeue class, add a method add_front(self, data) that creates a new Node with data and adds it to the front. Also add a method add_rear(self, data) that adds a new Node to the rear. Handle the case when the dequeue is empty by setting both front and rear to the new node.

DSA Python

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

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

    # Add a method add_front to add a node at the front
    # Your code here

    # Add a method add_rear to add a node at the rear
    # Your code here

Hint

When adding to front, point new node's next to current front. When adding to rear, point current rear's next to new node.

3

Add Methods to Remove from Front and Rear

In the Dequeue class, add a method remove_front(self) that removes the node from the front and returns its data. Also add a method remove_rear(self) that removes the node from the rear and returns its data. Handle empty dequeue by returning None. When removing the rear, traverse the list to find the node before rear.

DSA Python

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

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

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

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

    # Add a method remove_front to remove node from front and return its data
    # Your code here

    # Add a method remove_rear to remove node from rear and return its data
    # Your code here

Hint

To remove from front, move front pointer to next node. To remove from rear, find the node before rear and update rear pointer.

4

Print the Current Dequeue

Add a method print_dequeue(self) in the Dequeue class that prints the data of all nodes from front to rear separated by -> and ending with null. Then create a Dequeue object, add 10 to front, add 20 to rear, add 5 to front, remove one from rear, and finally print the dequeue.

DSA Python

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

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

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

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

    def remove_front(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

    def remove_rear(self):
        if self.rear is None:
            return None
        if self.front == self.rear:
            removed_data = self.rear.data
            self.front = self.rear = None
            return removed_data
        current = self.front
        while current.next != self.rear:
            current = current.next
        removed_data = self.rear.data
        self.rear = current
        self.rear.next = None
        return removed_data

    # Add a method print_dequeue to print all nodes from front to rear
    # Your code here

# Create a Dequeue object called dq
# Add 10 to front
# Add 20 to rear
# Add 5 to front
# Remove one from rear
# Print the dequeue
# Your code here

Hint

Traverse from front to rear, collect data, and print with arrows. Follow the steps exactly to get the final output.