Queue Implementation Using Linked List

Implementation

Enqueue Operation

Create a new node with the given data.
Check if the queue is empty:
- If head is NULL, set both head and tail to point to the newly created node.
- Otherwise, link the tail node's next pointer to the new node, then update tail to point to the new node.
Increment the size of the queue by 1.

Dequeue Operation

Check if the queue is empty:
- If head is NULL, print an error message ("Queue is empty") and return.
Remove the front node:
- Store the current head in a temporary variable (oldHead).
- Update head to point to the next node (head = head->next).
- If the new head is NULL, set tail to NULL (indicating the queue is now empty).
Delete the oldHead node to free memory.
Decrement the size of the queue by 1.

IsEmpty Operation

Check if the queue is empty:
- If head is NULL, return true (queue is empty).
- Otherwise, return false.

Front Operation

Check if the queue is empty:
- If head is NULL, print an error message ("Queue is empty") and return -1 (indicating an invalid front element).
Return the data of the node at the front (head->data).

Coding Implementation

//queueusinglinkedlist.cpp
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *next;
Node(int data) {
    this->data = data;
    this->next = NULL;
}
};

class Queue {
Node *head;
Node *tail;
int size;

public:
Queue() {
    this->head = NULL;
    this->tail = NULL;
    this->size = 0;
}

void enqueue(int data) {
    Node *temp = new Node(data);
    if (this->head == NULL) { 
        this->head = temp;
        this->tail = temp;
    } else { 
        this->tail->next = temp;
        this->tail = temp;
    }
    this->size++;
}

void dequeue() {
    if (this->head == NULL) { 
        cout << "Queue is empty, cannot dequeue." << endl;
        return;
    }
    Node *oldHead = this->head;
    this->head = this->head->next;
    if (this->head == NULL) { 
        this->tail = NULL;
    }
    delete oldHead;
    this->size--;
}

int getSize() {
    return this->size;
}

bool isEmpty() {
    return this->head == NULL;
}

int getFront() {
    if (this->head == NULL) {
        cout << "Queue is empty, no front element." << endl;
        return -1;
    }
    return this->head->data;
}
};

int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);

while (!q.isEmpty()) {
    cout << q.getFront() << " ";
    q.dequeue();
}
// 10 20 30 40 50

}

print("We're Working")

console.log("We're Working");

Comparison of Queue Implementation Using Array and Linked List

Feature	Array	Linked List
Memory Allocation	Requires a contiguous block of memory.	Uses non-contiguous memory; nodes allocated dynamically.
Size	Fixed size (needs resizing for dynamic growth).	Dynamic size, no resizing needed.
Memory Efficiency	Can waste space if resized or over-allocated.	Allocates memory exactly as needed.
Enqueue (Insert)	`O(1)` — amortized `O(n)` if resizing is triggered.	`O(1)` — always efficient.
Dequeue (Delete)	`O(1)` — straightforward.	`O(1)` — straightforward.
Access to Elements	Direct, constant-time access by index.	Linear access; must traverse from the front.
Overflow Condition	Occurs when the array is full.	None (structure can grow dynamically).
Underflow Condition	Occurs when dequeuing from an empty queue.	Occurs when dequeuing from an empty queue.

Queue Implementation Using Linked List

Implementation

Enqueue Operation

Dequeue Operation

IsEmpty Operation

Front Operation

Coding Implementation

Comparison of Queue Implementation Using Array and Linked List

On this page