Queue: Linked List Implementation

Explore how a queue works using dynamic linked list implementation. Watch how nodes are managed with front and rear pointers for efficient FIFO operations.

Interactive Operations

Linked List Implementation

O(1) Operations

Queue Visualization

Speed:

FRONT

REAR

Empty Queue

Size: 0

Memory: Dynamic allocation

Front: NULLRear: NULL

Current Step:

Select an operation to begin visualization

Complexity Analysis

O(1)

Enqueue

O(1)

Dequeue

O(1)

Peek

O(n) Space

Dynamic allocation + pointer overhead

Advantages over Array

O(1) Dequeue: No shifting required unlike array

Dynamic Size: No fixed maximum capacity

Memory Efficient: Only allocates what's needed

Pointer Overhead: Extra memory for next pointers

Operations

Enqueue

Create node, link to rear, update rear pointer

Dequeue

Store front value, move front pointer, deallocate

Peek

Return front node value without modification

Two-Pointer Approach

• Front Pointer: Points to first node (dequeue end)

• Rear Pointer: Points to last node (enqueue end)

• Empty Queue: Both pointers are NULL

• Single Element: Both pointers point to same node

• Efficiency: Enables O(1) operations at both ends

Applications

• Process Scheduling: OS task management

• Network Buffers: Packet handling in routers

• Print Spooling: Document queue management

• BFS Traversal: Graph/tree exploration

• Asynchronous Data: Producer-consumer patterns

Implementation

class Node:
    def __init__(self, value):
        self.value = value      # Data stored in the node
        self.next = None        # Reference to next node

class QueueLinkedList:
    def __init__(self):
        self.front = None       # Reference to front of queue
        self.rear = None        # Reference to rear of queue
        self.size = 0          # Track number of elements
    
    def enqueue(self, value):
        # Create new node
        new_node = Node(value)
        
        if self.rear is None:
            # First node - both front and rear point to it
            self.front = self.rear = new_node
        else:
            # Link new node to current rear
            self.rear.next = new_node
            # Update rear to point to new node
            self.rear = new_node
        
        self.size += 1
        return value
    
    def dequeue(self):
        # Check for queue underflow
        if self.front is None:
            raise Exception("Queue Underflow")
        
        # Get value from front node
        value = self.front.value
        
        # Update front to next node
        self.front = self.front.next
        
        # If queue becomes empty, reset rear to None
        if self.front is None:
            self.rear = None
        
        self.size -= 1
        return value
    
    def peek(self):
        # Check if queue is empty
        if self.front is None:
            raise Exception("Queue is Empty")
        
        return self.front.value
    
    def is_empty(self):
        return self.front is None
    
    def get_size(self):
        return self.size
    
    def display(self):
        # Traverse and display all elements
        current = self.front
        elements = []
        while current:
            elements.append(current.value)
            current = current.next
        return elements