Introduction to Singly Linked List Queue
In the realm of data structures, queues play a crucial role in managing data in a First-In-First-Out (FIFO) manner. Singly linked list queue , also known as linked list queues, are a popular choice for implementing queues in programming. In this article, we delve into the intricacies of singly linked list queues, exploring their definition, applications, characteristics, types, advantages, and disadvantages.
What is Singly Linked List Queues
A singly linked list queues is a linear data structure that follows the FIFO principle, where elements are inserted at the rear (enqueue) and removed from the front (dequeue). It is implemented using a singly linked list, where each element, or node, contains a data field and a pointer to the next node in the sequence. Singly linked list queues provide efficient insertion and deletion operations, making them suitable for scenarios requiring sequential data processing.
Why We Use Singly Linked List Queues in Programming
Singly linked list queues are used in programming for several reasons:
- FIFO Operations: Singly linked list queues support FIFO operations, making them suitable for scenarios where data needs to be processed in the order it was received.
- Dynamic Size: Singly linked list queues can grow or shrink dynamically based on the number of elements in the queue, providing flexibility in memory usage.
- Memory Efficiency: Singly linked list queues allocate memory dynamically for each element, optimizing memory usage compared to fixed-size arrays.
- Ease of Implementation: Singly linked list queues are relatively easy to implement and understand, making them accessible to developers across various skill levels.
Characteristics of Singly Linked List Queues
- FIFO Ordering: Singly linked list queues follow the FIFO principle, ensuring that elements are inserted at the rear and removed from the front.
- Dynamic Size: Singly linked list queues can grow or shrink dynamically based on the number of elements in the queue, accommodating varying workloads.
- Pointer-Based Implementation: Singly linked list queues are implemented using pointers, with each node containing a data field and a pointer to the next node.
- Efficient Insertion and Deletion: Singly linked list queues provide efficient insertion and deletion operations, with constant time complexity for enqueue and dequeue operations.
Types of Singly Linked List Queues
- Basic Singly Linked List Queues: The standard implementation of a singly linked list queue, with enqueue and dequeue operations.
- Circular Singly Linked List Queues: A variation of the singly linked list queue where the last node points back to the first node, forming a circular structure.
Advantages of Singly Linked List Queues
- Dynamic Size: Singly linked list queues can grow or shrink dynamically based on the number of elements, accommodating varying workloads.
- Efficient Insertion and Deletion: Singly linked list queues provide efficient insertion and deletion operations, with constant time complexity for enqueue and dequeue operations.
- Memory Efficiency: Singly linked list queues allocate memory dynamically for each element, optimizing memory usage compared to fixed-size arrays.
- Ease of Implementation: Singly linked list queues are relatively easy to implement and understand, making them accessible to developers across various skill levels.
Disadvantages of Singly Linked List Queues
- Lack of Random Access: Singly linked list queues do not support random access to elements, limiting their applicability in scenarios requiring direct access to elements.
- Pointer Overhead: Singly linked list queues incur additional memory overhead due to the use of pointers for linking nodes, potentially impacting memory usage and performance.
- Tail Pointer Dependency: Singly linked list queues may require a tail pointer for efficient enqueue operations, adding complexity to the implementation.
Code Examples of Singly Linked List Queues
Below are code examples demonstrating singly linked list queue implementation in various programming languages:
Singly Linked List Queues in C#
using System;
using System.Collections.Generic;
public class Node {
public int data;
public Node next;
public Node(int value) {
data = value;
next = null;
}
}
public class Queue {
private Node front;
private Node rear;
public Queue() {
front = null;
rear = null;
}
public void Enqueue(int value) {
Node newNode = new Node(value);
if (rear == null) {
front = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
}
public int Dequeue() {
if (front == null) {
throw new InvalidOperationException("Queue is empty");
}
int value = front.data;
front = front.next;
if (front == null) {
rear = null;
}
return value;
}
public void Display() {
Node current = front;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
}
class Program {
static void Main() {
Queue queue = new Queue();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Display();
queue.Dequeue();
queue.Display();
}
}
Output
1 2 3 2 3
Singly Linked List Queues in C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}
void enqueue(struct Queue* queue, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}
int dequeue(struct Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return -1;
}
int value = queue->front->data;
struct Node* temp = queue->front;
queue->front = queue->front->next;
free(temp);
if (queue->front == NULL) {
queue->rear = NULL;
}
return value;
}
void display(struct Queue* queue) {
struct Node* current = queue->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Queue* queue = createQueue();
enqueue(queue, 1);
enqueue(queue, 2);
enqueue(queue, 3);
display(queue);
dequeue(queue);
display(queue);
return 0;
}
Output
1 2 3 2 3
Singly Linked List Queues in C++
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
void enqueue(int value) {
Node* newNode = new Node(value);
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
int dequeue() {
if (front == nullptr) {
throw std::runtime_error("Queue is empty");
}
int value = front->data;
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return value;
}
void display() {
Node* current = front;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
~Queue() {
while (front != nullptr) {
Node* temp = front;
front = front->next;
delete temp;
}
}
};
int main() {
Queue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.display();
queue.dequeue();
queue.display();
return 0;
}
Output
1 2 3 2 3
Singly Linked List Queues in Python
class Node:
def __init__(self, value):
self.data = value
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, value):
new_node = Node(value)
if self.rear is None:
self.front = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front is None:
raise Exception("Queue is empty")
value = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return value
def display(self):
current = self.front
while current:
print(current.data, end=" ")
current = current.next
print()
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()
queue.dequeue()
queue.display()
Output
1 2 3 2 3
Singly Linked List Queues in PHP
<?php
class Node {
public $data;
public $next;
public function __construct($value) {
$this->data = $value;
$this->next = null;
}
}
class Queue {
private $front;
private $rear;
public function __construct() {
$this->front = null;
$this->rear = null;
}
public function enqueue($value) {
$newNode = new Node($value);
if ($this->rear === null) {
$this->front = $newNode;
} else {
$this->rear->next = $newNode;
}
$this->rear = $newNode;
}
public function dequeue() {
if ($this->front === null) {
throw new Exception("Queue is empty");
}
$value = $this->front->data;
$this->front = $this->front->next;
if ($this->front === null) {
$this->rear = null;
}
return $value;
}
public function display() {
$current = $this->front;
while ($current !== null) {
echo $current->data . " ";
$current = $current->next;
}
echo "\n";
}
}
$queue = new Queue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
$queue->display();
$queue->dequeue();
$queue->display();
?>
Output
1 2 3 2 3
Singly Linked List Queues in JAVA
public class Node {
public int data;
public Node next;
public Node(int value) {
data = value;
next = null;
}
}
public class Queue {
private Node front;
private Node rear;
public Queue() {
front = null;
rear = null;
}
public void enqueue(int value) {
Node newNode = new Node(value);
if (rear == null) {
front = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
}
public int dequeue() {
if (front == null) {
throw new IllegalStateException("Queue is empty");
}
int value = front.data;
front = front.next;
if (front == null) {
rear = null;
}
return value;
}
public void display() {
Node current = front;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.display();
queue.dequeue();
queue.display();
}
}
Output
1 2 3 2 3
Singly Linked List Queues in JavaScript
class Node {
constructor(value) {
this.data = value;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.rear) {
this.front = newNode;
} else {
this.rear.next = newNode;
}
this.rear = newNode;
}
dequeue() {
if (!this.front) {
throw new Error("Queue is empty");
}
const value = this.front.data;
this.front = this.front.next;
if (!this.front) {
this.rear = null;
}
return value;
}
display() {
let current = this.front;
while (current) {
process.stdout.write(current.data + " ");
current = current.next;
}
console.log();
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.display();
queue.dequeue();
queue.display();
Output
1 2 3 2 3
Conclusion
In conclusion, singly linked list queues serve as efficient and flexible data structures for implementing FIFO operations in programming. They offer dynamic resizing, efficient insertion and deletion operations, and ease of implementation. Despite some limitations such as lack of random access and pointer overhead, singly linked list queues remain a popular choice for managing sequential data processing in various applications. By understanding the characteristics, advantages, and disadvantages of singly linked list queues, programmers can leverage this versatile data structure to develop robust and scalable solutions, contributing to the advancement of technology and innovation in the digital age.
For more visit my website Codelikechamp.com
