Linked Implementation of Queues — Data Structures

What Is a Queue?

A queue is a simple data structure that works on the principle of FIFO — First In, First Out.

Think of a queue at a movie ticket counter or a bus stop.
The person who gets in line first is the one who gets served first.
New people can only join from the end (called the rear), and tickets are given from the *front of the line.

So, in short:

• Insertion (enqueue) happens at the rear.
• Deletion (dequeue) happens at the front.

---

💾 Two Ways to Implement a Queue

Queues can be implemented in two main ways:

1. Using Arrays
2. Using Linked Lists

The array-based approach has one major limitation — you must fix the size beforehand.
Once the array is full, you can’t add more elements without creating a new one.

That’s why the linked implementation is often preferred — it grows and shrinks dynamically as needed!

---

⚙️ What Is Linked Implementation of Queue?

In the linked implementation, a queue is built using a linked list.
Each element is stored in a node, and every node contains two parts:

1. Data field – stores the actual value.
2. Pointer field – stores the address of the next node.

We also maintain two special pointers:

• Front → points to the first node (the one to be deleted next).
• Rear → points to the last node (where new nodes are added).

---

🧩 Structure of a Node

Each node looks like this:

+--------+-----------+
|  Data  |   Next    |
+--------+-----------+

---

🧱 Diagram of a Linked Queue

Here’s how it looks visually:

Front → [10 | •] → [20 | •] → [30 | •] → NULL
                                ↑
                               Rear

• The Front points to the first element (10).
• The Rear points to the last element (30).
• Each node points to the next one, and the last node’s link is NULL (it’s the end of the queue).

---

⚡ Operations on a Linked Queue

Let’s break down the main operations step by step — just like you’d perform them in real life.

---

🔹 1. Enqueue (Insertion)

This operation adds a new element to the rear of the queue.

Steps:

1. Create a new node and store the data in it.
2. Set its next pointer to NULL (since it’ll be the last node).
3. If the queue is empty (both front and rear are NULL), make both point to this new node.
4. Otherwise, link the new node to the current rear, and update the rear pointer to the new node.

Example:
Let’s add 40 to this queue:

Before Enqueue:
Front → [10] → [20] → [30] → NULL
                            ↑
                           Rear

After Enqueue (40):
Front → [10] → [20] → [30] → [40] → NULL
                                    ↑
                                   Rear

---

🔹 2. Dequeue (Deletion)

This operation removes an element from the front of the queue.

Steps:

1. Check if the queue is empty (if front is NULL).

• If yes, show “Queue Underflow”.

1. Store the front node in a temporary pointer.
2. Move the front pointer to the next node.
3. Free the memory of the old front node.
4. If after deletion the queue becomes empty, set rear to NULL too.

Example:
If we dequeue from the queue above:

Before Dequeue:
Front → [10] → [20] → [30] → [40] → NULL
                                    ↑
                                   Rear

After Dequeue:
Front → [20] → [30] → [40] → NULL
                              ↑
                             Rear

The node containing 10 is removed.

---

🔹 3. Peek (Front Element)

Sometimes we just want to see the element at the front without removing it.

Step:

• Simply display the data in the node pointed to by front.

Example:
If the queue is [20 → 30 → 40],
then Peek = 20 (the front element).

---

🔹 4. isEmpty

This operation checks whether the queue has any elements or not.

Condition:
If front == NULL, the queue is empty.

---

🧠 Why Use Linked Implementation?

Let’s compare it with array-based queues:

Feature	Array Queue	Linked Queue
Size	Fixed	Dynamic (no limit)
Memory Use	May waste space	Efficient
Overflow	Can occur when full	Almost never (unless memory full)
Deletion	Needs shifting (in some cases)	Easy — just move pointers

So, the linked queue is much more flexible and memory-friendly.

---

💡 Real-Life Analogy

Think of a linked queue like people waiting in line at a coffee shop.
Each person (node) holds the hand of the next person (link).
When a new customer arrives, they join the end of the line (rear).
When the barista serves someone, that person leaves from the front.

The line keeps moving forward — dynamically growing and shrinking as people come and go!

---

🧾 Example in C-like Pseudocode

Here’s how a queue might look in a simple program:

struct Node {
    int data;
    struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

void dequeue() {
    if (front == NULL) {
        printf("Queue Underflow");
        return;
    }
    struct Node* temp = front;
    front = front->next;
    if (front == NULL)
        rear = NULL;
    free(temp);
}

This shows how pointers move dynamically — no fixed size, no wasted space!