LAB MANUAL CS-216

(DATA STRUCTURES & ALGORITHMS)

SUBMIT TO: MS. RIMSHA RASHEED

SUBMITTTED BY: IRFAN ILYAS

SEMESTER N0: 3

REGISTRATION NO: 2024-BS-CYS-059

DEPARTMENT OF CYBER
SECURITY
LAB TAK 1: Basic Programming Practices
Part 1: Operators
1. Write a program to take two numbers as input and display:
2. Sum, difference, product, division, modulus
3. Compare which number is greater/smaller
4. Check if both numbers are even using logical operators
Answer:
#include

<iostream> using

namespace std;

int main() {
int a, b;
cout << "Enter two

numbers: "; cin >> a >>

b;

cout << "Sum: " << a + b << endl;

cout << "Difference: " << a - b <<

endl; cout << "Product: " << a *

b << endl;

if (b != 0) {
cout << "Division: " << (float)a / b
 << endl; cout << "Modulus: " <<

a % b << endl;

} else {
cout << "Cannot divide by zero." << endl;
}

if (a > b)
 cout << a << " is greater than " << b

<< endl; else if (a < b)

cout << b << " is greater than " << a

<< endl; else

cout << "Both numbers are equal." << endl;

if (a % 2 == 0 CC b % 2 == 0)
cout << "Both numbers are even."

<< endl; else

cout << "Both numbers are not even." <<

endl; return 0;

}
OUTPUT:
Part 2: Loops:
1. Write a program using for loop to print multiplication table of a given
number.
Answer:
#include

<iostream> using

namespace std;

int main()

{ int

num;

cout << "Enter a

number: "; cin >>

num;

for (int i = 1; i <= 10; ++i) {

cout << num << " x " << i << " = " << num * i << endl;
}

return 0;
OUPUT:
 2. }Write a program using while loop to calculate factorial of a number.
Answer:
#include<iostrea

m> using

namespace std;

int main(){

int n , fact=1 , i=1;

cout<<"Enter number:

";cin>>n; while (i<=n){

fact = fact * i;

i++;

}
cout<<"Factorial:

"<<fact<<endl; return 0;

}
OUPUT:
 3. Write a program using do-while loop to repeatedly ask user for a
number until they enter 0.
Answer:
#include

<iostream> using

namespace std;

int

main()

{ int

num;

do {

cout << "Enter a number (0 to

stop): "; cin >> num;

} while (num != 0);

cout << "Program terminated."

<< endl; return 0;

}
OUPUT:
Part 3: Functions

1. Write a function to check if a number is prime.

Answer:
#include

<iostream> using

namespace std;

void

checkPrime(int n)

{ int cnt = 0;

if (n <= 1) {
cout << n << " is NOT

prime"; return;

for (int i = 1; i <= n;

i++) { if (n % i

== 0)

cnt++;
}
 if (cnt == 2)
cout << n << " is

prime"; else

cout << n << " is NOT prime";

}
int main()

{ int

num;

cout << "Enter

number: "; cin >>

num;

checkPrime(num);

return 0;
}

OUPUT:
 2. Write a function that takes a number and returns its factorial.
Answer:
#include<iostrea

m> using

namespace std;
void

findFact(){ int

n , fact=1 , i=1;

cout<<"Enter number:

";cin>>n; while (i<=n){

fact = fact * i;

i++;

}
cout<<"Factorial: "<<fact<<endl;
};
int

main(){

findFact(

); return

0;

}
OUPUT:
 3. Write a function that takes two numbers and returns the greater number.
Answer:

#include

<iostream> using

namespace std;

int greatestNumber(int a, int

b) { if (a > b) {

return a;
} else {

return

b;}

}
int main()

{ int x,

y;

cout << "Enter first

number: "; cin >> x;

cout << "Enter second

number: "; cin >> y;

int result = greatestNumber(x, y);

cout << "The greater number is: " << result << endl;
 return 0;
}
OUPUT:
LAB TASK 2:
Implementation of 1D and 2D Arrays and Operations of Arrays
Task 1: Temperature Analysis
Write a C++ program to store the temperature of each day in a week (7 days)
in a 1D array and:
• Display all temperatures.
• Find and print the hottest and coldest days.
• Calculate the average temperature of the week.
Answer:
#include

<iostream> using

namespace std;

int main() {
const int days = 7;
double temperatures[days];
double sum = 0.0,

average; double

hottest, coldest; for

(int i = 0; i < days;

i++) {

cout << "Enter temperature for day " << (i +

1) << ": "; cin >> temperatures[i];

sum += temperatures[i];
}
cout << "Temperatures for the

week: "; for (int i = 0; i < days;

i++) {
cout << temperatures[i] << " "<< endl;
}
hottest = coldest =

temperatures[0]; for (int i = 1; i

< days; i++) {

if (temperatures[i] >

hottest) { hottest =

temperatures[i];

}
if (temperatures[i] < coldest)
 { coldest =

temperatures[i];

}
}
average = sum / days;

cout << "Hottest day temperature: " << hottest

<< endl; cout << "Coldest day temperature: "

<< coldest << endl;

cout << "Average temperature of the week: " << average << endl;
 return 0;
}

Task 2: Frequency Counter

Write a C++ program that:

• Takes 10 integers as input in a 1D array.

• Counts and prints how many times each number occurs in the array.
Answer:
#include

<iostream> using

namespace std;

int main() {
int arr[10], i, j, count;
cout << "Enter 10

numbers:\n"; for (i = 0; i

< 10; i++)

 cin >> arr[i];

cout <<

"\nFrequencies:\n"; for

(i = 0; i < 10; i++) {

count = 1;
if (arr[i] != -1) {
for (j = i + 1; j < 10;

j++) { if (arr[i] ==

arr[j]) {

count++;

arr[j] = -1;

}
}
cout << arr[i] << " occurs " << count << " time(s)\n";
}
}
return 0;
}
Task 3: Reverse an

Array Write a C++

program to:

• Input 8 integers in an array.

• Display them in the reverse order without using another array.
Answer:
#include

<iostream> using

namespace std;

int

main()

{ int

arr[8];

cout << "Enter 8

integers: "; for (int i =

0; i < 8; i++) {
 cin >> arr[i];
}

cout << "Reversed

order: "; for (int i = 7;

i >= 0; i--) {

cout << arr[i] << " ";

}

return 0;
}

Task 4: Find Even and Odd numbers

Write a C++ program to store N integers in a 1D array. Separate and print all
even numbers and odd numbers from the array.
Answer:
#include

<iostream> using

namespace std;

int main()

{ int N;

cout << "Enter the number of

integers: "; cin >> N;

int arr[N];
cout << "Enter " << N << " integers: ";
for (int i = 0; i < N;

i++) { cin >>

arr[i];

cout << "Even

numbers: "; for (int i

= 0; i < N; i++) {

if (arr[i] % 2 ==

0) { cout <<

arr[i] << " ";

}
}

cout << "\nOdd

numbers: "; for (int i =

0; i < N; i++) {

if (arr[i] % 2 !=

0) { cout <<

arr[i] << " ";

}
}
 return 0;
}
 Lab 03
2D Arrays
Traversal→ visiting each element.
Insertion→ Adding a new element.
Deletion→ Removing a new element.
Searching→ Finding an element.
Sorting→ Arranging Elements.
Algorithm:
A step-by-step procedure to solve a problem in a finite amount of time.
Example:
Adding 2 numbers
Complexity Analysis
Time Complexity
How much time an algorithm takes as input size grows.
Expressed as number of steps, not actual seconds.
Space Complexity
How much memory an algorithm uses.
1. Linear Time Complexity – O(n)
An algorithm has linear time complexity if the time it takes increases
directly in proportion to the input size.
If input doubles → the number of steps also doubles.
sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
2. Quadratic Time Complexity – O(n²)
An algorithm has quadratic time complexity if the time taken is
proportional to the square of the input size.
If input doubles → the number of steps becomes four times.
Bubble sort:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Some operation
}
}
Traversal:
#include<iostream>
using namespace std;
int main(){
int arr[2][3]={{1,2,3},{4,5,6}};
for(int i=0;i<2;i++){
for(int j=0;j<3;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
return 0;
}
Lab 03
2D Arrays
Traversal→ visiting each element.
Insertion→ Adding a new element.
Deletion→ Removing a new element.
Searching→ Finding an element.
Sorting→ Arranging Elements.
Algorithm:
A step-by-step procedure to solve a problem in a finite amount of time.
Example:
Adding 2 numbers
Complexity Analysis
Time Complexity
How much time an algorithm takes as input size grows.
Expressed as number of steps, not actual seconds.
Space Complexity
How much memory an algorithm uses.
2. Linear Time Complexity – O(n)
An algorithm has linear time complexity if the time it takes increases
directly in proportion to the input size.
If input doubles → the number of steps also doubles.
sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
2. Quadratic Time Complexity – O(n²)
An algorithm has quadratic time complexity if the time taken is
proportional to the square of the input size.
If input doubles → the number of steps becomes four times.
Bubble sort:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Some operation
}
}
Traversal:
#include<iostream>
using namespace std;
int main(){
int arr[2][3]={{1,2,3},{4,5,6}};
for(int i=0;i<2;i++){
for(int j=0;j<3;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
 return 0;
}

Output

Insertion:
#include<iostream>
using namespace std;
int main(){
int arr[2][3]={{1,2,3},{4,5,6}};
int r,c,v;
cout<<"Enter the row coulome and value";
cin>>r>>c>>v;
arr[r][c]=v;
for(int i=0;i<2;i++){
for(int j=0;j<3;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
return 0;
}

Output

Deleting
#include<iostream>
using namespace std;
int main(){
int arr[2][3]={{1,2,3},{4,5,6}},r,c;
cin>>r>>c;
arr[r][c]=0;
for(int i=0;i<2;i++){
for(int j=0;j<3;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
 }
return 0;
}

Output

Searching
#include<iostream>
using namespace std;
int main(){
int arr[2][3]={{1,2,3},{4,5,6}};
int x;
int f=0;

cout<<"Enter element for search: ";

cin>>x;
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
if(arr[i][j]==x){
cout<<"Found in Row "<<i<<" Column "<<j;
f=1;
}
}
}
if(f==0)
cout<<"Not Found";
return 0;
}

Output:

Sorting
#include<iostream>
using namespace std;
int main(){
 int arr[2][3]={{5,2,8},{1,7,3}};
int temp;
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
for(int k=0;k<2;k++){
for(int l=0;l<3;l++){
if(arr[i][j]<arr[k][l]){
temp=arr[i][j];
arr[i][j]=arr[k][l];
arr[k][l]=temp;
}
}
}
}
}

cout<<"Sorted Array ";

for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}

Output

1- Write a C++ program to find the maximum element in a 2D array.

• Requirements:
➢ Take rows & columns from the user.
➢ Input elements.
➢ Print the largest element.
#include<iostream>
using namespace std;
int main(){
int r,c;
cout<<"Enter rows: ";
cin>>r;
cout<<"Enter columns: ";
cin>>c;
int arr[50][50]; // max size 50x50
cout<<"Enter elements:\n";
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin>>arr[i][j];
}
}
int max=arr[0][0]; // assume first element is max
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(arr[i][j]>max){
max=arr[i][j];
}
}
}
cout<<"Largest element: "<<max;
return 0;
}

Output
2- Write a C++ program to count the number of even and odd elements in a
2D array.
Requirements:
Take rows & columns from the user.
Input elements into a 2D array.
Count how many even and odd numbers are there.
Print the counts.
#include<iostream>
using namespace std;
int main(){
int r,c;
cout<<"Enter rows: ";
cin>>r;
cout<<"Enter columns: ";
cin>>c;
int arr[50][50];
cout<<"Enter elements:\n";
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin>>arr[i][j];
}
}
int even=0,odd=0;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(arr[i][j]%2==0)
even++;
else
odd++;
}
}
cout<<"Even count: "<<even<<endl;
cout<<"Odd count: "<<odd<<endl;
return 0;
}

Output
 Lab 04
Implementation of Single linked list & operations
Singly linked list :
A singly linked list is the simplest kind of linked lists.
It takes up less space in memory because each node has only one address to
the next node, like in the image below.
Applications of Arrays in Real Life:
1. Music & Video Playlists
Benefit:
➢ Easy to move to the next or previous song/video.
➢ Songs can be added or removed without shifting all others like
in arrays.
2. Undo/Redo Operations in Text Editors
Example: In MS Word or Notepad, each action is stored in a linked list of
states.
Benefit:
➢ Pressing Ctrl+Z moves to the previous state (undo).
➢ Pressing Ctrl+Y moves forward (redo).
Operations performed on arrays :
Basic Structure + display→ display list.
Insertion → Adding a new element.
Deletion→ Removing a new element.
Searching→ Finding an element.
Reversing→ Reverse Elements.
Basic Structure & Traversal
#include<iostream>
using namespace std;

struct Node{
int data;
Node* next;
};
int main(){
 Node* head=nullptr;
Node* first=nullptr;
Node* second=nullptr;
Node* third=nullptr;
head=new Node();
first=new Node();
second=new Node();
third=new Node();
head->data=5;
head->next=first;
first->data=10;
first->next=second;
second->data=15;
second->next=third;
third->data=20;
third->next=nullptr;
Node* a=head;
while(a!=nullptr){
cout<<a->data<<endl;
a=a->next;
}
return 0;
}

Output:

Insertion at the End:

#include <iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int value){
data=value;
next=nullptr;
 }
};
class Linkedlist{
private:
Node* head;
public:
Linkedlist(){
head=nullptr;
}
void insertion(int value){
Node* newnode=new Node(value);
if(head==nullptr){
head=newnode;
return;
}
Node* temp=head;
while(temp->next!=nullptr){
temp=temp->next;
}
temp->next=newnode;
}
void display(){
Node* temp=head;
while(temp!=nullptr){
cout<<temp->data<<endl;
temp=temp->next;
}
cout << endl;
}
};
int main() {
Linkedlist list;
[Link](10);
[Link](20);
[Link](30);
[Link](40);
cout<<"Linked list is: ";
[Link]();
 return 0;
}
Output:

Insertion at the Beginning:

#include <iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int value){
data=value;
next=nullptr;
}
};
class Linkedlist{
private:
Node* head;
public:
Linkedlist() {
head=nullptr;
}
void insertbeg(int value) {
Node* newnode=new Node(value);
newnode->next=head;
head=newnode;
}
void display(){
Node* temp=head;
while(temp!=nullptr){
cout<<temp->data <<endl;
temp=temp->next;
}
}
};
int main() {
Linkedlist list;
[Link](10);
 [Link](20);
[Link](30);
cout<<"Linked list is : ";
[Link]();
return 0;
}

Output

Insertion at the Position:

#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int value){
data=value;
next=nullptr;
}
};
class Linkedlist{
private:
Node* head;
public:
Linkedlist(){
head = nullptr;
}
void insertend(int value){
Node* newnode=new Node(value);
if(head==nullptr){
head=newnode;
return;
}
Node* temp=head;
while(temp->next!=nullptr){
temp=temp->next;
 }
temp->next=newnode;
}
void insertposition(int value, int pos){
Node* newnode=new Node(value);
if(pos==1){
newnode->next=head;
head=newnode;
return;
}
Node* temp=head;
for(int i=1; i<pos-1 && temp!=nullptr; i++){
temp=temp->next;
}
if(temp==nullptr){
cout<<"Position not in range position at the end: "<<endl;
delete newnode;
return;
}
newnode->next=temp->next;
temp->next=newnode;
}
void display(){
Node* temp=head;
while(temp!=nullptr){
cout<<temp->data<<endl;
temp=temp->next;
}
}
};
int main(){
Linkedlist list;
[Link](10);
[Link](20);
[Link](40);
cout << "Link list is : ";
[Link]();
[Link](30, 3);
 [Link](5, 1);
[Link](50, 10);
cout << "Update list: ";
[Link]();
return 0;
}

Output:

LAB TASK 5: Stack Implementation using Arrays

 Display
ANSWER:
#include<iostream>
using namespace std;

#define MAX 5

class Stack {
int arr[MAX];
int top;

public:
Stack() {
top = -1;
}

void display() {
if (top < 0) {
cout << "Stack is empty!" << endl;
} else {
cout << "Stack elements are: ";
for (int i = top; i >= 0; i--) {
cout << arr[i] << " ";
}
cout << endl;
 }
}
};

int main() {
Stack s;
[Link]();
return 0;
}
 Insertion
ANSWER:
#include<iostream>
using namespace std;

#define MAX 5

class Stack {
int arr[MAX];
int top;

public:
Stack() {
top = -1;
}
void insertion(int value) {
if (top >= MAX - 1) {
cout << "Stack Overflow! Cannot push " << value << endl;
} else {
arr[++top] = value;
cout << value << " pushed into stack.\n";
}
}
void display() {
if (top < 0) {
cout << "Stack is empty!\n";
} else {
cout << "Stack elements are: ";
for (int i = top; i >= 0; i--) {
 cout << arr[i] << " ";
}
cout << endl;
}
}
};

int main() {
Stack s;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);
[Link](60);
[Link]();

return 0;
}

 Deletion
ANSWER:
#include <iostream>
using namespace std;

#define MAX 5

class Stack {
int arr[MAX];
int top;

public:
Stack() {
top = -1;
}
 void insertion(int value) {
if (top >= MAX - 1) {
cout << "Stack overflow! Cannot push " << value << endl;
} else {
arr[++top] = value;
cout << value << " pushed into stack." << endl;
}
}

void deletion() {
if (top < 0) {
cout << "Stack underflow! Cannot pop." << endl;
} else {
cout << arr[top--] << " popped from stack." << endl;
}
}

void display() {
if (top < 0) {
cout << "Stack is empty." << endl;
} else {
cout << "Stack elements are:" << endl;
for (int i = top; i >= 0; i--) {
cout << arr[i] << endl;
}
}
}
};
int main() {
Stack s;
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link]();
return 0;
}
  Searching
ANSWER:
#include <iostream>
using namespace std;

#define MAX 5

class Stack {
int arr[MAX];
int top;

public:
Stack() {
top = -1;
}

void insertion(int value) {

if (top >= MAX - 1) {
cout << "Stack overflow! Cannot push " << value << endl;
} else {
arr[++top] = value;
cout << value << " pushed into stack." << endl;
}
}

void deletion() {
if (top < 0) {
cout << "Stack underflow! Cannot pop." << endl;
} else {
cout << arr[top--] << " popped from stack." << endl;
}
}
void searching(int value)
{
if (top < 0)
{
cout << "Stack is empty." << endl;
return;
 }
bool found = false;
for (int i = top; i >= 0; i--)
{
if (arr[i] == value)
{
cout << "Element " << value << " found at position "
<< (top - i + 1) << " from top." << endl;
found = true;
break;
}
}
if (!found){
cout << "Element " << value << " not found in stack." << endl;
}
}

void display() {
if (top < 0) {
cout << "Stack is empty." << endl;
} else {
cout << "Stack elements are:" << endl;
for (int i = top; i >= 0; i--) {
cout << arr[i] << endl;
}
}
}
};
int main() {
Stack s;
[Link](10);
[Link](20);
[Link](30);
[Link](20);
[Link]();
[Link]();
return 0;
}

 Sorting
ANSWER:
#include <iostream>
using namespace std;

#define MAX 5

class Stack {
int arr[MAX];
int top;

public:
Stack() {
top = -1;
}

void insertion(int value) {

if (top >= MAX - 1) {
cout << "Stack overflow! Cannot push " << value << endl;
} else {
arr[++top] = value;
cout << value << " pushed into stack." << endl;
}
}

void deletion() {
if (top < 0) {
cout << "Stack underflow! Cannot pop." << endl;
} else {
cout << arr[top--] << " popped from stack." << endl;
}
}
void sortStack()
{
if (top < 0)
 {
cout << "Stack is empty. Nothing to sort." << endl;
return;
}
for (int i = 0; i <= top; i++)
{
for (int j = 0; j < top - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

cout << "Stack sorted in ascending order." << endl;

for (int i = top; i >= 0; i--)
cout << arr[i] << " ";
}

void display() {
if (top < 0) {
cout << "Stack is empty." << endl;
} else {
cout << "Stack elements are:" << endl;
for (int i = top; i >= 0; i--) {
cout << arr[i] << endl;
}
}
}
};
int main() {
Stack s;
[Link](10);
[Link](20);
 [Link](30);
[Link]();
[Link]();
return 0;
}
LAB TASK 6: Linear Queue and Circular Queue Implementation
using Arrays
CLASSWORK:
Queue Operations:
1. Display
ANSWER:
#include<iostream>
using namespace std;
#define SIZE 5
class LinearQueue{
int front ; int end; int arr[SIZE];
public:
LinearQueue(){
front = -1; end = -1;
}

void display(){
if (front ==-1 || front >end){
cout<<"Queue is empty "<<endl;
}
else{
cout<<"Queue elements are: "<<endl;
for(int i = front; i<=end;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
};

int main(){
LinearQueue que;
[Link]();
return 0;
}
2. Insertion
ANSWER:
#include<iostream>
using namespace std;
#define SIZE 5
class LinearQueue{
int front ; int end; int arr[SIZE];
public:
LinearQueue(){
front = -1; end = -1;
}
void insertion(int val)
{
if (end == SIZE - 1)
{
cout << "queue overflow" << endl;
}
else
{
if (front == -1)
{
front = 0;
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
else
{
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
}
}
void display(){
if (front ==-1 || front >end){
cout<<"Queue is empty "<<endl;
}
else{
cout<<"Queue elements are: "<<endl;
for(int i = front; i<=end;i++){
cout<<arr[i]<<" ";
 }
cout<<endl;
}
}
};

int main(){
LinearQueue que;
[Link](70);
[Link](20);
[Link](40);
[Link](50);
[Link]();
return 0;
}

3. Deletion
ANSWER:
#include<iostream>
using namespace std;
#define SIZE 5
class LinearQueue{
int front ; int end; int arr[SIZE];
public:
LinearQueue(){
front = -1; end = -1;
}
void insertion(int val)
{
if (end == SIZE - 1)
{
cout << "queue overflow" << endl;
}
else
{
if (front == -1)
{
 front = 0;
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
else
{
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
}
}
void deletion()
{
if (front == -1 || front > end)
{
cout << "queue underflow" << endl;
}
else
{
int del = arr[front++];
cout << del << " is deleted successfully" << endl;
}
}

void display(){
if (front ==-1 || front >end){
cout<<"Queue is empty "<<endl;
}
else{
cout<<"Queue elements are: "<<endl;
for(int i = front; i<=end;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
};
int main()
{
LinearQueue que;
[Link](70);
[Link](20);
[Link](40);
[Link](50);
[Link]();
[Link]();
[Link]();
return 0;
}
4. Searching
ANSWER:
#include<iostream>
using namespace std;
#define SIZE 5
class LinearQueue{
int front ; int end; int arr[SIZE];
public:
LinearQueue(){
front = -1; end = -1;
}
void insertion(int val)
{
if (end == SIZE - 1)
{
cout << "queue overflow" << endl;
}
else
{
if (front == -1)
{
front = 0;
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
else
 {
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
}
}
void deletion()
{
if (front == -1 || front > end)
{
cout << "queue underflow" << endl;
}
else
{
int del = arr[front++];
cout << del << " is deleted successfully" << endl;
}
}
void searching(int val)
{
for (int i = front; i <= end; i++)
{
if (arr[i] == val)
{
cout << val << " found at position " << i - front + 1 << endl;
return;
}
}

cout << val << " not found" << endl;

}

void display(){
if (front ==-1 || front >end){
cout<<"Queue is empty "<<endl;
}
else{
cout<<"Queue elements are: "<<endl;
 for(int i = front; i<=end;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
};
int main()
{
LinearQueue que;
[Link](70);
[Link](20);
[Link](40);
[Link](50);
[Link]();
[Link]();
[Link]();
[Link](20);
return 0;
}
5. Sorting
ANSWER:
#include<iostream>
using namespace std;
#define SIZE 5
class LinearQueue{
int front ; int end; int arr[SIZE];
public:
LinearQueue(){
front = -1; end = -1;
}
void insertion(int val)
{
if (end == SIZE - 1)
{
cout << "queue overflow" << endl;
}
 else
{
if (front == -1)
{
front = 0;
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
else
{
arr[++end] = val;
cout << val << " inserted in queue successfully" << endl;
}
}
}
void sorting()
{
if (front == -1 || front > end)
{
cout << "Queue is empty. Nothing to sort." << endl;
return;
}

for (int i = front; i <= end - 1; i++)

for (int j = i + 1; j <= end; j++)
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

cout << "sorted successfully" << endl;

for (int i = front; i <= end; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
 void display(){
if (front ==-1 || front >end){
cout<<"Queue is empty "<<endl;
}
else{
cout<<"Queue elements are: "<<endl;
for(int i = front; i<=end;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
};

int main(){
LinearQueue que;
[Link](70);
[Link](20);
[Link](40);
[Link](50);
[Link]();
[Link]();
return 0;
}
6. Display in Circular Queue:
ANSWER:
#include <iostream>
using namespace std;
#define SIZE 5
class Circularqueue{
int front;
int end;
int arr[SIZE];
public:
Circularqueue() {
front = -1;
end = -1;
}
 void display(){
if (front == -1)
cout << "Queue is empty" << endl;
else{
cout << "Queue elements: " << endl;
int i = front;
while (true){
cout << arr[i] << " ";
if (i == end)
break;
i = (i + 1) % SIZE;
}
cout << endl;
}
}
};

int main(){
Circularqueue que;
[Link]();
return 0;
}

7. Insertion in Circular Queue:

ANSWER:
#include <iostream>
using namespace std;
#define SIZE 5
class Circularqueue{
int front;
int end;
int arr[SIZE];
public:
Circularqueue() {
front = -1;
end = -1;
}
 void insertion(int value)
{
if ((end + 1) % SIZE == front)
cout << "Queue Overflow!\n";
else
{
if (front == -1)
front = 0;
end = (end + 1) % SIZE;
arr[end] = value;
cout << value << " inserted Successfully" << endl;
}
}

void display(){
if (front == -1)
cout << "Queue is empty" << endl;
else{
cout << "Queue elements: " << endl;
int i = front;
while (true){
cout << arr[i] << " ";
if (i == end)
break;
i = (i + 1) % SIZE;
}
cout << endl;
}
}
};

int main(){
Circularqueue que;
[Link]();
[Link](40);
[Link](50);
[Link](10);
[Link](60);
 [Link](80);
[Link]();

return 0;
}

8. Deletion in Circular Queue:

ANSWER:
#include <iostream>
using namespace std;
#define SIZE 5
class Circularqueue{
int front;
int end;
int arr[SIZE];
public:
Circularqueue() {
front = -1;
end = -1;
}
void insertion(int value)
{
if ((end + 1) % SIZE == front)
cout << "Queue Overflow!\n";
else
{
if (front == -1)
front = 0;
end = (end + 1) % SIZE;
arr[end] = value;
cout << value << " inserted Successfully" << endl;
}
}

void deletion()
{
if (front == -1)
cout << "Queue Underflow" << endl;
 else
{
cout << arr[front] << " deleted" << endl;
if (front == end)
front = end = -1;
else
front = (front + 1) % SIZE;
}
}

void display(){
if (front == -1)
cout << "Queue is empty" << endl;
else{
cout << "Queue elements: " << endl;
int i = front;
while (true){
cout << arr[i] << " ";
if (i == end)
break;
i = (i + 1) % SIZE;
}
cout << endl;
}
}
};

int main(){
Circularqueue que;
[Link]();
[Link](40);
[Link](50);
[Link](10);
[Link](60);
[Link](80);
[Link]();
[Link]();
[Link]();
 return 0;
}

Home Tasks:
1. Add a search() function that checks whether a given element
exists in the circular queue.
ANSWER:
#include <iostream>
using namespace std;

class CircularQueue {
private:
int *arr;
int front, rear, capacity, currentSize;

public:
CircularQueue(int size) {
capacity = size;
arr = new int[capacity];
front = 0;
rear = -1;
currentSize = 0;
}

bool isFull() { return currentSize == capacity; }

bool isEmpty() { return currentSize == 0; }

void enqueue(int value) {

if (isFull()) {
cout << "Queue Overflow\n";
return;
}
rear = (rear + 1) % capacity;
arr[rear] = value;
currentSize++;
}
void dequeue() {
 if (isEmpty()) {
cout << "Queue Underflow\n";
return;
}
front = (front + 1) % capacity;
currentSize--;
}
bool search(int target) {
if (isEmpty()) return false;

int index = front;

for (int i = 0; i < currentSize; i++) {
if (arr[index] == target) {
return true;
}
index = (index + 1) % capacity;
}
return false;
}

void display() {
if (isEmpty()) return;
int index = front;
cout << "Queue: ";
for (int i = 0; i < currentSize; i++) {
cout << arr[index] << " ";
index = (index + 1) % capacity;
}
cout << endl;
}
};

int main() {
CircularQueue q(5);

[Link](10);
[Link](20);
[Link](30);
 [Link](40);

[Link]();

int key = 30;

if ([Link](key)) {
cout << "Element " << key << " found in the queue.\n";
} else {
cout << "Element " << key << " not found.\n";
}
[Link]();
[Link](50);
[Link](60);

[Link]();

key = 60;
if ([Link](key)) {
cout << "Element " << key << " found in the queue.\n";
}

return 0;
}
2. Add a sortQueue() function that sorts the circular queue in
ascending order.
ANSWER:

#include <iostream>
using namespace std;

class CircularQueue {
private:
int *arr;
int front, rear, capacity, currentSize;

public:
CircularQueue(int size) {
capacity = size;
 arr = new int[capacity];
front = 0;
rear = -1;
currentSize = 0;
}
~CircularQueue() {
delete[] arr;
}

bool isFull() { return currentSize == capacity; }

bool isEmpty() { return currentSize == 0; }

void enqueue(int value) {

if (isFull()) {
cout << "Queue is Full!\n";
return;
}
rear = (rear + 1) % capacity;
arr[rear] = value;
currentSize++;
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is Empty!\n";
return;
}
front = (front + 1) % capacity;
currentSize--;
}
bool search(int target) {
if (isEmpty()) return false;

int index = front;

for (int i = 0; i < currentSize; i++) {
if (arr[index] == target) return true;
index = (index + 1) % capacity;
}
return false;
 }
void sortQueue() {
if (currentSize < 2) return;
for (int i = 0; i < currentSize - 1; i++) {
for (int j = 0; j < currentSize - i - 1; j++) {
int currIdx = (front + j) % capacity;
int nextIdx = (front + j + 1) % capacity;

if (arr[currIdx] > arr[nextIdx]) {

int temp = arr[currIdx];
arr[currIdx] = arr[nextIdx];
arr[nextIdx] = temp;
}
}
}
cout << "Queue sorted successfully.\n";
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
int index = front;
cout << "Queue elements: ";
for (int i = 0; i < currentSize; i++) {
cout << arr[index] << " ";
index = (index + 1) % capacity;
}
cout << endl;
}
};

int main() {
int size = 5;
CircularQueue cq(size);
[Link](45);
[Link](12);
[Link](78);
 [Link](3);
[Link](25);

[Link]();

int val = 78;

if ([Link](val))
cout << "Found " << val << " in the queue." << endl;
else
cout << val << " not found." << endl;

[Link]();
[Link]();

if ([Link](3))
cout << "Found 3 in the queue." << endl;

return 0;
}

LAB TASK 7: Priority Queue and Double + Circular Linked list

implementation
➢ Display
ANSWER:
#include <iostream>
using namespace std;
#define size 5

class PriorityQueue{
int arr[size];
int priority[size];
int count;
public:
PriorityQueue(){
count = 0;
}
void display()
{
if (count == 0){
cout << "queue is empty" << endl;
}
else{
cout << "Elements\tPriority\n";
for (int i = 0; i < count; i++){
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
}
};

int main(){
PriorityQueue pp;
[Link]();
return 0;
}
➢ Insertion
ANSWER:
#include <iostream>
using namespace std;
#define size 5

class PriorityQueue{
int arr[size];
int priority[size];
int count;
public:
PriorityQueue(){
count = 0;
}

//Insertion
void insertion(int val, int p)
{
 if (count == size)
{
cout << "Overflow occure" << endl;
return;
}
else
{
arr[count] = val;
priority[count] = p;
count++;
cout << val << " inserted with priority " << p << endl;
}
}
void display()
{
if (count == 0){
cout << "queue is empty" << endl;
}
else{
cout << "Elements\tPriority\n";
for (int i = 0; i < count; i++){
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
}
};

int main(){
PriorityQueue pp;
[Link]();
[Link](10,1);
[Link](40,4);
[Link](30,5);
[Link](20,2);
[Link](60,3);
}

➢ Deletion
ANSWER:
#include <iostream>
using namespace std;
#define size 5

class PriorityQueue{
int arr[size];
int priority[size];
int count;
public:
PriorityQueue(){
count = 0;
}

//Inserion
void insertion(int val, int p)
{
if (count == size)
{
cout << "Overflow occure" << endl;
return;
}
else
{
arr[count] = val;
priority[count] = p;
count++;
cout << val << " inserted with priority " << p << endl;
}
}
// deletion
void deletion()
{
if (count == 0)
{
cout << "under occure" << endl;
return;
}
 cout << arr[0] << " deleted from " << priority[0] << endl;

for (int i = 0; i < count - 1; i++)

{
arr[i] = arr[i + 1];
priority[i] = priority[i + 1];
}
count--;
}
void display()
{
if (count == 0){
cout << "queue is empty" << endl;
}
else{
cout << "Elements\tPriority\n";
for (int i = 0; i < count; i++){
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
}
};

int main(){
PriorityQueue pp;
[Link]();
[Link](10,1);
[Link](40,4);
[Link](30,5);
[Link](20,2);
[Link](60,3);
[Link]();
[Link]();
return 0;
}
➢ Searching
ANSWER:
#include <iostream>
using namespace std;
#define size 5

class PriorityQueue{
int arr[size];
int priority[size];
int count;
public:
PriorityQueue(){
count = 0;
}

//Inserion
void insertion(int val, int p)
{
if (count == size)
{
cout << "Overflow occure" << endl;
return;
}
else
{
arr[count] = val;
priority[count] = p;
count++;
cout << val << " inserted with priority " << p << endl;
}
}
// deletion
void deletion()
{
if (count == 0)
{
cout << "under occure" << endl;
return;
}
cout << arr[0] << " deleted from " << priority[0] << endl;
 for (int i = 0; i < count - 1; i++)
{
arr[i] = arr[i + 1];
priority[i] = priority[i + 1];
}
count--;
}
// searching
void searching(int val){
bool found=false;
for(int i=0;i<count;i++){
if(arr[i]==val){
cout<<val<<" with priority "<<priority[i]<<" found at position
"<<i+1<<endl;
found=true;
return;
}
}
if(!found){
cout<<" value not found"<<endl;
}
}
void display()
{
if (count == 0){
cout << "queue is empty" << endl;
}
else{
cout << "Elements\tPriority\n";
for (int i = 0; i < count; i++){
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
}
};
int main(){
PriorityQueue pp;
[Link]();
[Link](10,1);
[Link](40,4);
[Link](30,5);
[Link](20,2);
[Link](60,3);
[Link]();
[Link]();
[Link](30);
return 0;
}
➢ Sorting
ANSWER:
#include <iostream>
using namespace std;
#define size 5

class PriorityQueue{
int arr[size];
int priority[size];
int count;
public:
PriorityQueue(){
count = 0;
}

//Inserion
void insertion(int val, int p)
{
if (count == size)
{
cout << "Overflow occure" << endl;
return;
}
else
{
 arr[count] = val;
priority[count] = p;
count++;
cout << val << " inserted with priority " << p << endl;
}
}
// deletion
void deletion()
{
if (count == 0)
{
cout << "under occure" << endl;
return;
}
cout << arr[0] << " deleted from " << priority[0] << endl;

for (int i = 0; i < count - 1; i++)

{
arr[i] = arr[i + 1];
priority[i] = priority[i + 1];
}
count--;
}
// sorting
void sorting()
{
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
if (priority[i] > priority[j])
{
// swap priority
int tempP = priority[i];
priority[i] = priority[j];
priority[j] = tempP;

// swap data
 int tempD = arr[i];
arr[i] = arr[j];
arr[j] = tempD;
}
}
}

cout << "Queue sorted successfully.\n";

cout << "Value\tPriority\n";
for (int i = 0; i < count; i++)
{
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
void display()
{
if (count == 0){
cout << "queue is empty" << endl;
}
else{
cout << "Elements\tPriority\n";
for (int i = 0; i < count; i++){
cout << arr[i] << "\t\t" << priority[i] << endl;
}
}
}
};

int main(){
PriorityQueue pp;
[Link]();
[Link](10,1);
[Link](40,4);
[Link](30,5);
[Link](20,2);
[Link](60,3);
[Link]();
 [Link]();
[Link]();
return 0;
}
1) Display double linkedlist:
ANSWER:
#include <iostream>
using namespace std;
class Node {
public:
int data;
int priority;
Node* prev;
Node* next;

Node(int val, int p = 0) {

data = val;
priority = p;
prev = nullptr;
next = nullptr;
}
};
class DoublyLinkedList {
Node* head;
int count;

public:
DoublyLinkedList() {
head = nullptr;
count = 0;
}

// Function to insert node at end

void insertAtEnd(int val, int p = 0) {
Node* newNode = new Node(val, p);
if (head == nullptr) {
head = newNode;
count++;
 return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
count++;
}

void searching(int val) {

bool found = false;
Node* temp = head;
for (int i = 0; i < count; i++) {
if (temp->data == val) {
cout << val << " with priority " << temp->priority << " found at
position " << i + 1 << endl;
found = true;
return;
}
temp = temp->next;
}
if (!found) {
cout << " value not found" << endl;
}
}

void sorting() {
if (head == nullptr) return;

Node* iNode = head;

for (int i = 0; i < count; i++) {
Node* jNode = iNode->next;
for (int j = i + 1; j < count; j++) {
if (iNode->priority > jNode->priority) {
// swap priority
int tempP = iNode->priority;
 iNode->priority = jNode->priority;
jNode->priority = tempP;

// swap data
int tempD = iNode->data;
iNode->data = jNode->data;
jNode->data = tempD;
}
jNode = jNode->next;
}
iNode = iNode->next;
}

cout << "Queue sorted successfully.\n";

cout << "Value\tPriority\n";
displayForward();
}
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << "\t\t" << temp->priority << endl;
temp = temp->next;
}
}
};

int main() {
DoublyLinkedList dll;
[Link](10, 3);
[Link](20, 1);
[Link](30, 4);
[Link](40, 2);

cout << "Original List:" << endl;

 [Link]();

cout << "\nTesting Search:" << endl;

[Link](30);

cout << "\nTesting Sort by Priority:" << endl;

[Link]();

return 0;
}
2) Display circular linkedlist:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}
void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
newNode->next = head;
return;
 }
Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
void display() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};

int main() {
CircularLinkedList cll;
[Link](10);
[Link](20);
[Link](30);
[Link](40);

[Link]();

return 0;
}
LAB TASK 8: Double LinkedList operations
➢ Display double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node
{
public:
int data;
Node *prev;
Node *next;

Node(int val)
{
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
public:
Node *head;
DoublyLinkedList()
{
head = nullptr;
}

// display Forward
void displayForward()
{
Node *temp = head;
cout << "Forward: ";
while (temp != nullptr)
{
cout << temp->data << " ";
 temp = temp->next;
}
cout << endl;
}
};

int main()
{
DoublyLinkedList dll;
[Link]();
return 0;
}
➢ Insert at start in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node
{
public:
int data;
Node *prev;
Node *next;

Node(int val)
{
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
public:
Node *head;
DoublyLinkedList()
{
 head = nullptr;
}
void insertAtBeginning(int val)
{
Node* newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}
// display Forward
void displayForward()
{
Node *temp = head;
cout << "Forward: ";
while (temp != nullptr)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main()
{
DoublyLinkedList dll;
[Link](10); [Link](20);
[Link]();
return 0;
}
➢ Insert at end in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;

Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}

// Function to insert node at end

void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
 // Function to display list forward
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link]();

return 0;
}
➢ Insert at specific position in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;
 Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}

// Function to insert node at end

void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void insertAfter(int key, int val)
{
Node* temp = head;
while (temp != nullptr && temp->data != key)
temp = temp->next;

if (temp == nullptr)
{
cout << "Node not found!\n";
 return;
}

Node* newNode = new Node(val);

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != nullptr)
temp->next->prev = newNode;

temp->next = newNode;
}
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](10,40);
[Link]();

return 0;
}
➢ Delete from start in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;

Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}

// Function to insert node at end

void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
 temp->next = newNode;
newNode->prev = temp;
}
void insertAfter(int key, int val)
{
Node* temp = head;
while (temp != nullptr && temp->data != key)
temp = temp->next;

if (temp == nullptr)
{
cout << "Node not found!\n";
return;
}

Node* newNode = new Node(val);

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != nullptr)
temp->next->prev = newNode;

temp->next = newNode;
}
void deleteFromBeginning()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

head = head->next;

if (head != nullptr)
head->prev = nullptr;
 delete temp;
}
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](10,40);
[Link]();
[Link]();

return 0;
}
➢ Delete from end in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
 int data;
Node* prev;
Node* next;

Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}

// Function to insert node at end

void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void insertAfter(int key, int val)
{
Node* temp = head;
while (temp != nullptr && temp->data != key)
temp = temp->next;
 if (temp == nullptr)
{
cout << "Node not found!\n";
return;
}

Node* newNode = new Node(val);

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != nullptr)
temp->next->prev = newNode;

temp->next = newNode;
}
void deleteFromBeginning()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

head = head->next;

if (head != nullptr)
head->prev = nullptr;

delete temp;
}
void deleteFromEnd()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}
 Node* temp = head;

// Case: Only one node in the list

if (temp->next == nullptr)
{
delete temp;
head = nullptr;
return;
}

// Traverse to the last node

while (temp->next != nullptr)
temp = temp->next;

// Update the second-last node's next pointer

temp->prev->next = nullptr;

// Delete the last node

delete temp;
}
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;
 [Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](10,40);
[Link]();
[Link]();
[Link]();

return 0;
}
➢ Delete from specific position in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;

Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}
 // Function to insert node at end
void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void insertAfter(int key, int val)
{
Node* temp = head;
while (temp != nullptr && temp->data != key)
temp = temp->next;

if (temp == nullptr)
{
cout << "Node not found!\n";
return;
}

Node* newNode = new Node(val);

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != nullptr)
temp->next->prev = newNode;

temp->next = newNode;
}
void deleteFromBeginning()
{
if (head == nullptr)
 {
cout << "List is empty!\n";
return;
}

Node* temp = head;

head = head->next;

if (head != nullptr)
head->prev = nullptr;

delete temp;
}
void deleteFromEnd()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

// Case: Only one node in the list

if (temp->next == nullptr)
{
delete temp;
head = nullptr;
return;
}

// Traverse to the last node

while (temp->next != nullptr)
temp = temp->next;

// Update the second-last node's next pointer

temp->prev->next = nullptr;
 // Delete the last node
delete temp;
}
void deleteNode(int key)
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

// Search for the node with the given key

while (temp != nullptr && temp->data != key)
temp = temp->next;

// If node not found

if (temp == nullptr)
{
cout << "Node not found!\n";
return;
}

// Update previous node's next pointer

if (temp->prev != nullptr)
temp->prev->next = temp->next;
else
head = temp->next; // deleting first node

// Update next node's prev pointer

if (temp->next != nullptr)
temp->next->prev = temp->prev;

delete temp;
}
void displayForward() {
if (head == nullptr) {
 cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](10,40);
[Link]();
[Link]();
[Link](10);
[Link]();

return 0;
}
➢ Searching in double LinkedList:
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
 Node* next;

Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};

class DoublyLinkedList {
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}

// Function to insert node at end

void insertAtEnd(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void insertAfter(int key, int val)
{
Node* temp = head;
while (temp != nullptr && temp->data != key)
temp = temp->next;

if (temp == nullptr)
{
 cout << "Node not found!\n";
return;
}

Node* newNode = new Node(val);

newNode->next = temp->next;
newNode->prev = temp;

if (temp->next != nullptr)
temp->next->prev = newNode;

temp->next = newNode;
}
void deleteFromBeginning()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

head = head->next;

if (head != nullptr)
head->prev = nullptr;

delete temp;
}
void deleteFromEnd()
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

 // Case: Only one node in the list
if (temp->next == nullptr)
{
delete temp;
head = nullptr;
return;
}

// Traverse to the last node

while (temp->next != nullptr)
temp = temp->next;

// Update the second-last node's next pointer

temp->prev->next = nullptr;

// Delete the last node

delete temp;
}
void deleteNode(int key)
{
if (head == nullptr)
{
cout << "List is empty!\n";
return;
}

Node* temp = head;

// Search for the node with the given key

while (temp != nullptr && temp->data != key)
temp = temp->next;

// If node not found

if (temp == nullptr)
{
cout << "Node not found!\n";
return;
 }

// Update previous node's next pointer

if (temp->prev != nullptr)
temp->prev->next = temp->next;
else
head = temp->next; // deleting first node

// Update next node's prev pointer

if (temp->next != nullptr)
temp->next->prev = temp->prev;

delete temp;
}
void search(int key)
{
Node* temp = head;
int pos = 1;

while (temp != nullptr)

{
if (temp->data == key)
{
cout << key << " found at position " << pos << endl;
return;
}
temp = temp->next;
pos++;
}

cout << key << " not found!\n";

}
void displayForward() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
 cout << "Doubly Linked List : ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
DoublyLinkedList dll;

[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](10,40);
[Link]();
[Link]();
[Link](10);
[Link](40);
[Link]();

return 0;
}
LAB TASK -9: Circular LinkedList operations
➢ Display
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}

void display() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};
int main() {
CircularLinkedList cl1;
[Link]();
return 0;
}
➢ Insertion
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}

void insertion(int val)

{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
head->next = head;
}
else
 {
Node *temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
void display() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};

int main() {
CircularLinkedList cl1;
[Link]();
[Link](5); [Link](15); [Link](20);
return 0;
}
➢ Deletion
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}

void insertion(int val)

{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
head->next = head;
}
else
{
Node *temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
void deletion(int val) {
if (head == nullptr) {
cout << "List is empty!" << endl;
 return;
}
Node* current = head;
Node* prev = nullptr;

// head node to delete

if (head->data == val) {
Node* temp = head;
while (temp->next != head)
temp = temp->next;
if (head == head->next) {
head = nullptr;
} else {
temp->next = head->next;
head = head->next;
}
delete current;
cout << "Deleted " << val << endl;
return;
}

// any other node

do {
prev = current;
current = current->next;
} while (current != head && current->data != val);

if (current == head)
cout << "Value not found!" << endl;
else {
prev->next = current->next;
delete current;
cout << "Deleted " << val << endl;
}
}
void display() {
if (head == nullptr) {
cout << "List is empty!" << endl;
 return;
}
Node* temp = head;
cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};

int main() {
CircularLinkedList cl1;

[Link](5); [Link](15); [Link](20);

[Link](5);
[Link]();
return 0;
}
➢ Searching
ANSWER:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
Node* head;
public:
CircularLinkedList() {
head = nullptr;
}

void insertion(int val)

{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
head->next = head;
}
else
{
Node *temp = head;
while (temp->next != head)
{
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
void deletion(int val) {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* current = head;
Node* prev = nullptr;
if (head->data == val) {
Node* temp = head;
while (temp->next != head)
temp = temp->next;
if (head == head->next) {
head = nullptr;
} else {
 temp->next = head->next;
head = head->next;
}
delete current;
cout << "Deleted " << val << endl;
return;
}

// any other node

do {
prev = current;
current = current->next;
} while (current != head && current->data != val);

if (current == head)
cout << "Value not found!" << endl;
else {
prev->next = current->next;
delete current;
cout << "Deleted " << val << endl;
}
}
void search(int val) {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
int pos = 1;
bool found = false;
do {
if (temp->data == val) {
cout << val << " found at position " << pos << endl;
found = true;
break;
}
temp = temp->next;
pos++;
 } while (temp != head);

if (!found)
cout << val << " not found in the list!" << endl;
}
void display() {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
cout << "Circular Linked List: ";
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
};

int main() {
CircularLinkedList cl1;

[Link](5); [Link](15); [Link](20);

[Link](5);
[Link](15);
[Link]();
return 0;
}

END !