Implementation of a Queue Using a Linked List: Algorithm, Code, and Examples

TL;DR: A queue using a linked list stores each element in a node and tracks two pointers, front and rear. Enqueue adds a new node at the rear; dequeue removes the node at the front. Both run in O(1) time with no fixed size limit, unlike an array-based queue.

A queue is a First-In-First-Out (FIFO) data structure, and like a stack, it can be built on an array or a linked list. An array-based queue needs a size decided in advance, and naive dequeue implementations waste the freed-up space at the front unless the array is shifted or treated as circular. A linked-list-based queue avoids this: nodes are allocated as elements are enqueued and freed as they're dequeued, so the queue grows and shrinks exactly as needed. 

This article covers how a linked-list queue works, the enqueue, dequeue, and peek operations with pseudocode, complete working code in C, C++, Java, and Python, time and space complexity, and how it compares to an array-based queue.

What Is Queue Implementation Using Linked List?

In a linked-list-based queue, each element is stored in a node containing a data field and a pointer to the next node. Two pointers track the queue: front, which points to the next node to be removed, and rear, which points to the most recently added node.

• Enqueue (insertion) always happens at rear, so the new node becomes the new rear.
• Dequeue (removal) always happens at front, so front moves to the next node and the old front is freed.
• When the queue has exactly one node, front and rear point to the same node.
• When the queue is empty, both front and rear are NULL.
• Overflow isn't a fixed-capacity limit like it is in an array; it happens only when there isn't enough heap memory left to allocate a new node.
• Underflow happens when you attempt a dequeue or peek while the queue is empty.

Because enqueue only touches the rear and dequeue only touches the front, neither operation ever needs to shift or scan through the rest of the queue, which is why both stay at O(1).

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

Why Use a Linked List Instead of an Array for a Queue?

An array-based queue has to reserve its size upfront. Once full, growing it means allocating a bigger array and copying every element over, an O(n) operation. A naive array-based dequeue also either shifts every remaining element left (also O(n)) or leaves a gap at the front that a circular array must reclaim. A linked-list-based queue sidesteps both problems: it allocates one node per enqueue and frees one node per dequeue, using exactly the memory it needs.

Because it allocates memory as it goes, a linked-list queue is inherently a dynamic queue implementation. There's no upper bound decided in advance, and no resize-and-copy step, unlike a plain array that still needs periodic reallocation even when implemented as a growable dynamic array.

Front and Rear in a Linked-List Queue

Front and rear are the only two pointers a linked-list queue needs to track, and mixing up their roles is the most common source of bugs when implementing one:

• front always points to the node that dequeue will remove next, the oldest element still in the queue.
• rear always points to the node that the most recent enqueue added, the newest element in the queue.
• On the first enqueue into an empty queue, set front and rear to the same new node.
• On every dequeue that empties the queue (front and rear point to the same single node), reset both pointers to NULL, not just front; otherwise, rear would point to freed memory.

Here's How to Land a Top Software Developer JobAI-Powered Full Stack Developer ProgramExplore Program

Queue Operations Using Linked List: Algorithm and Pseudocode

Enqueue (insert at rear):

enqueue(value):
    create newNode
    newNode.data = value
    newNode.next = NULL
    if front is NULL:
        front = rear = newNode
        return
    rear.next = newNode
    rear = newNode

Dequeue (remove from front):

dequeue():
    if front is NULL:
        report underflow
        return
    temp = front
    value = temp.data
    if front == rear:
        front = rear = NULL
    else:
        front = front.next
    free(temp)
    return value

Peek (view the front element without removing it):

peek():
    if front is NULL:
        report empty queue
        return
    return front.data

isEmpty (check whether the queue has any elements):

isEmpty():
    return front == NULL

Queue Implementation Using Linked List in C

#include <stdio.h>
#include <stdlib.h>

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

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

int isEmpty() {
    return front == NULL;
}

void enqueue(int x) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    if (isEmpty()) {
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear = temp;
    printf("%d enqueued to queue.\n", x);
}

int dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow: queue is empty.\n");
        return -1;
    }
    struct Node* temp = front;
    int dequeuedValue = temp->data;
    if (front == rear) {
        front = rear = NULL;
    } else {
        front = front->next;
    }
    free(temp);
    return dequeuedValue;
}

int peek() {
    if (isEmpty()) {
        printf("Queue is empty.\n");
        return -1;
    }
    return front->data;
}

void display() {
    struct Node* temp = front;
    printf("Queue (front to rear): ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    printf("Front element is %d\n", peek());
    printf("Dequeued element: %d\n", dequeue());
    display();
    return 0;
}

Sample output:

10 enqueued to queue.
20 enqueued to queue.
30 enqueued to queue.
Queue (front to rear): 10 20 30
Front element is 10
Dequeued element: 10
Queue (front to rear): 20 30

Queue Implementation Using Linked List in C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    void enqueue(int x) {
        Node* temp = new Node();
        temp->data = x;
        temp->next = nullptr;
        if (isEmpty()) {
            front = rear = temp;
            return;
        }
        rear->next = temp;
        rear = temp;
        cout << x << " enqueued to queue." << endl;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow: queue is empty." << endl;
            return -1;
        }
        Node* temp = front;
        int dequeuedValue = temp->data;
        if (front == rear) {
            front = rear = nullptr;
        } else {
            front = front->next;
        }
        delete temp;
        return dequeuedValue;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return front->data;
    }

    void display() {
        Node* temp = front;
        cout << "Queue (front to rear): ";
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();
    cout << "Front element is " << q.peek() << endl;
    cout << "Dequeued element: " << q.dequeue() << endl;
    q.display();
    return 0;
}

Learn 45+ in-demand full-stack development skills and tools, including Frontend Development, Backend Development, Version Control and Collaboration, Database Management, and AI-Assisted Development, with our Full Stack Developer Course.

Queue Implementation Using Linked List in Java

public class QueueLinkedList {

    private Node front;
    private Node rear;

    private class Node {
        int data;
        Node next;

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

    public boolean isEmpty() {
        return front == null;
    }

    public void enqueue(int x) {
        Node newNode = new Node(x);
        if (isEmpty()) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
        System.out.println(x + " enqueued to queue.");
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue Underflow: queue is empty.");
            return -1;
        }
        int dequeuedValue = front.data;
        if (front == rear) {
            front = rear = null;
        } else {
            front = front.next;
        }
        return dequeuedValue;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return front.data;
    }

    public void display() {
        Node temp = front;
        System.out.print("Queue (front to rear): ");
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        QueueLinkedList queue = new QueueLinkedList();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.display();
        System.out.println("Front element is " + queue.peek());
        System.out.println("Dequeued element: " + queue.dequeue());
        queue.display();
    }
}

Dive Deep Into Java Core ConceptsJava Certification TrainingENROLL NOW

Queue Implementation Using Linked List in Python

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


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

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

    def enqueue(self, x):
        new_node = Node(x)
        if self.is_empty():
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node
        print(f"{x} enqueued to queue.")

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow: queue is empty.")
            return None
        dequeued_value = self.front.data
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
        return dequeued_value

    def peek(self):
        if self.is_empty():
            print("Queue is empty.")
            return None
        return self.front.data

    def display(self):
        temp = self.front
        elements = []
        while temp is not None:
            elements.append(temp.data)
            temp = temp.next
        print("Queue (front to rear):", elements)


if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.display()
    print("Front element is", queue.peek())
    print("Dequeued element:", queue.dequeue())
    queue.display()

All four implementations follow the same pseudocode shown earlier; only syntax for structs/classes, memory management, and printing changes between languages.

Deep Dive Into Core Python ConceptsWith the Python Certification CourseENROLL NOW

Time and Space Complexity of Queue Using Linked List

Space complexity is O(n) for n elements, since each element needs its own node plus one extra pointer (next) beyond the data itself. That per-node pointer is the main memory overhead compared to an array-based queue, which stores only the raw data with no per-element pointer cost.

Advantages of Queue Using Linked List

• Grows and shrinks dynamically at runtime; no fixed size decided in advance.
• Enqueue and dequeue are O(1) worst-case on every call, with no occasional resize-and-copy cost like a dynamic array.
• No memory wasted on unused, pre-allocated capacity, since each node is allocated only when needed and freed immediately when dequeued.
• Avoids the array-based queue's dequeue problem entirely; there's no leftover gap at the front to manage or wrap around.

Disadvantages of Queue Using Linked List

• Each node uses extra memory for its pointer, in addition to the actual data.
• No random access; reaching any element other than the front requires traversing from the front, which is O(n).
• Slightly worse cache performance than an array-based queue, since nodes are scattered across the heap instead of sitting in contiguous memory.
• Slightly more bookkeeping than an array-based queue, since you must track both front and rear and keep them in sync, especially in the single-element and empty-queue edge cases.

Applications of Queue Using Linked List

• Task and job scheduling: Operating systems and print spoolers process requests in the order they arrive, without knowing in advance how many will show up.
• Breadth-first search (BFS): Graph and tree traversal algorithms use a queue to visit nodes level by level, where the number of nodes to track isn't known in advance.
• Handling requests in web servers: Incoming requests are queued and processed in order, with the queue growing and shrinking as load changes.
• Buffering data streams: Between producers and consumers running at different speeds, such as I/O buffers or message queues, where a fixed-size array risks overflow or wastes memory.

The step-by-step Software Engineer Roadmap is designed for professionals seeking to understand the full scope of the profession. Explore the skills, tools, salary potential, and career roadmap needed to build a successful career as a software engineer.

Conclusion

A linked-list queue solves the same core limitation for FIFO structures that a linked-list stack solves for LIFO ones: an array's fixed, pre-decided size, and, in a queue's case, the added headache of reclaiming space at the front after each dequeue. By allocating one node per enqueue and freeing it on dequeue, the queue grows and shrinks exactly as needed, with every enqueue, dequeue, and peek running in constant time. The trade-off is the same one seen with linked lists generally: extra pointer memory per node and no random access or cache-friendly contiguous storage.

To build on these data structure fundamentals with hands-on projects, explore Simplilearn's Full Stack Developer Course. You can also explore Simplilearn’s Software Development courses to build broader programming and software engineering skills for real-world development. 

Key Takeaways

• A linked-list-based queue tracks two pointers, front and rear; enqueue always acts on rear, dequeue always acts on front.
• Enqueue, dequeue, peek, and isEmpty are all O(1) worst-case; only traversal/display is O(n).
• Space complexity is O(n), with one extra pointer of overhead per node compared to an array-based queue.
• When the queue empties, reset both front and rear to NULL, not just front.
• Unlike an array-based queue, a linked-list queue never needs a resize-and-copy step or circular-array logic to reclaim space at the front.

FAQ

1. Can a queue be implemented using a singly linked list?

Yes, and it's the standard approach. Since enqueue only touches the rear and dequeue only touches the front, a singly linked list with just a next pointer is enough; a doubly linked list isn't needed unless the queue also needs to be traversed or modified from both ends, as in a deque.

2. What is the difference between an array-based queue and a linked-list queue?

An array-based queue has a fixed capacity and needs either a circular array or element shifting to reuse space freed by dequeue. A linked-list queue has no fixed capacity and reclaims space automatically, since a dequeued node is simply freed, at the cost of one extra pointer per element.

3. Which is better for a queue, an array or a linked list?

Neither is universally better. An array-based (especially circular) queue is faster and more cache-friendly when the maximum size is predictable. A linked-list-based queue is the better choice when the size is unpredictable or can grow very large, since it avoids resizing and never wastes memory on unused capacity.

4. What happens if front and rear aren't updated correctly during dequeue?

If front is advanced without checking whether the queue just became empty, rear can be left pointing at freed memory instead of also being reset to NULL. That's the most common bug in a hand-written linked-list queue, and it typically shows up as a crash or corrupted state on the very next enqueue.