AlgoDocs

Queue Implementation Using Linked List

Implementing queue operations using a 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

FeatureArrayLinked List
Memory AllocationRequires a contiguous block of memory.Uses non-contiguous memory; nodes allocated dynamically.
SizeFixed size (needs resizing for dynamic growth).Dynamic size, no resizing needed.
Memory EfficiencyCan 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 ElementsDirect, constant-time access by index.Linear access; must traverse from the front.
Overflow ConditionOccurs when the array is full.None (structure can grow dynamically).
Underflow ConditionOccurs when dequeuing from an empty queue.Occurs when dequeuing from an empty queue.

How is this guide?