UNIT 2

Introduction to Queue.
Queues are a fundamental data structure operating on the First-In-First-Out (FIFO) principle,
meaning the first item added is the first to be removed. They are important for organizing and
managing data in many applications, including operating systems, network protocols, and
data processing pipelines. Queues are essentially used to manage threads in multithreading
and implementing priority queuing systems.
Definition: A queue is a linear data structure that operates on the First In, First Out (FIFO)
principle, similar to a line of people waiting for a service. The element inserted first is the
first one to be removed. In C++, a queue can be implemented manually (using arrays or
linked lists) or by using the built-in std::queue container adapter from the Standard Template
Library (STL).
A Queue Data Structure is a fundamental concept in computer science used for storing and
managing data in a specific order.
• It follows the principle of "First in, First out" (FIFO), where the first element added to
the queue is the first one to be removed.
• It is used as a buffer in computer systems where we have speed mismatch between two
devices that communicate with each other. For example, CPU and keyboard and two
devices in a network
• Queue is also used in Operating System algorithms like CPU Scheduling and Memory
Management, and many standard algorithms like Breadth First Search of Graph, Level
Order Traversal of a Tree.
• Queue is very frequently used in most programming languages. A real-world example of
queue can be a single-lane one-way road, where the vehicle enters first, exits first. More
real-world examples can be seen as queues at the ticket windows and bus-stops.

Key Concepts
• FIFO Principle: Rule is “First in First Out” , the elements are processed in the strict order
they were received.
• Front: The Position of the element that will be removed next.
• Rear (or Back/Tail): The Position where the next new elements will be inseted.
• Size: Current number of elements in the queue.
• Capacity : Maximum number of elements the queue can hold.
 Basic Operations
The fundamental operations in a queue are:
• enqueue() (or push() in C++ STL): Adds an element to the rear of the queue.
• dequeue() (or pop() in C++ STL): Removes the element from the front of the queue.
• front() (or peek() ): Returns the value of the element at the front of the
queue without removing it.
• back() : Returns the value of the last element in the queue without removing it.
• empty() : Checks if the queue is empty, returning a Boolean value.
• size() : Returns the number of elements currently in the queue.
Characteristics of a Queue:
1. Linear order: Maintains the order of elements.
2. FIFO Principle: The first element inserted is the first to be removed.
3. Operations:
o Enqueue: Adding an element to the end of the queue.
o Dequeue: Removing an element from the front of the queue.
Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or
pointers. As a small example in this tutorial, we implement queues using a one-dimensional
array.

Dequeue: Enqueue:
Deletion Addition

Memory Representation of Queue.

Queues can be represented in memory in two primary ways: Using Array, Linked List.
1. Array Representation(Contiguous Memory)
When using an array, Elements are stored in sequential memory locations. This approach
requires a fixed maximum size to be defined before hand. A contiguous block of memory
(an Array) is allocated in RAM.
Pointers: Two pointers (or indices) manage the queue's operations:
front: Points to the index of the first (oldest) element in the queue, which is the next element
to be removed (dequeued).
rear (or back): Points to the index where the next new element will be inserted (enqueued).
Initially, if queue is empty, front = -1, rear = -1.
Memory Usage: While simple and efficient for basic access (O(1)), a simple linear array
implementation can be inefficient in its use of memory. Elements dequeued from the front
leave unused space in the array that cannot be easily reused until the entire queue is empty or
the remaining elements are shifted, which is time-consuming (O(N)).
Circular Queue: To address the memory wastage problem, a circular queue uses the array in
a logical circle, allowing the rear pointer to wrap around to the beginning of the array if space
is available there. This efficiently utilizes memory by reusing the empty spaces.

2. Linked List Representation

In a linked list implementation, the queue elements are stored in non-contiguous memory
locations using dynamically allocated nodes.
Dynamic Size: This approach is flexible as the queue can grow or shrink in size as needed
during runtime, avoiding the fixed-size limitation of arrays.
Nodes and Pointers: Each element is a node containing the data and a pointer (or link) to the
next node in the sequence.
Pointers: Two pointers manage the queue's operations:
front: Stores the memory address of the first node of the queue.
rear: Stores the memory address of the last node of the queue.
Memory Usage: Memory is allocated and deallocated dynamically (on the heap), offering
efficient memory management when the maximum size of the queue is unknown or highly
variable. The front and rear pointers are typically stored on the stack (if they are local
variables) or within a class structure.
Advantage : The approach is more flexible in terms of size, avoiding the overflow issues of a
fixed size.

Enqueue operation.
Algorithm of Enqueue.

Step 1: Start.
Step 2: if(rear = = max-1) then
Write “Queue is Full! Insertion is not possible”.
Step3: else
Step 4: if(front = = -1) then [Condition is checked queue is empty or not]
front=0. [front position at first in queue]
rear + +. [rear is incremented to insert element to queue]
queue[rear]=value. [data item at value variable is assigned to rear position in queue].
write “ Insertion Success”.
Step 5: Stop.
Queues maintain two data pointers, front and rear.
Therefore, its operations are comparatively difficult to implement than that of stacks.
Below are the steps to enqueue (insert) data into a queue
• Check whether the queue is full or not.
• If the queue is full – print the overflow error and exit the program.
• If the queue is not full – increment the rear pointer to point to the next empty space.
• Else add the element in the position pointed by Rear.
• Return success.
Dequeue Operation.
Algorithm of Dequeue.
Step 1: Start.
Step 2: if(front = = -1) then
Write “ Queue is Empty! Deletion is not possible”.
Step 3: else
Step 4: Write “ Deleted , Element ” queue[front]. [To delete an element from front]
front + +. [Incrementing front]
Step 4: if(front > rear ) then [It is used check Whether queue only one element]
front = rear = -1. [On deleting one element, queue has zero elements]

Below are the steps to perform the dequeue operation

• Check whether the queue is full or not
• If the queue is empty – print the underflow error and exit the program.
• If the queue is not empty – access the data where the front is pointing.
• Else increment the front pointer to point to the next available data element.
• Return success.
Display Queue.
Algorithm
Step 1: Start.
Step 2: if(front = -1) then
Write “Queue is Empty”.
Step 3: else
Step 4: Write “ Queue Elements are !:”
for(int i= front; i<= rear; i++)
Write “Queue[i]”.
Step 5: End.

Types of Queues.
There are four different types of queues in data structures:
• Simple Queue
• Circular Queue
• Priority Queue
• Double-Ended Queue (Deque)
1)Simple Queue (Linear Queue) : Simple Queue (or Linear Queue): This is the most basic
queue, where insertion (enqueue) always happens at the rear (back) and deletion (dequeue)
always happens at the front (head). It strictly follows the FIFO rule.

It is Ordered collection of comparable data kinds. • Queue structure is FIFO (First in, First
Out).
• When a new element is added, all elements added before the new element must be deleted
to remove the new element

Key Characteristics of Linear Queue:

1)Structure: Utilizes a linear array or linked list to store elements.
2)Operations: Insertion (enqueue) happens at the rear, and deletion (dequeue) occurs at the
front.
3)Index Management: Uses two pointers or indices: front and rear. The front points to the
first element, and the rear points to the last element.
4)Growth: The rear index moves towards the end of the array with each addition, and the
front index moves towards the end with each removal.

Advantages of Linear Queue:

1)Simplicity: Easy to implement and understand.
2)Sequential Access: Processes elements in a strict FIFO order, ensuring predictability.
Disadvantages of Linear Queue:
The major drawback of linear queue is that insertion is done only from rear end.
1)Inefficiency: Even after dequeuing elements, space is not reused, leading to inefficiency.
After several operations, unused space accumulates at the beginning of the array, leading to
wasted memory.
2)Static Size: In fixed-size array implementations, the queue cannot reuse the vacated spaces,
potentially leading to overflow even when space is available.
3)Requires shifting of elements, which is costly.
Linear Queue Representation Steps
A Linear Queue is a simple queue where elements are inserted at the rear and removed from
the front. It follows the FIFO (First In, First Out) principle.
Operations in a Linear Queue
1)Enqueue (Insertion) :
o Check if the queue is full (rear == SIZE - 1).
o If not full, increment rear and insert the new element.
o If inserting the first element, set front = 0.
2)Dequeue (Deletion) :
o Check if the queue is empty (front == -1 or front > rear).
o If not empty, remove the front element and increment front.
o If the last element is removed, reset front and rear to -1.

Algorithm of Linear Queue.

Enqueue (Insertion).
Step 1: Start.
Step 2: if (rear = = n-1)
Step 3: Write “ Queue Overflow ! Insertion is not possible.”
Step 4: else
Step 5: if (front = = -1)
Step 6: set front =0.
Step 7: Input value.
Step 8: rear = rear+ 1.
Step 9: queue[rear] = value.
Step 10: Stop.

Dequeue (Deletion)
Step 1: Start.
Step 2: if (front = = -1 || front > rear)
Step 3: Write “Queue is Empty! Deletion is not possible.”
Step 4: else
Step 5: Write” Deleted element from queue.” Queue[front]
Step 6: front = front +1.
Step 7: Stop.

Basic operations performed on Linear Queue.

1)Enqueue: Insert an element at rear end of the linear queue.
2)Dequeue: Removes an element at front end of the linear queue.
3)Peek / front : View front element without removing it.
4) isEmpty: Returns true if queue is empty, otherwise false.
5)isFull : Checks if Queue is full or not.

Write a C++ program to implement Linear Queue.

#include< iostream>
Using namespace std;
int queue[5], n=3, val, front = -1, rear = -1;
void enqueue( )
{
if (rear = = n-1)
cout<<”Queue Overflow” <<endl;
else{
if(front= = -1)
front=0;
cout<<”Insert the element in Queue:”<<endl;
cin>>val;
rear ++;
queue[rear]=val;
}
}
void dequeue( ){
if(front = = -1 | | front> rear)
{
cout<<”Queue underflow”<<endl;
}
else {
 cout<<”Element Deleted from Queue is :”, queue[front]<<endl;
front ++;
}
}
void display( ){
if(front = = -1 | | front> rear)
{
cout<<”Queue is Empty”<<endl;
}
else{
cout<<”Queue Elements are : “<<endl;
for(int i =front; i<=rear; i++)
{
cout<<queue[i]<<” “;
cout<<endl;
}
}
}

int main( )
{
int ch;
cout<<”[Link] Element into Queue.”<<endl;
cout<<”[Link] Element from Queue .”<<endl;
cout<”[Link] all the elements of Queue.”<<endl;
cout<<”4. Exit. “<<endl;
do{
cout<<”Enter your choice:”<<Endl;
cin>>ch;
switch(ch)
{
case 1: enqueue( );
break;
case 2: dequeue( );
break;
case 3: display( );
break;
case 4:
cout<<”Exit”<<endl;
break;
default:
cout<<”Invalid choice.”<<endl;
}
}while(ch! =4);
return 0;
}
Applications of Simple Queue
• Resource Allocation: Simple Queues are is useful for resource allocation in operating
systems that manage resource requests such as CPU, memory, and I/O devices.
• Batch Processing: Queues accommodate batch jobs, for instance, tasks like data
processing or rendering images, which are queued up for sequential execution.
• Message Buffering: It helps to buffer the message in communication systems to ensure a
smooth data flow among processes.
Circular Queue.
A circular queue is a type of queue in which the last position is connected to the first position
to make a circle. It is a linear data structure in which the operations are performed based on
FIFO (First In First Out) principle.
What is a Circular Queue?
A Circular Queue is an extended version of a normal queue where the last element of the
queue is connected to the first element of the queue forming a circle.
A circular queue is a special case of a simple queue in which the last member is linked to the
first, forming a circle-like structure.
• The last node is connected to the first node.
• Also known as a Ring Buffer, the nodes are connected end to end.
• Insertion takes place at the front of the queue, and deletion at the end of the queue.
• Example of circular queue application: Insertion of days in a week. 1.

Consider a scenario where you're simulating a printer queue. New documents are constantly
being added to the queue, and as they are printed, they are removed. In a circular queue, if
the queue becomes full and documents are printed, new documents can still be added at the
beginning of the queue, as it is circular in nature.

Why we need Circular Queue in C++?

Circular queue concept is especially helpful when the queue is implemented using an array.
In linear implementation, when the rear pointer reaches the end of the queue, we cannot insert
new elements even if there are empty locations in the queue.
Circular queues address this limitation by connecting the front and rear ends, allowing the
rear to go back to the start in when the rear reaches the end of the queue.
Concept Behind Circular Queue
There are two different concepts behind circular queue depending upon which data structure
it is using in its implementation:
For Linked List Implementation, we can directly use the circular linked list where the last
element of the list points to the head of the list.
For Array Implementation
For array implementation for circular queue, we use the mathematical concept of modular (or
circular) increment. In this concept, a value that is being incremented will wrap around a
particular threshold value. It can be achieved using the formula.
value = (value + 1) % threshold_value;
For Example, if value is 9, and threshold is 10. Incrementing the value by 1 will make it 10
and dividing it with 10 will yield the remainder 0.
Circular Queue Representation Steps
A Circular Queue overcomes the limitation of the linear queue by connecting the last position
back to the first position, making use of empty spaces. Operations in a Circular Queue
1)Enqueue (Insertion)
o Check if the queue is full using the condition: (rear + 1) % SIZE == front
o If not full, insert the new element at (rear + 1) % SIZE.
o If inserting the first element, set front = 0. 2.
2)Dequeue (Deletion)
o Check if the queue is empty (front == -1).
o Remove the front element and move front to (front + 1) % SIZE.
o If the last element is removed, reset front and rear to -1.
Key Characteristics of Circular Queue:
Structure: Uses a circular array or linked list to store elements.
Operations: Similar to linear queues but with circular index management.
Index Management: Both front and rear pointers move in a circular manner. When the rear
or front reaches the end of the array, it wraps around to the beginning.
Efficient Memory Usage: By wrapping around, the circular queue utilizes available space
that would be inaccessible in a standard queue when the rear reaches the end of the array.
This design ensures all available memory is utilized efficiently.
Wrap-Around Logic: The circular behaviour is achieved using modular arithmetic ( (index
+ 1) % SIZE ) to move the front and rear pointers.
Fixed Size: Circular queues are typically implemented with a fixed-size array, defined at the
time of creation.

Implementation of Queue
A queue can be implemented in two ways:
• Sequential allocation: It can be implemented using an array. A queue implemented using
an array can organize only a limited number of elements.
• Linked list allocation: It can be implemented using a linked list. A queue implemented
using a linked list can organize unlimited elements.
Advantages of Circular Queue.
1)Efficient use of memory as spaces are reused.
2)Memory Utilization: Optimizes memory use by reusing the vacated space.
3)No Overflow Until Full: Prevents overflow until the queue is genuinely full, maximizing
space utilization.
4)No need for shifting elements.
Disadvantages of Circular Queue.
1)Complex Implementation: More complex to implement due to wrap-around logic.
2)Difficult Debugging: Debugging issues can be more challenging compared to linear
queues.
3) Data Loss: If Queue is Full and new elements are inserted without removing old ones. It
can lead to data loss.
4)Fixed Size: Array is Fixed and linked list is dynamic.
Basic Circular queue operations.
Below are the basic queue operations in data structure:-
1)enqueue( ) : Process of adding or storing an element to the end of the queue
2)dequeue() : Process of removing or accessing an element from the front of the queue .
3)peek( ) : Used to get the element at the front of the queue without removing it .
4)initialize( ) : Creates an empty queue .
5)isfull( ) : Checks if the queue is full by comparing if ( (rear + 1) % size = = front)
6)isempty( ) : Check if the queue is empty by verifying if front = -1.
7)rear ( ) : Retrieves the value of the last element without removing it.

Algorithm of Circular Queue.

Enqueue(Insertion)
Step 1:Start
Step 2: if( (rear + 1) % max = = front) // Queue is Full
Step 3: return “Queue Overflow”.
Step 4: else
Step 5: if( front = rear = -1) // Queue is Empty.
Step 6: front = rear =0.
Step 7: else
Step 8: rear = (rear + 1) % max.
Step 9 : queue[rear] = data.
Step 10: endif
Step 11: end.

Dequeue (Deletion)
Step 1: Start
Step 2: if (front = = -1) // Queue is Full.
Step 3: return “Queue Underflow”.
Step 4: else
Step 5: if(front = = rear) //Queue has only one element.
Step 6: queue[front]=data.
Step 7: front rear = -1.
Step 8: else
Step 9: data = queue[front].
Step 10: front = (front + 1) % max.
Step 11: endif
Step 12: end.

Display of Circular Queue.

Step 1: Start.
Step 2: if (front = = -1)
Step 3: Write” Queue is Empty”.
Step 4: else
Step 5: set i=front
Step 6: do
Step 7:Write “ queue[i] ”
Step 8: i = (i+1) % max.
Step 9:while( i! = (rear + 1) % max)
Step 10: end While
Step 11: end.

Write a C++ program to implement Circular Queue.

#include< iostream >
Using namespace std;
#define size 5
class Circularqueue {
private:
int queue[size];
int front, rear ;
public:
Circularqueue( ){
front = -1, rear =-1;
}
// Function to insert an element
void enqueue(int value){
if((rear + 1) % size = = front){
cout<<”Queue is Full. Cannot insert “<<value<<endl;
return ;
}
if(front = = -1){
front = 0;
rear = 0;
}
else
{
rear = (rear+1) %size;
}
queue[rear] value;
cout<<value<<”Inserted into the queue”<<endl;
}
void dequeue( ) {
if (front = = -1){
cout<<”Queue is Empty”<<endl;
return ;
}
cout<<queue[front]<<”deleted from queue:”<<endl;
// If only one element was present
if(front = = rear){
front = -1;
rear= -1;
}
else
{
front=(front+1) %size;
}
}
void display ( ){
if(front = = -1){
cout<<”Queue is Empty:”<<endl;
return;
}
cout<<”Queue elements are :”<<endl;
int i = front;
while( True){
cout<<queue[i]<<” “<<endl;
if(i = = rear)
break;
i= (i+1) % size;
}
cout<<endl;
}
};
int main( ){
circularqueue cq;
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);
[Link]( );
[Link]( );
[Link]( );
[Link] ( );
[Link](60);
[Link](70);
return 0;
}

Output:
Inserted Elements are: 10 20 30 40 50
Deleted Elements : 10 20
Queue Elements are : 30 40 50
After inserting
Inserted elements are 60 70
Queue Elements are : 30 40 50 60 70
Representation of Circular Queue in C++
The circular queue in C++ can be represented as a class which contains the rear and front
index pointers, array to store queue elements, and the member functions to provide the basic
operations.
class Queue {
private:
int front, rear;
int arr[MAX_SIZE];
public
........
}

Implementation of isEmpty for Circular Queue

The queue is only empty when the front == rear pointer

Algorithm of isEmpty
if front is equal to rear
return true
else
return false

Implementation of isFull for Circular Queue

The queue will be full when the incremented rear pointer is equal to the front pointer.
Algorithm of isFull
if (rear + 1) % size is equal to front
return true;
else
return false;

Implementation of Enqueue for Circular Queue

We insert the new elements at the end of the queue using rear pointer. We first check if the
queue is full or not.
Algorithm of Enqueue
if (isFull(queue)) {
print "Queue Overflow"
return
else
rear = (rear + 1) % size
arr[rear] = new_element
Implementation of Dequeue for Circular Queue

The elements are removed from the queue at the front of the queue. We first need to check
whether queue is empty or not.
Algorithm of Enqueue
if (isEmpty(queue)) {
print "Queue Underflow"
return
else
front = (front + 1) % size
// C++ program to implement the circular queue using array
#include <iostream>

// defining the max size of the queue

#define MAX_SIZE 5
using namespace std;
// class that represents queue
class Queue {
public:
// index pointers and data array
int front, rear;
int arr[MAX_SIZE];

// constructor to initialize the index pointers

Queue() { front = rear = 0; }

// checking if queue is empty

bool isEmpty()
{
if (front == rear)
return true;
return false;
}

// checking if the queue is full

bool isFull()
{
if ((rear + 1) % MAX_SIZE == front)
return true;
return false;
}

// enqueue operation
void enqueue(int val)
{
if (this->isFull()) {
printf("Queue Overflow!\n");
return;
 }
rear = (rear + 1) % MAX_SIZE;
arr[rear] = val;
}

// dequeue operation
void dequeue()
{
if (this->isEmpty()) {
printf("Queue Underflow!\n");
return;
}
front = (front + 1) % MAX_SIZE;
}

// peek function
int peek()
{
if (this->isEmpty()) {
printf("Queue is Empty!\n");
return -1;
}
return arr[(front + 1) % MAX_SIZE];
}

// utility to print queue

void print()
{
if (this->isEmpty())
return;
for (int i = (front + 1) % MAX_SIZE; i < rear;
i = (i + 1) % MAX_SIZE) {

printf("%d ", arr[i]);

}
cout << arr[rear];
}
};

// driver code
int main()
{
Queue q;

[Link](11);
[Link](11);
[Link](11);
[Link](11);
[Link](11);
[Link](11);
 [Link]();
[Link]();
[Link](123);
[Link]();
return 0;
}

Output
Queue Overflow!
Queue Overflow!
123

Applications of Circular queue.

Circular queues are used in various real-world scenarios due to their efficiency:
• CPU Scheduling: Operating systems use a circular queue in the Round-Robin scheduling
algorithm to manage processes efficiently.
• Buffer Management: They are frequently used in scenarios like keyboard buffers or
multimedia streaming, where data continuously flows in and out of a fixed-size memory area.
Frequently used in data streaming and buffering applications.
• Traffic Management: Computer-controlled traffic signal systems use circular queues to
cycle through lights in a fair, repeated order. Simulation world systems and processes, e.g.,
traffic flow control.
• Memory Management: The unused memory locations in the case of ordinary queues can be
utilized in circular queues

3)Priority Queue: In this type, each element is assigned a priority, and elements are served
based on their priority, not their order of arrival. Higher-priority elements are processed first.
If elements have the same priority, they are served based on their order in the queue.
4)Double-Ended Queue (Deque): Often pronounced "deck," a deque is a more flexible
queue that allows for both insertion and deletion operations at both the front and the rear
ends. Due to this flexibility, it can support both FIFO and Last-In, First-Out (LIFO)
operations, effectively functioning as both a queue and a stack. Deques can be further
categorized into: Input-restricted Deque: Allows insertions at one end but deletions from both
ends.
Output-restricted Deque: Allows insertions at both ends but deletions from only one end.
Concurrent Queue: This is a type of queue designed to be accessed by multiple threads
simultaneously in a thread-safe manner, which is crucial in multi-threaded applications to
prevent data corruption and race conditions.
Application of Queue.
A Queue is a linear data structure. This data structure follows a particular order in which the
operations are performed. The order is First In First Out (FIFO).
• Network: In a network, a queue is used in devices such as a router or a switch. another
application of a queue is a mail queue which is a directory that stores data and controls
files for mail messages.
• Job Scheduling: The computer has a task to execute a particular number of jobs that are
scheduled to be executed one after another. These jobs are assigned to the processor one
by one which is organized using a queue.
• Shared resources: Queues are used as waiting lists for a single shared resource.

Real-time application of Queue:

• Working as a buffer between a slow and a fast device. For example keyboard and CPU,
and two devices on network.
• ATM Booth Line
• Ticket Counter Line
• CPU task scheduling
• Waiting time of each customer at call centres.
• Managing requests on a single shared resource, such as CPU scheduling and disk
scheduling
• Handling hardware or real-time systems interrupts
• Handling website traffic
• Routers and switches in networking
• Maintaining the playlist in media players
• CPU Scheduling: Used in Round-Robin and other scheduling algorithms.
• Data Transmission: Ensures proper order in packets.
• Printers: Jobs are managed in a queue.
• Call Centre Systems: Handles customer requests in a queue.
• Breadth-First Search (BFS): In graph traversal algorithms.
Advantages of Queue:
• Queues are useful when a particular service is used by multiple consumers.
• Queues are fast in speed for data inter-process communication.
• Queues can be used for the implementation of other data structures.
Disadvantages of Queue:
• The operations such as insertion and deletion of elements from the middle are time
consuming.
• In a classical queue, a new element can only be inserted when the existing elements are
deleted from the queue.
• Searching an element takes O(N) time.
• Maximum size of a queue must be defined prior in case of array implementation.

Linked List
Introduction
A linked list in C++ is a dynamic linear data structure composed of a sequence of nodes.
Unlike arrays, nodes are not stored in contiguous memory locations but are linked together
using pointers. It allows user to store data in non – contiguous memory locations.
A linked list is a dynamic linear data structure whose memory size can be allocated or de
allocated at run time based on the operation insertion or deletion, this helps in using system
memory efficiently. Linked lists can be used to implement various data structures like a stack,
queue, graph, hash maps, etc.
Core Concepts
Node: The fundamental building block of a linked list. Each node typically contains two
parts:
Data: The actual value or information stored in the node (e.g., an integer, a string, another
object).
Pointer (or Link): A pointer that holds the memory address of the next node in the sequence.
In a singly linked list, the last node's pointer is nullptr to mark the end of the list.
Head: A pointer to the very first node in the linked list. If the list is empty, the head pointer is
nullptr.
Dynamic Memory Allocation: Linked lists use dynamic memory allocation (using new and
delete in C++) to allocate and deallocate memory for nodes at runtime, allowing them to
grow or shrink as needed.

Basic Operations: Common operations performed on linked lists include:

1)Insertion: Adding a new node at the beginning, end, or a specific position.
2)Deletion: Removing a node from the beginning, end, or a specific position.
3)Traversal: Iterating through the list, usually from the head, to access or print the data in
each node.
4)Search: Finding a specific element within the list by traversing the nodes

Definition: A linked list is defined as a collection of nodes where each node consists of two
members which represents its value(data part) and a next/previous pointer(Address part)
which stores the address for the next/previous node.

Linked List Representation in C++

In C++, linked lists are basically represented by a pointer to the first node, which is
commonly referred to as the "head" of the list. Each node in the list is defined by a structure
that includes a data field and a pointer pointing to the same type of structure. This type of
structure is known as a self-referential structure.

A linked list starts with a head node which points to the first node. Every node consists of
data which holds the actual data (value) associated with the node and a next pointer which
holds the memory address of the next node in the linked list. The last node is called the tail
node in the list which points to null indicating the end of the list.

Types of Linked Lists

1)Singly Linked List: The simplest type, where each node has a pointer only to the next
node. Traversal is unidirectional (forward from head to tail).

2)Doubly Linked List: Each node contains pointers to both the next and the previous nodes
in the sequence. This allows for traversal in both forward and backward directions.

3)Circular Linked List: Can be either singly or doubly linked, but the last node's pointer
points back to the first node (head) instead of nullptr, forming a continuous loop.

1. Singly Linked List in C++

The singly linked list is the simplest form of linked list in which the node contains two
members data and a next pointer that stores the address of the next node. Each node is a
singly linked list is connected through the next pointer and the next pointer of the last node
points to NULL denoting the end of the linked list. The following diagram describes the
structure of a singly linked list:
Singly Linked List Representation
Singly linked list can be represented as a pointer to the first node, where each node
contains: Data: Actual information is stored. . Next: Pointer to the next node.
// Structure to represent the singly linked list
struct Node {
int data; // Data field - can be of any type and count
struct Node* next; // Pointer to the next node
};

Memory Representation of Singly Linked List

Basic Operations for Singly Linked List

Operation Time Space

Operation Type Description Complexity Complexity

Insert a new node at the

O (1) O (1)
At Beginning start of a linked list.

Insert a new node at the

O (N) O (1)
At the End end of the linked list.

Insert a new node at a

At Specific specific position in a O (N) O (1)
Insertion Position linked list.

From Delete a node from the

O (1) O (1)
Deletion Beginning start of a linked list
 Operation Time Space
Operation Type Description Complexity Complexity

Delete a node at the end of

O (N) O (1)
From the End a linked list.

Delete a node from a

A Specific specific position of a O (N) O (1)
Node linked list.

Traverse the linked list

O (N) O (1)
Traversal from start to end.

In, SLL Traversal is possible only forward direction. It uses less memory (only one
pointer per node), and simple to implement.
Implementation of Singly Linked list in C++
Here is the Implementation of Singly Linked List in C++ with basic operations:
Operations included: 1)Insertion at beginning . 2)Insertion at end 3)Deletion at beginning
4)Display
In this operation, we have only insertionatbeginning, and deletionatend in SLL.
Algorithm for Insertion at Beginning (SLL)
Algorithm Steps:
Step 1: Start
Step 2: Create a new node
Step 3: Read the value
Step 4: Store value in new node
Step 5: Set new node → next = head
Step 6: Set head = new node
Step 7: Stop

C++ Code.
void insertBeginning(int value) {
Node* newNode = new Node(); // Step 2
newNode->data = value; // Step 4
newNode->next = head; // Step 5
head = newNode; // Step 6
}
Algorithm for Deletion at end (SLL)
Step 1: Start
Step 2: if head = = NULL
Write” List is Empty”
Step 3: if head → next = = NULL
delete head
set head = NULL
stop
Step 4: set temp =head
Step 5: Traverse the list until temp → next →next = = NULL
Step 6: Delete temp → next
Step7: set temp → next NULL
Step 8: Stop.
C++ Code
void deleteend( ){
if (head = = NULL) {
cout<<”List is empty”<<endl;
return ;
}
// Only one node
if(head → next = = NULL) {
delete head;
head = NULL;
cout<<”Last Node deleted \n”<< endl;
return;
}
// Step 4: Traverse to second last node
Node * temp = head;
while (temp → next →next ! = NULL)
temp = temp → next;
}
// Step 6 and 7 : Delete last node.
delete temp → next;
temp →next = NULL;
cout<<”Last Node Deleted \n”<<endl;
}
Algorithm for Display
Step 1: Start.
Step 2: if head = = NULL
Write “ List is Empty”/
Stop.
Step 3: set temp = head
Step 4: While(temp! = NULL)
Wite” temp → data”
Move temp = temp → next
Step 5: Stop.
C++ Code
void display() {

if(head = = NULL)
{
cout<<”List is Empty”<< endl;
return;
}
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
1)Write a C++ program to insert a node at the beginning of a singly linked List.
Output
2) Write a C++ program to delete a node at the end of a singly Linked List.
Output:
Advantages of Singly Linked List
1)Dynamic Size (no fixed limit Like Arrays), No need of Contiguous memory)
2)Efficient insertion and deletion at beginning and end. We also have insertion at the
middle efficient if we have reference or pointer to the node after which we need to insert.
3)It is Less Expensive.
4)It doesn’t require shifting elements.
5) It is extended according to requirements.
6)Can implement complex data structures like Stack, Queues, Graph.
Disadvantages.
1)Cannot traversed backward.
2)Extra memory required for sorting pointers for each node.
3)No direct or random access (need traversal) Strictly sequentially.
4)Cache unfriendly (not stored in contiguous memory)
5)It is not easy to sort elements.

Applications of Singly Linked Lists

A singly linked list is a basic form of linked list where each node contains a pointer to the
next node but no reference to the previous one. This structure is simple and efficient for
applications that require sequential data processing.

1. Simple Dynamic Memory Management

Singly linked lists are widely used for managing memory dynamically, where memory is
allocated and deallocated as needed without requiring continuous blocks of storage.
This is particularly useful in embedded systems, where memory availability is limited.
2. Used in Basic Stack and Queue Implementations
Stacks (LIFO - Last In, First Out) and Queues (FIFO - First In, First Out) can be
implemented using singly linked lists without needing a predefined size, unlike arrays.
In stacks, elements are inserted and removed from the top, while in queues, elements are
added at the rear and removed from the front.
3. Creating Sparse Matrix Representations
Sparse matrices, which have a large number of zero elements, can be efficiently stored using
singly linked lists. Instead of storing every element (including zeros), only non-zero values
and their positions are stored, reducing memory usage.
4. Managing Symbol Tables in Compilers
Compilers use symbol tables to store information about variables, functions, and objects in a
program. A singly linked list is often used to store and retrieve symbols dynamically,
ensuring efficient memory usage and fast lookup operations.
5)Polynomial Representation: Efficiently represent sparse polynomials where each term is
stored in a node.
6)Hashing: Used in chaining methods to resolve hash collisions.
5."Undo" and "Redo" Functionality: Many software applications, like text editors or
graphic design tools, use linked lists to store a history of actions. Each action is a node,
allowing the program to traverse backward to reverse operations.
[Link] Browser History: While often a doubly linked list is used to allow forward and
backward navigation, the concept applies where each node is a URL, allowing users to move
between visited pages.
[Link] and Video Playlists: Media players use linked lists to manage playlists, allowing
users to easily navigate to the next or previous song by updating a pointer.
[Link] System Allocation: File systems can use linked allocation, where each block of a file
contains a pointer to the next block, allowing files to be stored in non-contiguous memory
locations and avoiding fragmentation.
2. Doubly Linked List in C++
The doubly linked list is the modified version of the singly linked list where each node of
the doubly linked consists of three data members data, next and prev. The prev is a pointer
that stores the address of the previous node in the linked list sequence. Each node in a
doubly linked list except the first and the last node is connected with each other through the
prev and next pointer. The prev pointer of the first node and the next pointer of the last
node points to NULL in the doubly linked list. The following diagram describes the
structure of a doubly linked list:

Doubly Linked List Representation

Doubly linked list can be represented as pointer to the first node where each node contains:

// Structure to represent the doubly linked list

struct Node {
int data; // Data field - can be of any type and count
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
Basic Operations for Doubly Linked List

Operation Time Space

Operation Type Description Complexity Complexity

Insert a new node at the

O (1) O (1)
At Beginning start of a linked list.

Insert a new node at the

O (N) O (1)
At the End end of the linked list.

Insert a new node at a

At Specific specific position in a O (N) O (1)
Insertion Position linked list.

From Delete a node from the

O (1) O (1)
Beginning start of a linked list

Delete a node at the end of

O (N) O (1)
From the End a linked list.

Delete a node from a

A Specific specific position of a O (N) O (1)
Deletion Node linked list.

Traverse the linked list

from start to end or vice O (N) O (1)
Traversal versa.
Some basic Operations in Doubly Linked List
1)Display forward − Displays the complete list in a forward manner.
2)Display backward − Displays the complete list in a backward manner.
NOTE:Extra Information (Not Included in Syllabus)
Algorithm for Insertion at Beginning (DLL)
Step 1: Start
Step 2: Create a new node
Step 3: Read value
Step 4: Store value in new node
Step 5: Set newNode → prev = NULL
Step 6: Set newNode → next = head
If head ≠ NULL
head → prev = newNode
Set head = newNode
Step 7: Stop
C++ Code
struct DNode{
int data;
DNode* prev;
DNode* next;
};
void insertAtBeginning(DNode* Chead, int value) {
DNode* newNode = new DNode();
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;
if (head) head->prev = newNode;
head = newNode;
}
Algorithm for Deletion at End.
(C++ Code)
void deleteAtEnd(DNode* Chead) {
if (!head) return;
if (!head->next) {
delete head;
head = NULL;
return;
}
DNode* temp = head;
while (temp->next)
temp = temp->next;
temp->prev->next = NULL;
delete temp;
}
Advantages of DLL(doubly linked List)
1)Bidirectional traversal: you can traverse forward (using next) as well as backward
(using prev). it enables flexibility over singly Linked list.
2)Efficient deletion: Give a pointer to a node, you can delete it in O(1) time (no need to
traverse from the head).Since you can update both prev and next.
3)Insertion at both ends:
Insertion at head or tail is efficient because you can update both directions easily.
4)Easy to implement deque / Navigation features: useful for undo /redo , browser history
and music playlist navigation, where both forward and backward movement is needed.

Disadvantages of DLL.
1)Extra memory per node: Each node requires an additional pointer (prev) making DLL
more memory consuming than SLL.
2)More Complex implementation: Both prev and next must be handled carefully during
insertion and deletion which increases chances of Errors (Broken Links , null pointer
Issues)
3)Slower operations due to overhead: Extra pointer manipulators during insertion /
deletion cause slightly more overhead compared to SLL.
4)Not Cache friendly: Like SLL, Nodes are scattered in memory, so traversals may be
slower compared to arrays, due to poor locality of reference [Nodes are scattered in
memory].

Applications of Doubly Linked Lists

A doubly linked list has two pointers: one pointing to the next node and another pointing to
the previous node. This bidirectional nature makes it suitable for applications requiring easy
forward and backwards traversal.

1. Undo/Redo Functionality
Many applications, such as text editors, graphic design tools, and IDEs, implement undo/redo
functionality using doubly linked [Link] action performed is stored as a node, allowing
users to move backwards (undo) or forward (redo) through their editing history.
2. Navigation Systems Requiring Bidirectional Traversal
Applications like web browsers (back and forward navigation) and file explorers use doubly
linked lists to navigate between previously visited and next items. This structure allows
seamless movement between pages or directories without requiring additional memory-
intensive operations.
3. Implementing LRU (Least Recently Used) Cache
LRU Cache is an efficient caching mechanism used in operating systems and database
management systems to manage frequently used data. A doubly linked list is used to store
cache elements, where the most recently used item is moved to the front, and the least
recently used item is removed from the end when the cache limit is reached.
4. Managing File Systems
File systems such as Linux's ext4 and Windows’ NTFS use doubly linked lists to maintain
file directories. Since files and folders are accessed frequently in both forward and backward
directions, doubly linked lists provide an efficient way to traverse and modify them.
5)Navigation Systems: Enable efficient forward and backward traversal, such as browser
history or playlist navigation.
6)Polynomial Arithmetic and sparse matrix representation: DLL can efficiently represent
terms or non Zero elements where both forward and backward traversal helps in calculations.
7)Dynamic Memory Management: Helps implement techniques like garbage collection.
8)Complex Data Structures: Used in implementing advanced structures like binary trees,
Fibonacci heaps, or LRU cache, adjacency lists of graphs where back traversal is useful.
9)Music/Video Playlists: Enable easy movement between previous and next items. Both
types of linked lists offer flexibility in memory allocation, making them suitable for
applications requiring dynamic memory management and non-contiguous memory use.
10)Implemention of dequeue: DLL males insertion and deletion efficient at both ends.
3. Circular Linked List in C++ [Not there in syllabus]
The circular linked list is almost same as the singly linked list but with a small change. In
a circular linked list the next pointer of the last node points to the first node of the linked
list rather than pointing to NULL, this makes this data structure circular in nature which is
used in various applications like media players. The following diagram describes the
structure of a circular linked list:

In CLL, is a variation of linked list where the last node points back to the first node forming
a circle. This structure allows for continuous traversal without a defined beginning or end.

Circular Linked List Representation : Circular linked list can be represented as pointer
to the first node where each node contains:
• Data: Actual information is stored.
• Next: Pointer to the next node and last node Next is pointed to the first node of the
linked list.
// Structure to represent the circular linked list
struct Node {
int data; // Data field - can be of any type and count
struct Node* next; // Pointer to the next node
};
Advantages of Linked List
• Inserting and deleting node is efficient because no need to shifting like in array.
• Linked lists have dynamic size, which allows them to grow or shrink during runtime.
• Memory is utilized more efficiently as linked lists do not require a pre-allocated size,
reducing wasted space.
• Efficient for those operations where we need large or frequently changing datasets.
• Linked list used non-contiguous memory blocks, so it is useful for those application
where memory is needed.
Disadvantages of Linked List
• Direct access to element is not possible in a linked list; it requires traversing from the
start to reach a specific position.
• Each node requires extra memory for storing a pointer.
• Linked lists are more complex to implement and manage.
• Pointers can lead to bugs, memory leaks, or segmentation fault.

Applications of Linked Lists

Linked lists play a crucial role in various fields of computer science and real-world
applications due to their flexibility and dynamic memory allocation. Here are the various
application of linked list in data structures:
1. Implementing Stacks and Queues
Linked lists are ideal for implementing stacks (LIFO - Last In, First Out) and queues (FIFO -
First In, First Out) since they allow efficient insertion and deletion without requiring a
predefined size, unlike arrays.
2. Graph Representation (Adjacency List)
Graphs often use adjacency lists, which are implemented using linked lists. This approach
saves memory compared to adjacency matrices, especially for sparse graphs where many
connections are absent.
3. Hash Tables (Chaining)
To resolve hash collisions, linked lists are used in separate chaining. Multiple elements with
the same hash key are stored in a linked list, reducing collision issues and ensuring efficient
retrieval.
4. Polynomial Manipulation
In polynomial arithmetic, each term is stored as a node in a linked list, with pointers
connecting terms in increasing or decreasing order of exponents. This allows for efficient
addition, subtraction, and differentiation of polynomials.
5. Dynamic Memory Allocation Operating Systems: Memory management uses linked
lists for heap allocation (free and allocated memory blocks).
6. Undo/Redo Functionality Text Editors & Software Applications: Maintain a history of
actions using a doubly linked list for undo and redo operations.
7. Web Browsers – Forward & Backward Navigation Doubly Linked List stores browsing
history, allowing users to move back and forward between pages.
8. Music & Video Playlists Circular Linked Lists are used in media players to loop through
songs or videos continuously.
9. CPU Scheduling (Operating Systems) Circular Linked Lists implement Round Robin
Scheduling, where processes are executed in a cyclic order.
10. File Systems Linked allocation in file systems stores file data across non-contiguous
blocks to minimize fragmentation.
11. Polynomial Arithmetic Linked Lists store and process polynomials efficiently for
mathematical computations.
12. Social Media & Recommendation Systems Graph-based models using linked lists
connect users, friends, or recommended products dynamically.
13. Network Packet Transmission Linked Lists store incoming and outgoing packets
efficiently in network routers.
14. Memory Management
Operating systems use linked lists for dynamic memory allocation, tracking free and
allocated memory blocks efficiently. For example, the buddy system for memory allocation
often relies on linked lists.
15. Image Viewers
Image viewers use doubly linked lists to facilitate next and previous navigation, enabling
smooth transitions between images in a gallery.
16. Operating Systems (Process Scheduling)
The round-robin scheduling algorithm in operating systems uses circular linked lists to
manage processes, ensuring that each process gets an equal time slice before moving to the
next. These applications of linked list highlight the versatility of linked lists in handling
dynamic data structures efficiently across different domains.

Difference Between Singly Linked List (SLL) and doubly Linked List(DLL)
Includes Some Features in SLL and DLL.

Features SLL DLL

Number of pointers One(next ) Two (prev, next)
Memory Usage Less Memory More Memory(extra
Memory)
Traversal Forward Forward and backward
Reverse traversal Not Possible directly Possible
Insertion at beginning Easy Easy
Deletion at end Need previous node tracking Easier (direct access using
prev)
Implementation Simple More Complex.
Searching Sequential O(n) Sequential O(n)
Extra space No extra pointer Requires extra pointer.