Rajarshi Shahu College Of Engineering,Buldana

Department of Computer Science and Engineering

Session 2023-24
Subject: Data Structure Lab Semester: 3rd

MASTER PRACTICALLIST

Sr.no Title

1 Write a program to find out largest number from the array and also find it’s location

Write a program to traverse an array and find the sum and average
2 of data elements from an array.

Write a Program to a) insert an element in an array b)delete an

3 element from an array.

4 To study and execute the Linear search method.

5 To study and execute the Binary Search method.

6 To study and execute the Pattern matching Algorithms( Slow and Fast)

7 To study and execute Bubble sort method.

To study and implement various operations on singly linked list
(a) Traversing the linked list.
(b) Insert a node at the front of the linked list.
8 (c) Delete a last node of the linked list.
(d) Searching a Linked list.

To study and implement following operations on the doubly linked list.

(a) Insert a node at the front of the linked list.
9 (b) Insert a node at the end of the linked list.
(c) Delete a last node of the linked list.
(d) Delete a node before specified position.
To study and implement following operations on the circular linked list.
(a) Insert a node at the end of the linked list.
10 (b) Insert a node before specified position.
(c) Delete a first node of the linked list.
(d) Delete a node after specified position.
11 Understand the stack structure and execute the push, pop operation on it.

1
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

12 Understand the Queue structure and execute the insertion, deletion operation on it.

Practical No. 1

Aim: Write a program to find out largest number from the array and also find it’s location.

Software Requirement:
Turbo C7
Theory:Arrays are used to store multiple values in a single variable, instead of declaring
separate variables for each value.

To create an array, define the data type (like int) and specify the name of the array
followed by square brackets [].

To insert values to it, use a comma-separated list, inside curly braces:

int myNumbers[] = {25, 50, 75, 100};

We have now created a variable that holds an array of four integers.

Access the Elements of an Array

To access an array element, refer to its index number.
2
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Array indexes start with 0: [0] is the first element. [1] is the second element, etc.

This statement accesses the value of the first element [0] in myNumbers:

Example
int myNumbers[] = {25, 50, 75, 100};
printf("%d", myNumbers[0]);
To find out largest element from array.Following sample codes are useful.
#include <stdio.h>
int main() {
int n;
double arr[100];
printf("Enter the number of elements (1 to 100): ");
scanf("%d", &n);

for (int i = 0; i < n; ++i) {

printf("Enter number%d: ", i + 1);
scanf("%lf", &arr[i]);
}

// storing the largest number to arr[0]

for (int i = 1; i < n; ++i) {
if (arr[0] < arr[i]) {
arr[0] = arr[i];
}
}

printf("Largest element = %.2lf", arr[0]);

return 0;
}

Output

Enter the number of elements (1 to 100): 5

Enter number1: 34.5
Enter number2: 2.4

3
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Enter number3: -35.5

Enter number4: 38.7
Enter number5: 24.5
Largest element = 38.70

Result: In this way, we have executed program to find largest element in an array.

Practical No. 2

Aim:
Write a program to traverse an array and find the sum and average of data elements from an array.

Software Requirement:
Turbo C7
Theory:
\* C Program to to Calculate Sum & Average of an Array *\

# include < stdio.h >

int main( )
{
int a[25], n, i ;
float avg = 0, sum = 0 ;
printf(" Enter the Numbers of element in Array: ") ;
scanf("%d ",& n) ;
printf("\n Enter the Array of Element : \n") ;
for ( i = 1 ; i < = n ; i++)
{
scanf("%d ",& a[i]) ;
}
for ( i = 1 ; i < = n ; i++)
{

4
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

sum = sum + a[i] ;

avg = sum / n ;
}
printf("\n Sum of Element of Array is : %f ",sum) ;
printf("\n Average of Element of Array are : %f ",avg) ;
return ( 0 ) ;
}
Output of Program:

Result: In this way, Students have executed the program to calculate sum & average of array elements.

5
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No. 3
Aim: Write a Program to a) insert an element in an array b)delete an element
from an array.

Software Requirement:
Turbo C7

Theory:
Inserting or deleting an element at the of an array can be easily done. If we need to insert or remove
an element in the middle of an array, half of the items must be shifted to accommodate the new
element while maintaining the order of the other elements.

Inserting a new element in an array

A new element can be inserted at any position of an array if there is enough memory space allocated
to accommodate the new element. Some of the elements should be shifted forward to keep the order
of the elements.

Suppose we want to add an element 93 at the 3rd position in the following array.

Initial array
After inserting all elements comes after 32 must be moved to the next location to accommodate the new
element and to keep the order of the elements as follows.

Array after inserting a new element

Example: Inserting new element in an array

The following program demonstrates how to insert a new element at the specified position in an array.

#include <stdio.h>
6
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int main()
{
int arr[100];
int i, item, pos, size=7;
printf("Enter 7 elements: ");
// reading array
for (i = 0; i < size; i++)
scanf("%d",&arr[i]);
// print the original array
printf("Array before insertion: ");
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
// read element to be inserted
printf("Enter the element to be inserted: ");
scanf("%d",&item);
// read position at which element is to be inserted
printf("Enter the position at which the element is to
be inserted: ");
scanf("%d",&pos);
// increase the size
size++;
// shift elements forward
for (i = size-1; i >= pos; i--)
arr[i] = arr[i - 1];
// insert item at position
arr[pos - 1] = item;
// print the updated array
printf("Array after insertion: ");
for (i = 0; i < size; i++)
7
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

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

printf("\n");
return 0;
}
Output

Enter 7 elements: 22 32 44 51 65 71 80
Array before insertion: 22 32 44 51 65 71 80
Enter the element to be inserted: 93
Enter the position at which the element is to be inserted: 3
Array after insertion: 22 32 93 44 51 65 71 80
Deleting an element from an array

Suppose we want to delete element 44 at the 3rd position in the following array.

Initial array
After deletion, all elements coming after 44 must be moved to the previous location to fill the free space and to
keep the order of the elements as follows.

Array after deleting an element

Algorithm

 Find the position of the element to be deleted in the array.

 If the element is found,
Shift all elements after the position of the element by 1 position.
Decrement array size by 1.
 If the element is not found: Print “Element Not Found”
Example: Deleting an element from an array

The following program demonstrates how to delete an element at the specified position in an array.

#include<stdio.h>
int main()

8
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

{
int key, i, pos = -1, size=5;
int arr[5] = {1, 20, 5, 78, 30};
printf("Array before deletion: ");
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
printf("Enter element to delete: ");
scanf("%d",&key);
// traverse the array
// if any element matches the key, store its position
for(i = 0; i < size; i++)
{
if(arr[i] == key)
{
pos = i;
break;
}
}
if(pos != -1)
{
//shift elements backwards by one position
for(i = pos; i < size - 1; i++)
arr[i] = arr[i+1];
printf("Array after deletion: ");
for(i = 0; i < size - 1; i++)
printf("%d ",arr[i]);
}
else
printf("Element Not Found\n");
return 0;
9
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

}
Output

Array before deletion: 1 20 5 78 30

Enter element to delete: 20
Array after deletion: 1 5 78 30
Post navigation

Result: In this way, Students have executed program to insert & delete element in to stack at the specified
position into array.

10
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No. 4
Aim: To study & execute linear search method.
Software Requirement:
TC7 Software
Theory:

// C program to implement linear search using loops

#include <stdio.h>

// linear search function that searches the key in arr

int linearSearch(int arr, int size, int key)

// starting traversal

for (int i = 0; i < size; i++) {

// checking condition

if (arr[i] == key) {

return i;

11
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

return -1;

// Driver code

int main()

int arr[10] = { 3, 4, 1, 7, 5, 8, 11, 42, 3, 13 };

int size = sizeof(arr) / sizeof(arr[0]);

int key = 4;

// calling linearSearch

int index = linearSearch(arr[], size, key);

// printing result based on value returned by

// linearSearch()

if (index == -1) {

printf("The element is not present in the arr.");

12
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

else {

printf("The element is present at arr[%d].", index);

return 0;

Output

Result: In this way, Student had studied the program of Linear Search method.

Practical No. 5
Aim: To study & execute binary search method.
Software Requirement:
TC7
Theory:
#include <stdio.h>
int main()
{
13
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int i, low, high, mid, n, key, array[100];

printf("Enter number of elementsn");
scanf("%d",&n);
printf("Enter %d integers");
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter value to find");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high) {
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key) {
printf("%d found at location %d.n", key, mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("Not found! %d isn't present in the list.n", key);
return 0;
}
Result: In this way we have studied Binary search method.

14
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No. 6
Aim: To Study Pattern Matching algorithm in C.
Software Requirement:
Turbo C7 Software
Theory:

Pattern Matching is widely used in computer science and many other fields. Pattern
Matching algorithms are used to search for patterns within a larger text or data set.
One of the most popular algorithms for pattern matching is the Boyer-
Moore algorithm, which was first published in 1977. In this article, we will discuss
Pattern Matching algorithms in C and how they work.

What is a Pattern Matching Algorithm?

Pattern Matching algorithms are used to find patterns within a bigger set of data or
text. These algorithms work by comparing a pattern with a larger data set or text
and determining whether or not the pattern is present. Pattern Matching algorithms
are important because they allow us to search for patterns in large data sets quickly.

Brute Force Pattern Matching Algorithm:

Brute Force Pattern Matching is the simplest Pattern Matching Algorithm. It involves
comparing the characters of the pattern with the characters of the text one by one. If
all the characters match, the algorithm returns the starting position of the pattern in
the text. If not, the algorithm moves to the next position in the text and repeats the
comparison until a match is found or the end of the text is reached. The Time
Complexity of the Brute Force Algorithm is O(MXN), where M denotes the length of
the text and N denotes the length of the pattern.

Naive Pattern Matching Algorithm:

15
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

The Naive Pattern Matching algorithm is an improvement over the Brute Force
algorithm. It avoids unnecessary comparisons by skipping some positions in the text.
The algorithm starts comparing the pattern with the text at the first position. If the
characters match, it moves to the next position and repeats the comparison. If the
characters do not match, the algorithm moves to the next position in the text and
compares the pattern with the text again. The time complexity of the Naive
algorithm is also O(MXN), but it is faster than the Brute Force algorithm in most
cases.

Knuth-Morris-Pratt Algorithm:
The Knuth-Morris-Pratt (KMP) algorithm is a more advanced Pattern Matching
algorithm. It is based on the observation that when a mismatch occurs, some
information about the text and the pattern can be used to avoid unnecessary
comparisons. The algorithm precomputes a table that contains information about the
pattern. The table determines how many characters of the pattern can be skipped
when a mismatch occurs. The Time Complexity of the KMP algorithm is O(M+N).

The Boyer-Moore Algorithm:

One of the most popular Pattern Matching algorithms is the Boyer-Moore algorithm.
This algorithm was first published in 1977 by Robert S. Boyer and J Strother Moore.
The Boyer-Moore algorithm compares a pattern with a larger set of data or text
from right to left instead of left to right, as with most other pattern matching
algorithms.

The Boyer-Moore algorithm has two main components: the bad character rule and
the good suffix rule. The bad character rule works by comparing the character in the
pattern with the corresponding character in the data or text. If the characters do not
match, the algorithm moves the pattern to the right until it finds a character that
matches. The good suffix rule compares the suffix of the pattern with the
corresponding suffix of the data or text. If the suffixes do not match, the algorithm
moves the pattern to the right until it finds a matching suffix.

The Boyer-Moore algorithm is known for its efficiency and is widely used in many
applications. It is considered one of the fastest pattern matching algorithms
available.

Implementing the Boyer-Moore algorithm in C:

16
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

To implement the Boyer-Moore algorithm in C, we can start by defining the bad

character rule. We can use an array to store the last occurrence of each character in
the pattern. This array can determine how far we must move the pattern to the right
when a mismatch occurs.

1. void bad_character_rule(char *pattern, int pattern_length, int *bad_char)

2. {
3. int i;
4. for (i = 0; i < NO_OF_CHARS; i++)
5. bad_char[i] = -1;
6. for (i = 0; i < pattern_length; i++)
7. bad_char[(int) pattern[i]] = i;
8. }

In this example, we first initialize the array to -1 for all characters. We then iterate
through the pattern and update the array with the last occurrence of each character
in the pattern.

Next, we can implement the good suffix rule. We can use an array to store the length
of the longest suffix of the pattern that matches a suffix of the data or text. This
array can be used to determine how far we need to move the pattern to the right.

Result:
In this way, students have studied pattern matching algorithm in C.

17
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No.7
Aim: To Study & Execute bubble sort program in C.
Software Requirement:
TC7 software
Theory:

Bubble sort is a simple and intuitive sorting algorithm. It repeatedly swaps adjacent
elements if they are in the wrong order until the array is sorted. In this algorithm, the
largest element "bubbles up" to the end of the array in each iteration. Bubble sort is
inefficient for large data sets, but it is useful for educational purposes and small data
sets. In this article, we will implement the bubble sort algorithm in C programming
language.

The first step is to define the bubble sort function. This function takes an integer
array and the size of the array as its parameters. The function returns nothing as it
modifies the original array.

1. #include <stdio.h>
2.
3. void bubble_sort(int arr[], int n) {
4. int i, j;
5. for (i = 0; i < n - 1; i++) {
6. for (j = 0; j < n - i - 1; j++) {
7. if (arr[j] > arr[j + 1]) {
8. int temp = arr[j];
9. arr[j] = arr[j + 1];
10. arr[j + 1] = temp;
11. }
12. }

18
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

13. }
14. }
15. int main() {
16. int arr[] = {64, 34, 25, 12, 22, 11, 90};
17. int n = sizeof(arr) / sizeof(arr[0]);
18. bubble_sort(arr, n);
19. printf("Sorted array: ");
20. for (int i = 0; i < n; i++) {
21. printf("%d ", arr[i]);
22. }
23. return 0;
24. }

Result:
In this we have studied Bubble Sort algorithm & executed Bubble Sort Program in C.

19
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No.8
Aim: study and implement various operations on singly linked list
(a) Traversing the linked list.
(b) Insert a node at the front of the linked list.
(c) Delete a last node of the linked list.
(d) Searching a Linked list.

Theory:
A Linked List is a linear data structure that consists of two parts: one is the data part
and the other is the address part. In this article, all the common operations of a singly
linked list are discussed in one menu-driven program.
Operations to be performed :
 createList(): To create the list with the ‘n’ number of nodes initially as defined by the
user.
 traverse(): To see the contents of the linked list, it is necessary to traverse the given
linked list. The given traverse() function traverses and prints the content of the linked
list.
 insertAtFront(): This function simply inserts an element at the front/beginning of the
linked list.
 insertAtEnd(): This function inserts an element at the end of the linked list.
 insertAtPosition(): This function inserts an element at a specified position in the
linked list.
 deleteFirst(): This function simply deletes an element from the front/beginning of the
linked list.
 deleteEnd(): This function simply deletes an element from the end of the linked list.
 deletePosition(): This function deletes an element from a specified position in the
linked list.
 maximum(): This function finds the maximum element in a linked list.
 mean(): This function finds the mean of the elements in a linked list.
20
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

 sort(): This function sorts the given linked list in ascending order.
 reverseLL(): This function reverses the given linked list.
 display(): This function displays the linked list.
 search(): This function searches for an element user wants to search.
Below is the implementation of the above operations:
C

// C program for the all operations in

// the Singly Linked List

#include <stdio.h>

#include <stdlib.h>

// Linked List Node

struct node {

int info;

struct node* link;

};

struct node* start = NULL;

// Function to create list with n nodes initially

21
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

void createList()

if (start == NULL) {

int n;

printf("\nEnter the number of nodes: ");

scanf("%d", &n);

if (n != 0) {

int data;

struct node* newnode;

struct node* temp;

newnode = malloc(sizeof(struct node));

start = newnode;

temp = start;

printf("\nEnter number to"

" be inserted : ");

scanf("%d", &data);

start->info = data;

22
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

for (int i = 2; i <= n; i++) {

newnode = malloc(sizeof(struct node));

temp->link = newnode;

printf("\nEnter number to"

" be inserted : ");

scanf("%d", &data);

newnode->info = data;

temp = temp->link;

printf("\nThe list is created\n");

else

printf("\nThe list is already created\n");

23
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Function to traverse the linked list

void traverse()

struct node* temp;

// List is empty

if (start == NULL)

printf("\nList is empty\n");

// Else print the LL

else {

temp = start;

while (temp != NULL) {

printf("Data = %d\n", temp->info);

temp = temp->link;

24
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Function to insert at the front

// of the linked list

void insertAtFront()

int data;

struct node* temp;

temp = malloc(sizeof(struct node));

printf("\nEnter number to"

" be inserted : ");

scanf("%d", &data);

temp->info = data;

// Pointer of temp will be

// assigned to start

temp->link = start;

25
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

start = temp;

// Function to insert at the end of

// the linked list

void insertAtEnd()

int data;

struct node *temp, *head;

temp = malloc(sizeof(struct node));

// Enter the number

printf("\nEnter number to"

" be inserted : ");

scanf("%d", &data);

// Changes links

26
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

temp->link = 0;

temp->info = data;

head = start;

while (head->link != NULL) {

head = head->link;

head->link = temp;

// Function to insert at any specified

// position in the linked list

void insertAtPosition()

struct node *temp, *newnode;

int pos, data, i = 1;

newnode = malloc(sizeof(struct node));

27
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Enter the position and data

printf("\nEnter position and data :");

scanf("%d %d", &pos, &data);

// Change Links

temp = start;

newnode->info = data;

newnode->link = 0;

while (i < pos - 1) {

temp = temp->link;

i++;

newnode->link = temp->link;

temp->link = newnode;

// Function to delete from the front

28
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// of the linked list

void deleteFirst()

struct node* temp;

if (start == NULL)

printf("\nList is empty\n");

else {

temp = start;

start = start->link;

free(temp);

// Function to delete from the end

// of the linked list

void deleteEnd()

29
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

struct node *temp, *prevnode;

if (start == NULL)

printf("\nList is Empty\n");

else {

temp = start;

while (temp->link != 0) {

prevnode = temp;

temp = temp->link;

free(temp);

prevnode->link = 0;

// Function to delete from any specified

// position from the linked list

void deletePosition()

30
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

struct node *temp, *position;

int i = 1, pos;

// If LL is empty

if (start == NULL)

printf("\nList is empty\n");

// Otherwise

else {

printf("\nEnter index : ");

// Position to be deleted

scanf("%d", &pos);

position = malloc(sizeof(struct node));

temp = start;

31
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Traverse till position

while (i < pos - 1) {

temp = temp->link;

i++;

// Change Links

position = temp->link;

temp->link = position->link;

// Free memory

free(position);

// Function to find the maximum element

// in the linked list

32
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

void maximum()

int a[10];

int i;

struct node* temp;

// If LL is empty

if (start == NULL)

printf("\nList is empty\n");

// Otherwise

else {

temp = start;

int max = temp->info;

// Traverse LL and update the

// maximum element

33
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

while (temp != NULL) {

// Update the maximum

// element

if (max < temp->info)

max = temp->info;

temp = temp->link;

printf("\nMaximum number "

"is : %d ",

max);

// Function to find the mean of the

// elements in the linked list

void mean()

34
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int a[10];

int i;

struct node* temp;

// If LL is empty

if (start == NULL)

printf("\nList is empty\n");

// Otherwise

else {

temp = start;

// Stores the sum and count of

// element in the LL

int sum = 0, count = 0;

float m;

35
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Traverse the LL

while (temp != NULL) {

// Update the sum

sum = sum + temp->info;

temp = temp->link;

count++;

// Find the mean

m = sum / count;

// Print the mean value

printf("\nMean is %f ", m);

36
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Function to sort the linked list

// in ascending order

void sort()

struct node* current = start;

struct node* index = NULL;

int temp;

// If LL is empty

if (start == NULL) {

return;

// Else

else {

37
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Traverse the LL

while (current != NULL) {

index = current->link;

// Traverse the LL nestedly

// and find the minimum

// element

while (index != NULL) {

// Swap with it the value

// at current

if (current->info > index->info) {

temp = current->info;

current->info = index->info;

index->info = temp;

index = index->link;

38
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Update the current

current = current->link;

// Function to reverse the linked list

void reverseLL()

struct node *t1, *t2, *temp;

t1 = t2 = NULL;

// If LL is empty

if (start == NULL)

printf("List is empty\n");

39
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Else

else {

// Traverse the LL

while (start != NULL) {

// reversing of points

t2 = start->link;

start->link = t1;

t1 = start;

start = t2;

start = t1;

// New head Node

temp = start;

40
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

printf("Reversed linked "

"list is : ");

// Print the LL

while (temp != NULL) {

printf("%d ", temp->info);

temp = temp->link;

// Function to search an element in linked list

void search()

int found = -1;

// creating node to traverse

41
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

struct node* tr = start;

// first checking if the list is empty or not

if (start == NULL) {

printf("Linked list is empty\n");

else {

printf("\nEnter the element you want to search: ");

int key;

scanf("%d", &key);

// checking by traversing

while (tr != NULL) {

// checking for key

if (tr->info == key) {

found = 1;

break;

42
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// moving forward if not at this position

else {

tr = tr->link;

// printing found or not

if (found == 1) {

printf(

"Yes, %d is present in the linked list.\n",

key);

else {

printf("No, %d is not present in the linked "

"list.\n",

key);

43
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// Driver Code

int main()

createList();

int choice;

while (1) {

printf("\n\t1 To see list\n");

printf("\t2 For insertion at"

" starting\n");

printf("\t3 For insertion at"

" end\n");

printf("\t4 For insertion at "

44
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

"any position\n");

printf("\t5 For deletion of "

"first element\n");

printf("\t6 For deletion of "

"last element\n");

printf("\t7 For deletion of "

"element at any position\n");

printf("\t8 To find maximum among"

" the elements\n");

printf("\t9 To find mean of "

"the elements\n");

printf("\t10 To sort element\n");

printf("\t11 To reverse the "

"linked list\n");

printf("\t12 Search an element in linked list\n");

printf("\t13 To exit\n");

printf("\nEnter Choice :\n");

45
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

scanf("%d", &choice);

switch (choice) {

case 1:

traverse();

break;

case 2:

insertAtFront();

break;

case 3:

insertAtEnd();

break;

case 4:

insertAtPosition();

break;

case 5:

deleteFirst();

46
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

break;

case 6:

deleteEnd();

break;

case 7:

deletePosition();

break;

case 8:

maximum();

break;

case 9:

mean();

break;

case 10:

sort();

break;

case 11:

47
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

reverseLL();

break;

case 12:

search();

break;

case 13:

exit(1);

break;

default:

printf("Incorrect Choice\n");

return 0;

Output:
Menu:

48
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Insertion at the starting:

Insertion at the end:

49
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Insertion at specific position:

Print the Linked List:

Maximum among Linked List:

Sorting the Linked List:

Reverse the Linked List:

Delete the first and last element with choice 5 and 6:

50
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Searching the element with choice 12:

51
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Result :

In this we have studied various operation on link list.

52
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No.9
Aim: To study optimization techniques using OR-tools.

Theory:
Inserting a new node in a doubly linked list is very similar to inserting new
node in linked list. There is a little extra work required to maintain the link of the
previous node. A node can be inserted in a Doubly Linked List in four ways:
 At the front of the DLL.
 In between two nodes
 After a given node.
 Before a given node.
 At the end of the DLL.
Add a node at the front in a Doubly Linked List:
The new node is always added before the head of the given Linked List. The task can
be performed by using the following 5 steps:
1. Firstly, allocate a new node (say new_node).
2. Now put the required data in the new node.
3. Make the next of new_node point to the current head of the doubly linked list.
53
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

4. Make the previous of the current head point to new_node.

5. Lastly, point head to new_node.
Illustration:
See the below illustration where E is being inserted at the beginning of the doubly linked
list.

Below is the implementation of the 5 steps to insert a node at the front of the linked list:

 C
 C++
 Java
 Python3
 C#
 Javascript

// Given a reference (pointer to pointer) to the head

// of a list and an int, inserts a new node

// on the front of the list.

void push(struct Node** head_ref, int new_data)

// 1. allocate node

struct Node* new_node

= (struct Node*)malloc(sizeof(struct Node));

54
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// 2. put in the data

new_node->data = new_data;

// 3. Make next of new node as head and previous as NULL

new_node->next = (*head_ref);

new_node->prev = NULL;

// 4. change prev of head node to new node

if ((*head_ref) != NULL)

(*head_ref)->prev = new_node;

// 5. move the head to point to the new node

(*head_ref) = new_node;

Learn Data Structures & Algorithms with GeeksforGeeks

Time Complexity: O(1)
Auxiliary Space: O(1)
Add a node in between two nodes:
It is further classified into the following two parts:
55
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Add a node after a given node in a Doubly Linked List:

We are given a pointer to a node as prev_node, and the new node is inserted after the
given node. This can be done using the following 6 steps:
1. Firstly create a new node (say new_node).
2. Now insert the data in the new node.
3. Point the next of new_node to the next of prev_node.
4. Point the next of prev_node to new_node.
5. Point the previous of new_node to prev_node.
6. Change the pointer of the new node’s previous pointer to new_node.
Illustration:
See the below illustration where ‘E‘ is being inserted after ‘B‘.

Below is the implementation of the 7 steps to insert a node after a given node in the
linked list

// Given a node as prev_node, insert a new node

// after the given node

56
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

void insertAfter(struct Node* prev_node, int new_data)

// Check if the given prev_node is NULL

if (prev_node == NULL) {

printf("the given previous node cannot be NULL");

return;

// 1. allocate new node

struct Node* new_node

= (struct Node*)malloc(sizeof(struct Node));

// 2. put in the data

new_node->data = new_data;

// 3. Make next of new node as next of prev_node

new_node->next = prev_node->next;

57
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

// 4. Make the next of prev_node as new_node

prev_node->next = new_node;

// 5. Make prev_node as previous of new_node

new_node->prev = prev_node;

// 6. Change previous of new_node's next node

if (new_node->next != NULL)

new_node->next->prev = new_node;

Time Complexity: O(1)

Auxiliary Space: O(1)
Add a node before a given node in a Doubly Linked List:
Let the pointer to this given node be next_node. This can be done using the following 6
steps.
1. Allocate memory for the new node, let it be called new_node.
2. Put the data in new_node.
3. Set the previous pointer of this new_node as the previous node of the next_node.
4. Set the previous pointer of the next_node as the new_node.
5. Set the next pointer of this new_node as the next_node.
6. Now set the previous pointer of new_node.
58
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

 If the previous node of the new_node is not NULL, then set the next pointer of this
previous node as new_node.
 Else, if the prev of new_node is NULL, it will be the new head node.
Illustration:
See the below illustration where ‘B‘ is being inserted before ‘C‘.

Below is the implementation of the above

// Given a node as prev_node, insert a new node

// after the given node

void insertBefore(struct Node* next_node, int new_data)

// Check if the given next_node is NULL

if (next_node == NULL) {

printf("the given next node cannot be NULL");

return;

// 1. Allocate new node

59
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

struct Node* new_node

= (struct Node*)malloc(sizeof(struct Node));

// 2. Put in the data

new_node->data = new_data;

// 3. Make previous of new node as previous of next_node

new_node->prev = next_node->prev;

// 4. Make the previous of next_node as new_node

next_node->prev = new_node;

// 5. Make next_node as next of new_node

new_node->next = next_node;

// 6. Change next of new_node's previous node

60
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

if (new_node->prev != NULL)

new_node->prev->next = new_node;

else

head = new_node;

Time Complexity: O(1)

Auxiliary Space: O(1)
Add a node at the end in a Doubly Linked List:
The new node is always added after the last node of the given Linked List. This can be
done using the following 7 steps:
1. Create a new node (say new_node).
2. Put the value in the new node.
3. Make the next pointer of new_node as null.
4. If the list is empty, make new_node as the head.
5. Otherwise, travel to the end of the linked list.
6. Now make the next pointer of last node point to new_node.
7. Change the previous pointer of new_node to the last node of the list.

Result:
In this way we have studied various operations on doubly link list.

61
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No .10
Aim: To study and implement following operations on the circular linked list.
(a) Insert a node at the end of the linked list.
(b) Insert a node before specified position.
(c) Delete a first node of the linked list.
(d) Delete a node after specified position.
Theory:

In a circular Singly linked list, the last node of the list contains a pointer to the first
node of the list. We can have circular singly linked list as well as circular doubly
linked list.

We traverse a circular singly linked list until we reach the same node where we
started. The circular singly liked list has no beginning and no ending. There is no null
value present in the next part of any of the nodes.

Circular linked list are mostly used in task maintenance in operating systems. There
are many examples where circular linked list are being used in computer science
including browser surfing where a record of pages visited in the past by the user, is
maintained in the form of circular linked lists and can be accessed again on clicking
the previous button.

Memory Representation of circular linked list:

In the following image, memory representation of a circular linked list containing
marks of a student in 4 subjects. However, the image shows a glimpse of how the
circular list is being stored in the memory. The start or head of the list is pointing to
the element with the index 1 and containing 13 marks in the data part and 4 in the
next part. Which means that it is linked with the node that is being stored at 4th
index of the list.

62
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

However, due to the fact that we are considering circular linked list in the memory
therefore the last node of the list contains the address of the first node of the list.

We can also have more than one number of linked list in the memory with the
different start pointers pointing to the different start nodes in the list. The last node
is identified by its next part which contains the address of the start node of the list.
We must be able to identify the last node of any linked list so that we can find out
the number of iterations which need to be performed while traversing the list.

63
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Operations on Circular Singly linked list:

Insertion

SN Operation Description

1 Insertion at beginning Adding a node into circular singly linked list at the beginning.

2 Insertion at the end Adding a node into circular singly linked list at the end.

Deletion & Traversing

S Operation Description
N

1 Deletion at Removing the node from circular singly linked list at the beginning.
beginning

2 Deletion at the Removing the node from circular singly linked list at the end.
end

3 Searching Compare each element of the node with the given item and return the
location at which the item is present in the list otherwise return null.

4 Traversing Visiting each element of the list at least once in order to perform some
specific operation.

Menu-driven program in C implementing all operations

on circular singly linked list

1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
64
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

5. int data;
6. struct node *next;
7. };
8. struct node *head;
9.
10.void beginsert ();
11.void lastinsert ();
12.void randominsert();
13.void begin_delete();
14.void last_delete();
15.void random_delete();
16.void display();
17.void search();
18.void main ()
19.{
20. int choice =0;
21. while(choice != 7)
22. {
23. printf("\n*********Main Menu*********\n");
24. printf("\nChoose one option from the following list ...\n");
25. printf("\n===============================================\
n");
26. printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from l
ast\n5.Search for an element\n6.Show\n7.Exit\n");
27. printf("\nEnter your choice?\n");
28. scanf("\n%d",&choice);
29. switch(choice)
30. {
31. case 1:
32. beginsert();
65
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

33. break;
34. case 2:
35. lastinsert();
36. break;
37. case 3:
38. begin_delete();
39. break;
40. case 4:
41. last_delete();
42. break;
43. case 5:
44. search();
45. break;
46. case 6:
47. display();
48. break;
49. case 7:
50. exit(0);
51. break;
52. default:
53. printf("Please enter valid choice..");
54. }
55. }
56.}
57.void beginsert()
58.{
59. struct node *ptr,*temp;
60. int item;
61. ptr = (struct node *)malloc(sizeof(struct node));
62. if(ptr == NULL)
66
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

63. {
64. printf("\nOVERFLOW");
65. }
66. else
67. {
68. printf("\nEnter the node data?");
69. scanf("%d",&item);
70. ptr -> data = item;
71. if(head == NULL)
72. {
73. head = ptr;
74. ptr -> next = head;
75. }
76. else
77. {
78. temp = head;
79. while(temp->next != head)
80. temp = temp->next;
81. ptr->next = head;
82. temp -> next = ptr;
83. head = ptr;
84. }
85. printf("\nnode inserted\n");
86. }
87.
88.}
89.void lastinsert()
90.{
91. struct node *ptr,*temp;
92. int item;
67
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

93. ptr = (struct node *)malloc(sizeof(struct node));

94. if(ptr == NULL)
95. {
96. printf("\nOVERFLOW\n");
97. }
98. else
99. {
100. printf("\nEnter Data?");
101. scanf("%d",&item);
102. ptr->data = item;
103. if(head == NULL)
104. {
105. head = ptr;
106. ptr -> next = head;
107. }
108. else
109. {
110. temp = head;
111. while(temp -> next != head)
112. {
113. temp = temp -> next;
114. }
115. temp -> next = ptr;
116. ptr -> next = head;
117. }
118.
119. printf("\nnode inserted\n");
120. }
121.
122. }
68
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

123.
124. void begin_delete()
125. {
126. struct node *ptr;
127. if(head == NULL)
128. {
129. printf("\nUNDERFLOW");
130. }
131. else if(head->next == head)
132. {
133. head = NULL;
134. free(head);
135. printf("\nnode deleted\n");
136. }
137.
138. else
139. { ptr = head;
140. while(ptr -> next != head)
141. ptr = ptr -> next;
142. ptr->next = head->next;
143. free(head);
144. head = ptr->next;
145. printf("\nnode deleted\n");
146.
147. }
148. }
149. void last_delete()
150. {
151. struct node *ptr, *preptr;
152. if(head==NULL)
69
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

153. {
154. printf("\nUNDERFLOW");
155. }
156. else if (head ->next == head)
157. {
158. head = NULL;
159. free(head);
160. printf("\nnode deleted\n");
161.
162. }
163. else
164. {
165. ptr = head;
166. while(ptr ->next != head)
167. {
168. preptr=ptr;
169. ptr = ptr->next;
170. }
171. preptr->next = ptr -> next;
172. free(ptr);
173. printf("\nnode deleted\n");
174.
175. }
176. }
177.
178. void search()
179. {
180. struct node *ptr;
181. int item,i=0,flag=1;
182. ptr = head;
70
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

183. if(ptr == NULL)

184. {
185. printf("\nEmpty List\n");
186. }
187. else
188. {
189. printf("\nEnter item which you want to search?\n");
190. scanf("%d",&item);
191. if(head ->data == item)
192. {
193. printf("item found at location %d",i+1);
194. flag=0;
195. }
196. else
197. {
198. while (ptr->next != head)
199. {
200. if(ptr->data == item)
201. {
202. printf("item found at location %d ",i+1);
203. flag=0;
204. break;
205. }
206. else
207. {
208. flag=1;
209. }
210. i++;
211. ptr = ptr -> next;
212. }
71
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

213. }
214. if(flag != 0)
215. {
216. printf("Item not found\n");
217. }
218. }
219.
220. }
221.
222. void display()
223. {
224. struct node *ptr;
225. ptr=head;
226. if(head == NULL)
227. {
228. printf("\nnothing to print");
229. }
230. else
231. {
232. printf("\n printing values ... \n");
233.
234. while(ptr -> next != head)
235. {
236.
237. printf("%d\n", ptr -> data);
238. ptr = ptr -> next;
239. }
240. printf("%d\n", ptr -> data);
241. }
242.
72
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

243. }

Output:

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

1

Enter the node data?10

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

2

Enter Data?20

node inserted

*********Main Menu*********

73
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

2

Enter Data?30

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

3

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element

74
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

6.Show
7.Exit

Enter your choice?

4

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

5

Enter item which you want to search?

20
item found at location 1
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

6

printing values ...

20

*********Main Menu*********

75
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Delete from Beginning
4.Delete from last
5.Search for an element
6.Show
7.Exit

Enter your choice?

7

Result:Thus we have studied various operations on circular link list.

76
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No 11

Aim: Understand the stack structure and execute the push, pop operation on it.

Theory:

The Last-In-First-Out (LIFO) concept is used by Stacks, a type of linear data structure.
The Queue has two endpoints, but the Stack only has one (front and rear). It only has
one pointer, top pointer, which points to the stack's topmost member. When an
element is added to the stack, it is always added to the top, and it can only be
removed from the stack. To put it another way, a stack is a container that allows
insertion and deletion from the end known as the stack's top.

LIFO (Last in First Out)

According to this method, the piece that was added last will appear first. As an
actual illustration, consider a stack of dishes stacked on top of one another. We may
claim that the plate we put last comes out first because the plate we put last is on
top and we take the plate at the top.

Due to the possibility of understating inventory value, LIFO is not a reliable indicator
of ending inventory value. Due to increasing COGS, LIFO leads to reduced net
income (and taxes). However, under LIFO during inflation, there are fewer inventory
write-downs. Results from average cost are in the middle of FIFO and LIFO.

Real Life Example of LIFO

Let's say that business A sells 10 widgets. $100 per, the first five widgets were
delivered two days ago. The remaining five widgets, which cost $200 apiece, just got
here yesterday. The last items received are the first to go out on the market,
according to the LIFO technique of inventory management. How much may the
accountant put down as a cost even though seven widgets were sold?

77
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Although the income from each widget is the same because of its fixed sales price,
the cost of each widget is determined by the inventory method used. The last item
received is the first item sold according to the LIFO mechanism. Accordingly, the
$200 widgets were the first to sell. Following that, the business sold two more of the
$100 widgets. Five widgets are priced at $200 each, and two are priced at $100, for
a total cost of $1,200 for the widgets using the LIFO approach. As opposed to FIFO,
which sells the $200 widgets last, the $100 widgets are sold first. As a result, the
price of the sold widgets, which breaks down to five at $100 and two at $200, will be
reported as $900. That's why LIFO generates bigger profits during price-increasing
periods.

Because of this, LIFO increases expenses during times of price growth and decreases
net revenue, which also lowers taxable income. Similar to this, LIFO reduces
expenses and raises net income during periods of declining prices, which also raises
taxable revenue.

Stack Vs Array
Stack: A stack is a type of linear data structure whose components may only be
added to or removed from the top side of the list. The Last in First out (LIFO)
principle governs stacks, meaning that the element put last is the first element to be
removed. Push operations and pop operations are the terms used to describe the
addition and removal of elements from stacks, respectively. A pointer named top is
used in stack to maintain track of the last piece that is currently present in the list.

Array: A group of objects kept in consecutive memory regions is known as an array.

The goal is to group objects of the same category for storage. As a result, it is
simpler to determine each element's position by simply adding an offset to a base
value, or the address in memory where the array's first element is stored (generally
denoted by the name of the array).

78
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

push()
It stacks up a new item. A stack overflow circumstance is when the stack is
completely full.

Algorithm for push():

push()
It stacks up a new item. A stack overflow circumstance is when the stack is
completely full.

Algorithm for push():

1. begin
2. if stack is full
3. return
4. endif

79
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

5. else
6. increment top
7. stack[top] assign value
8. end else
9. end procedure

pop()
It takes something out of the stack. In the opposite sequence from which they were
pushed, the things are popped. The condition is referred to as an underflow if the
stack is empty.

Algorithm for pop():

1. begin
2. if stack is empty
3. return
4. endif
5. else
6. store value of stack[top]
7. decrement top
8. return value
9. end else
10. end procedure

Program to demonstrate push and pop operation in stack in data

structure in C

1. #include <stdio.h>
2. #include <stdlib.h>
3. #define SIZE 4
4. int top = -1, inp_array[SIZE];

80
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

5. void push();
6. void pop();
7. void show();
8. int main()
9. {
10. int choice;
11. while (1)
12. {
13. printf("\nPerform operations on the stack:");
14. printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
15. printf("\n\nEnter the choice: ");
16. scanf("%d", &choice);
17. switch (choice)
18. {
19. case 1:
20. push();
21. break;
22. case 2:
23. pop();
24. break;
25. case 3:
26. show();
27. break;
28. case 4:
29. exit(0);
30. default:
31. printf("\nInvalid choice!!");
32. }
33. }
34. }
81
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

35. void push()

36. {
37. int x;
38. if (top == SIZE - 1)
39. {
40. printf("\nOverflow!!");
41. }
42. else
43. {
44. printf("\nEnter the element to be added onto the stack: ");
45. scanf("%d", &x);
46. top = top + 1;
47. inp_array[top] = x;
48. }
49. }
50. void pop()
51. {
52. if (top == -1)
53. {
54. printf("\nUnderflow!!");
55. }
56. else
57. {
58. printf("\nPopped element: %d", inp_array[top]);
59. top = top - 1;
60. }
61. }
62. void show()
63. {
64. if (top == -1)
82
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

65. {
66. printf("\nUnderflow!!");
67. }
68. else
69. {
70. printf("\nElements present in the stack: \n");
71. for (int i = top; i >= 0; --i)
72. printf("%d\n", inp_array[i]);
73. }
74. }

Output

10 pushed into stack

20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10
...........................................................
Process executed in 3.22 seconds
Press any key to continue.

Explanation

As we can see in the above example of push and pop operation in c, we pushed 10,
20 and 30. After successfully pushing elements into the stack we pop out 30 from
the stack and to check if the element is pop out or not, we checked it by performing
top operation on the stack, which found out to be 20.

Conclusion:
In this way we have studied Push & Pop operation on Stack

83
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Practical No 12
Aim: nderstand the Queue structure and execute the insertion, deletion operation on it.

Software:TC7 software
Theory: Queue, like Stack, is also an abstract data structure. The thing that
makes queue different from stack is that a queue is open at both its ends.
Hence, it follows FIFO (First-In-First-Out) structure, i.e. the data item inserted
first will also be accessed first. The data is inserted into the queue through
one end and deleted from it using the other end.
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.

Basic Operations

Queue operations also include initialization of a queue, usage and

permanently deleting the data from the memory.

The most fundamental operations in the queue ADT include: enqueue(),

dequeue(), peek(), isFull(), isEmpty(). These are all built-in operations to
carry out data manipulation and to check the status of the queue.

84
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Queue uses two pointers − front and rear. The front pointer accesses the
data from the front end (helping in enqueueing) while the rear pointer
accesses data from the rear end (helping in dequeuing).
Insertion operation: enqueue()
The enqueue() is a data manipulation operation that is used to insert
elements into the stack. The following algorithm describes the enqueue()
operation in a simpler way.

Algorithm

1. START
2. Check if the queue is full.
3. If the queue is full, produce overflow error and exit.
4. If the queue is not full, increment rear pointer to point
the next empty space.
5. Add data element to the queue location, where the rear
is pointing.
6. return success.
7. END

Example

Following are the implementations of this operation in various

programming languages −

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
85
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
86
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

printf("Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
Output
Queue: 3 5 9 1 12 15

Deletion Operation: dequeue()

The dequeue() is a data manipulation operation that is used to remove
elements from the stack. The following algorithm describes the dequeue()
operation in a simpler way.

Algorithm

1. START
2. Check if the queue is empty.
3. If the queue is empty, produce underflow error and exit.
4. If the queue is not empty, access the data where front
is pointing.
5. Increment front pointer to point to the next available
data element.
6. Return success.
7. END

Example

Following are the implementations of this operation in various

programming languages −

#include <stdio.h>
#include <string.h>

87
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){
88
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int i;

/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);

// remove one item

int num = removeData();
printf("\nElement removed: %d\n",num);
printf("Updated Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
Output
Queue: 3 5 9 1 12 15
Element removed: 3
Updated Queue: 5 9 1 12 15

The peek() Operation

The peek() is an operation which is used to retrieve the frontmost element

in the queue, without deleting it. This operation is used to check the status
of the queue with the help of the pointer.
89
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

Algorithm

1. START
2. Return the element at the front of the queue
3. END

Example

Following are the implementations of this operation in various

programming languages −

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
90
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

itemCount++;
}
}
int main(){
int i;

/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("\nElement at front: %d\n",peek());
}
Output
Queue: 3 5 9 1 12 15
Element at front: 3

The isFull() Operation

The isFull() operation verifies whether the stack is full.

Algorithm

1. START
2. If the count of queue elements equals the queue size,
return true
3. Otherwise, return false

91
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

4. END

Example

Following are the implementations of this operation in various

programming languages −

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
int i;
/* insert 5 items */
insert(3);
92
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("\n");
if(isFull()) {
printf("Queue is full!\n");
}
}
Output
Queue: 3 5 9 1 12 15
Queue is full!

The isEmpty() operation

The isEmpty() operation verifies whether the stack is empty. This operation
is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the count of queue elements equals zero, return true
3. Otherwise, return false
4. END

Example

Following are the implementations of this operation in various

programming languages −
93
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

C C++JavaPython

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isEmpty(){
return itemCount == 0;
}
int main(){
int i;
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("\n");
if(isEmpty()) {
printf("Queue is Empty!\n");
}
}
Output
Queue: 0 0 0 0 0 0
Queue is Empty!

Complete Implementation

Following are the complete implementations of Queue in various

programming languages −

94
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

C C++JavaPython

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
95
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){

/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue size: %d", size());
printf("\nQueue: ");
for(int i = 0; i < MAX; i++){
printf("%d ", intArray[i]);
}
if(isFull()) {
printf("\nQueue is full!");
}

// remove one item

int num = removeData();
printf("\nElement removed: %d", num);
printf("\nSize of Queue after deletion: %d", size());
printf("\nElement at front: %d", peek());
96
 Rajarshi Shahu College Of Engineering,Buldana
Department of Computer Science and Engineering
Session 2023-24
Subject: Data Structure Lab Semester: 3rd

}
Output
Queue size: 6
Queue: 3 5 9 1 12 15
Queue is full!
Element removed: 3
Size of Queue after deletion: 5
Element at front: 5

Conclusion:
In this way we have studied various operations on Queue data structure.

97