Linked List Implementation of the queue

For implementing a queue using linked list we don’t need to know the size beforehand like array. The dynamic property of linked list allows queue to grow to any size. In case of a linked list also we use two pointers front and rear that perform the same task as in array. For more details about linked list implementation refer to this link.

Below is the code for linked list implementation of queue.

C++

// Program to implement queue using linked list
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a queue node
struct Qnode {
    int d;
    struct Qnode* next;
};
 
// Structure of a queue
struct Q {
    struct Qnode *front, *rear;
};
 
// Function to create a new node
struct Qnode* newNode(int k)
{
    struct Qnode* t
        = (struct Qnode*)malloc(sizeof(struct Qnode));
    t->d = k;
    t->next = NULL;
    return t;
}
 
// Function to create a queue
struct Q* createQ()
{
    struct Q* q = (struct Q*)malloc(sizeof(struct Q));
    q->front = q->rear = NULL;
    return q;
}
 
// Function to enqueue a new value
void enqueue(struct Q* q, int data)
{
    struct Qnode* t = newNode(data);
    if (q->rear == NULL) {
        q->front = q->rear = t;
        return;
    }
    q->rear->next = t;
    q->rear = t;
}
 
// Function for implementing deque
void dequeue(struct Q* q)
{
    if (q->front == NULL)
        return;
    struct Qnode* t = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(t);
}
 
// Driver code
int main()
{
    struct Q* q = createQ();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    dequeue(q);
 
    cout << "Queue front  " << q->front->d;
    cout << "\nQueue rear  " << q->rear->d;
    return 0;
}

Java

class Qnode {
    int d;
    Qnode next;
}
 
class Q {
    Qnode front, rear;
    Q() {
        front = rear = null;
    }
}
 
class Main {
    static Qnode newNode(int k) {
        Qnode t = new Qnode();
        t.d = k;
        t.next = null;
        return t;
    }
 
    static Q createQ() {
        Q q = new Q();
        return q;
    }
 
    static void enqueue(Q q, int data) {
        Qnode t = newNode(data);
        if (q.rear == null) {
            q.front = q.rear = t;
            return;
        }
        q.rear.next = t;
        q.rear = t;
    }
 
    static void dequeue(Q q) {
        if (q.front == null) {
            return;
        }
        Qnode t = q.front;
        q.front = q.front.next;
        if (q.front == null) {
            q.rear = null;
        }
        t = null;
    }
 
    public static void main(String[] args) {
        Q q = createQ();
        enqueue(q, 10);
        enqueue(q, 20);
        enqueue(q, 30);
        dequeue(q);
 
        System.out.println("Queue front: " + q.front.d);
        System.out.println("Queue rear: " + q.rear.d);
    }
}

Python

class Qnode:
    def __init__(self, d):
        self.d = d
        self.next = None
 
class Q:
    def __init__(self):
        self.front = None
        self.rear = None
 
def newNode(k):
    t = Qnode(k)
    return t
 
def createQ():
    q = Q()
    return q
 
def enqueue(q, data):
    t = newNode(data)
    if q.rear is None:
        q.front = q.rear = t
        return
    q.rear.next = t
    q.rear = t
 
def dequeue(q):
    if q.front is None:
        return
    t = q.front
    q.front = q.front.next
    if q.front is None:
        q.rear = None
    t = None
 
q = createQ()
enqueue(q, 10)
enqueue(q, 20)
enqueue(q, 30)
dequeue(q)
 
print("Queue front: ", q.front.d)
print("Queue rear: ", q.rear.d)

C#

public class Qnode
{
    public int d;
    public Qnode next;
 
    public Qnode(int val)
    {
        d = val;
        next = null;
    }
}
 
public class Q
{
    public Qnode front, rear;
 
    public Q()
    {
        front = rear = null;
    }
}
 
public class MainClass
{
    public static Qnode newNode(int k)
    {
        Qnode t = new Qnode(k);
        return t;
    }
 
    public static Q createQ()
    {
        Q q = new Q();
        return q;
    }
 
    public static void enqueue(Q q, int data)
    {
        Qnode t = newNode(data);
        if (q.rear == null)
        {
            q.front = q.rear = t;
            return;
        }
        q.rear.next = t;
        q.rear = t;
    }
 
    public static void dequeue(Q q)
    {
        if (q.front == null)
        {
            return;
        }
        Qnode t = q.front;
        q.front = q.front.next;
        if (q.front == null)
        {
            q.rear = null;
        }
        t = null;
    }
 
    public static void Main(string[] args)
    {
        Q q = createQ();
        enqueue(q, 10);
        enqueue(q, 20);
        enqueue(q, 30);
        dequeue(q);
 
        System.Console.WriteLine("Queue front: " + q.front.d);
        System.Console.WriteLine("Queue rear: " + q.rear.d);
    }
}
 
// This code is contributed by factworx412.

Javascript

// Program to implement queue using linked list
 
class QNode {
    constructor(data) {
    this.d = data;
    this.next = null;
    }
    }
     
    class Q {
    constructor() {
    this.front = this.rear = null;
    }
    }
     
    const newNode = data => new QNode(data);
     
    const createQ = () => new Q();
     
    const enqueue = (q, data) => {
    const t = newNode(data);
    if (q.rear === null) {
    q.front = q.rear = t;
    return;
    }
    q.rear.next = t;
    q.rear = t;
    };
     
    const dequeue = q => {
    if (q.front === null) return;
    const t = q.front;
    q.front = q.front.next;
    if (q.front === null) q.rear = null;
    };
     
    // Driver code
    const q = createQ();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    dequeue(q);
     
    console.log("Queue front: ", q.front.d);
    console.log("Queue rear: ", q.rear.d);
     
    // This code is contributed by aadityamaharshi21.

Output

Queue front  20
Queue rear  30

Time complexity: The time complexity of enqueue and dequeue operations in a queue implemented using linked list is O(1). This is because, in a linked list, insertion and deletion operations are performed in constant time.

Space complexity: The space complexity of a queue implemented using linked list is O(n), where n is the number of elements in the queue. This is because we need to allocate memory for each element in the queue and the size of the queue increases or decreases as elements are added or removed.

Note: For easy understanding only the enqueue() and deque() functionalities are shown here. For detailed implementation you can check the links provided for implementation.

Name some Queue implementations and compare them by efficiency of operations

A queue is a linear data structure in which insertion is done from one end called the rear end and deletion is done from another end called the front end. It follows FIFO (First In First Out) approach. The insertion in the queue is called enqueue operation and deletion in the queue is called dequeue operation.

A queue can be implemented in two ways:

Array implementation of queue
Linked List implementation of queue

Tags:

#Analysis of Algorithms #DSA #Queue #Queue

Array implementation of the queue:

Comparison:

Linked List Implementation of the queue

C++

Java

Python

C#

Javascript

Name some Queue implementations and compare them by efficiency of operations

Similar Reads