Queue Using Linked List in Java (Complete Implementation with Detailed Explanation)

 

Queue Using Linked List (Deep Concept Guide)

Core Idea Recap

Queue = FIFO (First In First Out)

Linked List = Nodes dynamically connected.

Queue using Linked List me:

👉 Do pointers maintain karte hain:

  • Front → First element

  • Rear → Last element

Enqueue → Rear par add
Dequeue → Front se remove

What is Queue Using Linked List? 

Queue using Linked List is an implementation of the queue data structure where elements are stored dynamically in nodes connected by references instead of a fixed-size array. Each node contains a data field and a reference to the next node. The queue maintains two pointers: front (which points to the first element) and rear (which points to the last element). When an element is enqueued, a new node is created and added at the rear. When an element is dequeued, the front node is removed. This implementation allows the queue to grow dynamically without predefined size limitations.

 Why Linked List Queue is Better? 

In an array-based queue, once the rear pointer reaches the end of the array, no more elements can be added even if there is free space at the beginning, unless a circular queue is implemented. This creates limitations in fixed-size memory allocation. In contrast, a linked list-based queue dynamically allocates memory for each new node using heap memory. As long as system memory is available, the queue can grow without predefined size constraints. This makes linked list implementation more flexible and efficient for dynamic data handling in real-world applications like scheduling systems and buffering tasks.

 Internal Working (Step-by-Step)

Let’s enqueue 10, 20, 30.

Step 1: enqueue(10)

Front → 10 → null
Rear → 10

Step 2: enqueue(20)

Front → 10 → 20 → null
Rear → 20

Step 3: enqueue(30)

Front → 10 → 20 → 30 → null
Rear → 30

Now dequeue:

Remove 10

Front → 20 → 30 → null

 Technical Deep Explanation

Queue maintains:

  • Node front

  • Node rear

Each node has:

  • int data

  • Node next

Enqueue algorithm:

  1. Create new node

  2. If queue empty → front = rear = newNode

  3. Else → rear.next = newNode

  4. rear = newNode

Dequeue algorithm:

  1. If empty → underflow

  2. temp = front

  3. front = front.next

  4. If front == null → rear = null

 Complete Java Implementation

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class QueueLinkedList {

    private Node front, rear;

    public void enqueue(int data) {
        Node newNode = new Node(data);

        if (rear == null) {
            front = rear = newNode;
            return;
        }

        rear.next = newNode;
        rear = newNode;
    }

    public int dequeue() {
        if (front == null) {
            System.out.println("Queue Underflow");
            return -1;
        }

        int value = front.data;
        front = front.next;

        if (front == null)
            rear = null;

        return value;
    }

    public int peek() {
        if (front == null)
            return -1;

        return front.data;
    }
}

 Time Complexity (With Reasoning)

  • Enqueue → O(1)
    Direct rear pointer change.

  • Dequeue → O(1)
    Direct front pointer change.

  • Peek → O(1)

No traversal required.

 Space Complexity

O(n)

Har element ke liye ek node allocate hota hai.

 Advantages

  • Dynamic size

  • No fixed capacity

  • Efficient FIFO handling

 Disadvantages

  • Extra memory for pointer

  • Slightly complex than array implementation

 Array Queue vs Linked List Queue

FeatureArray QueueLinked List Queue
SizeFixedDynamic
MemoryContiguousNon-contiguous
OverflowPossibleRare

 Real Life Application

  • Printer queue

  • CPU scheduling

  • BFS in Graph

  • Order processing systems

 Basic Question

Agar queue me 5 → 10 → 15 enqueue kiya gaya ho
to do baar dequeue karne par kaunsa element front par bachega?

 Thinking Question

Queue using linked list me rear pointer maintain na karein to kya problem hogi?

Comments

Post a Comment

Popular posts from this blog

Binary Tree in Data Structures Explained in Depth (Concept, Types and Java Implementation)

  Binary Tree in Data Structures (Deep Concept Guide)  What is a Binary Tree? A Binary Tree is a specialized type of tree data structure in which each node can have at most two children, typically referred to as the left child and the right child. Unlike general trees where a node may have multiple children, a binary tree restricts branching to two directions. This limitation allows structured organization and efficient implementation of many algorithms such as searching, sorting, and expression evaluation. Binary trees form the foundation of advanced structures like Binary Search Trees (BST), Heaps, and AVL Trees. Because of their recursive nature, binary trees are often implemented and traversed using recursion. A Binary Tree is a hierarchical, non-linear data structure in which each node can have at most two children, referred to as the left child and right child. This restriction distinguishes it from a general tree where nodes may have multiple children. A binary tree...
Read more

Binary Tree Traversal Explained in Depth (Preorder, Inorder, Postorder with Java Code)

 Binary Tree Traversals (In Depth Guide) Ye topic bahut important hai kyunki: Tree ko read kaise karna hai — traversal se pata chalta hai 70% tree interview questions traversal based hote hain Recursion ka real use yahi se start hota hai DFS aur BFS concepts yahi se clear hote hain  What is Tree Traversal?  Tree Traversal is the process of visiting every node in a tree data structure exactly once in a specific order. Since a tree is hierarchical and non-linear, we cannot simply iterate over it like arrays or linked lists. Instead, we follow systematic traversal techniques to access nodes. Traversal ensures that all nodes are processed, whether for searching, printing, evaluating expressions, or performing modifications. Traversal techniques are mainly divided into two categories: Depth First Search (DFS) and Breadth First Search (BFS). DFS explores branches deeply before moving to the next branch, while BFS explores level by level. Understanding traversal is essential for...
Read more

Recursion in Java Explained with Examples (Base Case, Recursive Case & Dry Run Guide)

Recursion in Java (Complete Detailed Guide) Introduction  Recursion DSA ka ek powerful concept hai jo beginners ko thoda confusing lag sakta hai, lekin agar ek baar samajh aa gaya to Tree, Graph, Backtracking, Dynamic Programming sab easy ho jate hain. Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler input until a stopping condition is reached. Instead of using loops, recursion repeatedly breaks the problem into smaller subproblems of the same type. Each recursive call waits for the next call to finish before returning its result. Every recursive solution must contain a base case to stop execution and a recursive case to reduce the problem size. Recursion is widely used in tree traversal, divide-and-conquer algorithms, backtracking, and dynamic programming. Aaj hum recursion ko bilkul simple language me samjhenge — real-life example ke saath.  What is Recursion? Recursion is a programming technique in wh...
Read more