DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Beginner Friendly

Queue: Linked List Implementation

A dynamic queue with front and rear pointers. True O(1) dequeue — no element shifting needed.

Interactive Operations

Linked Nodes

True O(1) Both Ends

Queue Visualization

FRONT = where elements leave →→→ REAR = where elements arrive

Color Legend

DefaultActive / TargetCompletedNew node

Speed:

FRONT

REAR

Queue is empty — enqueue to begin

Size

NULL

Front

NULL

Rear

Current Step

Use Enqueue, Dequeue, or Peek to begin visualization.

Complexity Analysis

O(1)

Enqueue

O(1)

Dequeue

O(1)

Peek

O(n) Space

Dynamic allocation + pointer per node

True O(1) dequeue — unlike array queues which may require O(n) shifting, linked list queues always dequeue in O(1).

Two-Pointer Design

FRONT pointer

Points to the first node — where dequeue removes from

REAR pointer

Points to the last node — where enqueue adds to

Both NULL

When the queue is empty — single node makes both equal

vs Array Queue

True O(1) Dequeue

No element shifting — just move front pointer

Unlimited Size

No fixed capacity — grows dynamically

Memory Efficient

Allocates nodes as needed

Pointer Overhead

Each node needs memory for next pointer

Cache Locality

Nodes scattered in memory, not contiguous

Test Yourself

Q1/3

A linked list queue uses two pointers — what are they called?

Implementation

Python

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

class QueueLinkedList:
    def __init__(self):
        self.front = None  # Dequeue end
        self.rear = None   # Enqueue end
        self.size = 0

    def enqueue(self, value):
        new_node = Node(value)
        if self.rear is None:
            # Empty queue: front and rear both point to new node
            self.front = self.rear = new_node
        else:
            # Link new node to current rear, update rear
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1
        return value

    def dequeue(self):
        if self.front is None:
            raise Exception("Queue Underflow")
        value = self.front.value
        self.front = self.front.next
        if self.front is None:  # Queue became empty
            self.rear = None
        self.size -= 1
        return value

    def peek(self):
        if self.front is None:
            raise Exception("Queue is Empty")
        return self.front.value

    def is_empty(self):
        return self.front is None

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Beginner Friendly

Queue: Linked List Implementation

A dynamic queue with front and rear pointers. True O(1) dequeue — no element shifting needed.

Interactive Operations

Linked Nodes

True O(1) Both Ends

Queue Visualization

FRONT = where elements leave →→→ REAR = where elements arrive

Color Legend

DefaultActive / TargetCompletedNew node

Speed:

FRONT

REAR

Queue is empty — enqueue to begin

Size

NULL

Front

NULL

Rear

Current Step

Use Enqueue, Dequeue, or Peek to begin visualization.

Complexity Analysis

O(1)

Enqueue

O(1)

Dequeue

O(1)

Peek

O(n) Space

Dynamic allocation + pointer per node

True O(1) dequeue — unlike array queues which may require O(n) shifting, linked list queues always dequeue in O(1).

Two-Pointer Design

FRONT pointer

Points to the first node — where dequeue removes from

REAR pointer

Points to the last node — where enqueue adds to

Both NULL

When the queue is empty — single node makes both equal

vs Array Queue

True O(1) Dequeue

No element shifting — just move front pointer

Unlimited Size

No fixed capacity — grows dynamically

Memory Efficient

Allocates nodes as needed

Pointer Overhead

Each node needs memory for next pointer

Cache Locality

Nodes scattered in memory, not contiguous

Test Yourself

Q1/3

A linked list queue uses two pointers — what are they called?

Implementation

Python

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

class QueueLinkedList:
    def __init__(self):
        self.front = None  # Dequeue end
        self.rear = None   # Enqueue end
        self.size = 0

    def enqueue(self, value):
        new_node = Node(value)
        if self.rear is None:
            # Empty queue: front and rear both point to new node
            self.front = self.rear = new_node
        else:
            # Link new node to current rear, update rear
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1
        return value

    def dequeue(self):
        if self.front is None:
            raise Exception("Queue Underflow")
        value = self.front.value
        self.front = self.front.next
        if self.front is None:  # Queue became empty
            self.rear = None
        self.size -= 1
        return value

    def peek(self):
        if self.front is None:
            raise Exception("Queue is Empty")
        return self.front.value

    def is_empty(self):
        return self.front is None