SHIVAM

Degree Engineering
A Laboratory Manual for
Data Structures
(3130702)
[ B.E. (COMPUTER ) : Semester - 3 ]
Enrolment No 230160107100
Name PRAJAPATI SHIVAM RAJARAM
Branch COMPUTER
Academic Term 2024-2025

Institute Name GOVERNMENT ENGINEERING COLLEGE, MODASA
Directorate of Technical Education, Gandhinagar, Gujarat

Government Engineering College
Data Structure (3130702) 230160107100
Modasa
Department of C
CERTIFICATE
This is to certify that Mr./Ms. PRAJAPATI SHIVAM RAJARAM
Enrollment No. 230160107103 of B.E. Semester 3 oomutter eeuartment
Engineering of this Instittte (GTU oode: 3330704 ) has satisfactorily comuleted
the Practical.
/ Tttorial work for the stbject DATA STRUCTURE (3130702) for the academic
year 2024 -25
Place:
Date:
Signature of Course Faculty Head of the Department

Data Structure (3130702) 230160107100
Preface
Main motto of any laboratory/practical/field work is for enhancing required skills as well as
creating ability amongst students to solve real time problem by developing relevant competencies
in psychomotor domain. By keeping in view, GTU has designed competency focused outcome-
based curriculum for engineering degree programs where sufficient weightage is given to
practical work. It shows importance of enhancement of skills amongst the students and it pays
attention to utilize every second of time allotted for practical amongst students, instructors and
faculty members to achieve relevant outcomes by performing the experiments rather than having
merely study type experiments. It is must for effective implementation of competency focused
outcomebased curriculum that every practical is keenly designed to serve as a tool to develop and
enhance relevant competency required by the various industry among every student. These
psychomotor skills are very difficult to develop through traditional chalk and board content
delivery method in the classroom. Accordingly, this lab manual is designed to focus on the
industry defined relevant outcomes, rather than old practice of conducting practical to prove
concept and theory.
By using this lab manual students can go through the relevant theory and procedure in advance
before the actual performance which creates an interest and students can have basic idea prior to
performance. This in turn enhances pre-determined outcomes amongst students. Each experiment
in this manual begins with competency, industry relevant skills, course outcomes as well as
practical outcomes (objectives). The students will also achieve safety and necessary precautions
to be taken while performing practical.
This manual also provides guidelines to faculty members to facilitate student centric lab activities
through each experiment by arranging and managing necessary resources in order that the
students follow the procedures with required safety and necessary precautions to achieve the
outcomes. It also gives an idea that how students will be assessed by providing rubrics.
Data Structures is a core course in all computer science undergraduate curricula. The course is
the basis for understanding several data structures and also algorithms that operate on them. The
course forms the foundation for almost all computer science subjects: compilers, operating
systems, databases, AI and software engineering. The course comes with a lab in most universities
in India. The associated lab in university curricula focuses on implementation of algorithms
operating on the data structures, i.e., coding programs on the data structures and algorithms.
Data Structure (3130702) 230160107100
 DTE’s Vision
 To provide globally competitive technical education

 Remove geographical imbalances and inconsistencies
 Develop student friendly resources with a special focus on girls’ education and support to weaker
sections
 Develop programs relevant to industry and create a vibrant pool of technical professional
 Institute’s Vision
 To be a leading institution ensuring Academic Excellence, Research, Nurturing Innovation and Attitude
to produce competent technocrats for service to Nation.
 Department’s Vision
 To become a prominent department of Computer Engineering producing Competent professionals with

research, innovation and entrepreneurial skills, inculcating moral values and societal concerns.
 Department’s Mission
 To create globally competent students having the ability to design, develop and test world class
software, keeping pace with the latest technological developments.
 Create facilities and expertise in advanced computer technology thereby promote research.
 Enhance Industry Institute Interaction program to get acquainted with corporate culture.
 Induce moral, ethical values and spirit of social commitment.
Programme Outcomes (POs)

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.
2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of mathematics,
natural sciences, and engineering sciences.
3. Design/development of solutions: Design solutions for complex engineering problems and
design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
considerations.
4. Conduct investigations of complex problems: Use research-based knowledge and research
methods including design of experiments, analysis and interpretation of data, and synthesis of
the information to provide valid conclusions.
Data Structure (3130702) 230160107100
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering activities
with an understanding of the limitations.
6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess
societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to
the professional engineering practice.
7. Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and need
for sustainable development.
8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of the engineering practice.
9. Individual and team work: Function effectively as an individual, and as a member or leader
in diverse teams, and in multidisciplinary settings.
10. Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and write
effective reports and design documentation, make effective presentations, and give and receive
clear instructions.
11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member and
leader in a team, to manage projects and in multidisciplinary environments.
12. Life-long learning: Recognize the need for, and have the preparation and ability to engage in
independent and life-long learning in the broadest context of technological change
▪ Program Educational ctives (PEOs) :-
Obje
▪ An ability to effectively integrate IT-based solutions into the user environment.

Management
de ▪ Possess professional skill set of software design process using open source technologies. innovative
▪ Apply concepts of core areas of Information Technology– Data Structures, Database solutions.
Systems, Operating Systems, Computer Network and Software Engineering to provi
▪ Program Educational Objectives (PEOs) :-

▪ Be prepared to gain employment as a successful IT professional and/or pursue higher
▪ studies.
▪ Be capable to adapt advanced state of the art Information technology for professional
excellence and Research and be a lifelong learner.
Data Structure (3130702) 230160107100
▪ Work productively exhibiting ethical qualities for the betterment of society.
▪ Possess leadership and entrepreneurial qualities, work harmoniously as a team member
with effective communication skills.
Practical – Course Outcome matrix
Course Outcomes (COs)

Define and classify various data structures, storage structures and common
CO_3130702.1 operations on them
Create various linear data structures with their representation and perform
CO_3130702.2 different operations on them
Create various nonlinear data structures with their representation and perform
CO_3130702.3 different operations on them
CO_3130702.4 Apply various searching sorting techniques on data set
Solve the given a problem using an appropriate data structure to achieve

CO_3130702.5 optimal performance and compare its performance with other possible data
structures
Sr. CO CO CO CO CO
No. Practical Outcome/Title of experiment
1 2 3 4 5
1. Classification of Data Structure and Stack
1.1 Classify various data structures

1.2 Implement a program for stack that performs
following operations using array. (a) PUSH (b) POP
(c) PEEP (d) CHANGE (e) DISPLAY
1.3 Implement a program to convert infix notation to √
postfix notation using stack. √ √
1.4 Write a program to implement Tower of Hanoi
problem.
1.5 Identify widely used application which use stack data
structure for implementation of its important feature.
2. Queue
Data Structure (3130702) 230160107100
2.1 Write a program to implement QUEUE using arrays
that performs following operations (a) INSERT (b)
DELETE (c) DISPLAY
2.2 Write a program to implement Circular Queue using
arrays that performs following operations. (a) √ √
INSERT (b) DELETE (c) DISPLAY
2.3 Identify widely used application which use Queue
data structure for implementation of its important
feature.
3. Singly linked list
3.1 Write a menu driven program to implement

following operations on the singly linked list. √ √
(a) Insert a node at the front of the linked list.

(b) Insert a node at the end of the linked list.
(c) Insert a node such that linked list is in ascending
order.(according to info. Field)
(d) Delete a first node of the linked list. (e) Delete a
node before specified position. (f) Delete a node
after specified position.
3.2 Write a program to implement stack using linked list.
3.3 Write a program to implement queue using linked
list.
4. Doubly linked list
4.1 Write a program to implement following

operations on the doubly linked list.
√ √
(c) Delete a last node of the linked list.
(d) Delete a node before specified position.
5. Circular linked list

Data Structure (3130702) 230160107100
5.1 Write a program to 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.
5.2 Identify widely used application which use Linked
List for implementation of its important feature.
6. Tree
6.1 Write a program which create binary search tree.

6.2 Implement recursive tree traversing methods
inorder, pre-order and post-order traversal
√ √
6.3 Identify widely used application which use Tree data
structure for implementation of its important feature.
7. Graph
7.1 Write a program to perform BFS and DFS on given

graph.
7.2 Identify widely used application which use Graph √ √
data structure for implementation of its important
feature.
8. Searching
8.1 Write a program to implement Linear Search.

8.2 Write a program to implement Binary Search.
8.3 Identify widely used application which use √ √
Searching technique for implementation of its
important feature.
9. Sorting
Data Structure (3130702) 230160107100
9.1 Write a program to implement Quick Sort √
9.2 Write a program to implement Merge Sort
9.3 Write a program to implement Bubble Sort
9.4 Identify widely used application which use Sorting
technique for implementation of its important
feature.
10 Hashing and File Structure
10.1 Write a program to create hash table and handle the

collision using linear probing.
10.2 Write a program to demonstrate the file primitives
such as fopen, fclose, fprintf. √ √
10.3 Identify widely used application which use
Hashing technique for implementation of its
important feature.
Industry Relevant Skills
The following industry relevant competencies are expected to be developed in the student by
undertaking the practical work of this laboratory.
1. Will be able to classify data structures and identify storage representation of primitive and
nonprimitive data structures
2. Will be able to implement various operations on Stack, Queue, Link list, Tree, Graph, Hashing
and File operations.
3. Will be able to understand need of sorting and searching for various applications
4. Will be able to apply various data structure to design real time applications in efficient manner.
Guidelines for Faculty members
1. Teacher should provide the guideline with demonstration of practical to the students with all
features.
2. Teacher shall explain basic concepts/theory related to the experiment to the students before
starting of each practical
3. Involve all the students in performance of each experiment.
Data Structure (3130702) 230160107100
4. Teacher is expected to share the skills and competencies to be developed in the students and
ensure that the respective skills and competencies are developed in the students after the
completion of the experimentation.
5. Teachers should give opportunity to students for hands-on experience after the demonstration.
6. Teacher may provide additional knowledge and skills to the students even though not covered
in the manual but are expected from the students by concerned industry.
7. Give practical assignment and assess the performance of students based on task assigned to
check whether it is as per the instructions or not.
8. Teacher is expected to refer complete curriculum of the course and follow the guidelines for
implementation.
Instructions for Students
1. Students are expected to carefully listen to all the theory classes delivered by the faculty
members and understand the COs, content of the course, teaching and examination scheme, skill
set to be developed etc.
2. Students will have to perform experiments on computer system on which C/C++ compiler is
installed to execute programs of data structure.
3. Students should develop programs and execute all the programs using C/C++ compiler. Students
have to show output of each program in their practical file.
4. Students are instructed to submit practical list as per given sample list shown on next page.
5. Student should develop a habit of submitting the experimentation work as per the schedule and
s/he should be well prepared for the same.
Common Safety Instructions
Students are expected to
1. switch on the PC carefully (not to use wet hands)

2. shutdown the PC properly at the end of your Lab
3. carefully handle the peripherals (Mouse, Keyboard, Network cable etc)
4. use Laptop in lab after getting permission from Teacher
5. carefully handle all lab resources
Index
(Progressive Assessment Sheet)
Date
of Date of Assessme Sign. of
Sr. Objective(s) of Experiment Page Remar
No. No. perfor submiss nt Teacher
mance ion Marks with date ks
Data Structure (3130702) 230160107100
1. Classification of Data Structure and Stack

1.2 Implement a program for stack that
performs following operations using array.
(a) PUSH (b) POP (c) PEEP (d) CHANGE
(e) DISPLAY
1.3 Implement a program to convert infix
notation to postfix notation using stack.
1.4 Write a program to implement Tower of
Hanoi problem.
stack data structure for implementation of
its important feature.
2. Queue
2.1 Write a program to implement QUEUE

using arrays that performs following
operations (a) INSERT (b) DELETE (c)
DISPLAY
2.2 Write a program to implement Circular
Queue using arrays that performs following
operations. (a) INSERT (b) DELETE (c)
DISPLAY
Queue data structure for implementation of
3. Singly linked list
3.1 Write a menu driven program to implement

following operations on the singly linked
list.
(a) Insert a node at the front of the linked
list.
(b) Insert a node at the end of the linked
list.
(c) Insert a node such that linked list is in
ascending order.(according to info.
Field)
Data Structure (3130702) 230160107100
(d) Delete a first node of the linked list.
(e) Delete a node before specified
position.
(f) Delete a node after specified position.
3.2 Write a program to implement stack using
linked list.
3.3 Write a program to implement queue
using linked list.
4. Doubly linked list

operations on the doubly linked list. (a) list. list.
Insert a node at the front of the (b) linked
Insert a node at the end of the linked
(c) Delete a last node of the linked list.
(d) Delete a node before
specified position.
5. Circular linked list

operations on the circular linked list.
(a) Insert a node at the end of the linked
list.
(b) Insert a node before specified
position.
Linked List for implementation of its
important feature.
6.
Tree
6.1 Write a program which create binary
search tree.
6.2 Implement recursive tree traversing
methods in-order, pre-order and post-order
traversal.
Tree data structure for implementation of
Data Structure (3130702) 230160107100
7. Graph
7.1 Write a program to perform BFS and DFS

on given graph.

Graph data structure for implementation of
8. Searching
8.1 Write a program to implement Linear
Search.
8.2 Write a program to implement Binary
Search.
8.3 Identify widely used application which
use Searching technique
for implementation of its important feature.
9. Sorting
9.1 Write a program to implement Quick Sort
use Sorting technique for implementation of
10. Hashing and File Structure

10.1 Write a program to create hash table and
handle the collision using linear probing.
10.2 Write a program to demonstrate the file
primitives such as fopen, fclose, fprintf.
use Hashing technique for implementation
of its important feature.
Total
Data Structure (3130702) 230160107100
Experiment No – 1
AIM : Classification of Data Structure and Stack

1.2 Implement a program for stack that performs following operations using array. (a) PUSH (b) POP
(c) PEEP (d) CHANGE (e) DISPLAY
1.3 Implement a program to convert infix notation to postfix notation using stack.
1.4 Write a program to implement Tower of Hanoi problem.
1.5 Identify widely used application which use stack data structure for implementation of its important
feature.
Date:
Competency and Practical Skills: Logic building and programming
Relevant CO: CO1, CO2, CO5
Objectives: (a) To analyze various data structures

(b) To understand the concepts of stack
(c) To implement various applications of the stack
Equipment/Instruments: Computer System with C/C++ compiler
Safety and necessary Precautions:
Operate computer system carefully and responsibly. Use required

lab resources cautiously
Theory:
Data Structure
Data structures are a fundamental concept in computer science that enable efficient storage and
manipulation of data. They are used to organize and store data in a manner that allows for optimal
performance of algorithms. The selection of a suitable data structure begins with the choice of an
abstract data type, which defines the operations that can be performed on the data. Well-designed
data structures can perform a wide range of critical operations while using minimal resources such
14
Data Structure (3130702) 230160107100
as execution time and memory space. In essence, data structure introduction refers to the
arrangement of data in a computer's memory in a way that enables rapid access by the processor for
the required calculations.
Stack
A stack is a data structure that follows the last-in first-out (LIFO) principle, meaning that objects
are inserted and removed from the container in a particular order. In pushdown stacks, only two
operations are allowed: pushing an item onto the stack, and popping an item off the top of the stack.
Access to the stack is limited, as elements can only be added and removed from the top. When an
item is pushed onto the stack, it becomes the new top item. Conversely, when an item is popped off
the stack, it is removed from the top.
To illustrate this concept, consider a stack of books. Just as you can only remove the top book, you
can only add a new book to the top of the stack. A stack can also have a limited capacity. If the
stack is already full and there is no space to add a new item, it is said to be in an overflow state. On
the other hand, if the stack is empty and an item is removed, it is in an underflow state, meaning
that no items are present in the stack to be removed.
A stack is an abstract data structure that operates on the LIFO principle, where the last item added
is the first item to be removed. Items can be inserted and deleted at one end called the top, creating
a structure that resembles a closed tube on one side.
The add operation of the stack is called push operation The delete operation is called as
pop operation.
Push operation on a full stack causes stack overflow.
Pop operation on an empty stack causes stack underflow. SP is a
pointer, which is used to access the top element of the stack.
If you push elements that are added at the top of the stack; In the same way when we pop the
elements, the element at the top of the stack is deleted.
There are two operations applied on stack they are
(1) PUSH
(2) POP
In-fix- to Postfix Conversion:
Procedure to convert from infix expression to postfix expression is as follows:
1. Start scanning the infix expression from left to right.

2. If the symbol scanned is a left parenthesis, push it onto the stack. 3. If the scanned
symbol is an operand, place it directly into the postfix expression output.
15
Data Structure (3130702) 230160107100
4. If the symbol scanned is a right parenthesis, continue to pop all items from the stack and place
them into the postfix expression output until a matching left parenthesis is found.
5. If the scanned symbol is an operator, remove all operators from the stack and place them in the
postfix expression output if and only if the precedence of the operator on top of the stack is
greater than or equal to the precedence of the scanned operator. Then push the scanned operator
onto the stack; otherwise, push the scanned operator onto the stack.
1.1 Classify various data structures Classification
of Data Structures:
Data structures can be classified as
1. Primitive data structure

2. Non-Primitive data structure (a) Linear data structure (b) Non-linear data structure
1. Primitive data structures: Primitive data structures are simple data structures
constructed using the standard data types of a computer language. Examples of primitive
data structures include variables, arrays, pointers, structures, unions, and more. These
structures are used to build more complex data structures
2. Non-primitive data structures: Non-primitive data structures are constructed using

primitive data structures and have specific functionality. They can be designed by a user
and are classified into two categories: linear data structures and non-linear data structures.
(a) Linear data structures
Linear data structures are arranged as a continuous set of data elements in the memory
and can be constructed using array data types. In linear data structures, the adjacency
relationship between data elements is maintained.
Operations applied on linear data structure:
The following list of operations applied on linear data structures
Add an element
Delete an element
Traverse
Sort the list of elements Search for a data element
Examples of linear data structure
16
Data Structure (3130702) 230160107100
Stack
Queue Tables
List Linked
Lists.
(b) Non-linear Data Structure:
Non-linear data structures are not arranged in a continuous manner and include data
structures such as trees and graphs. These structures can be used to represent complex
relationships between data elements.
Operations applied on non-linear data structures:
The following list of operations applied on non-linear data structures.
Add elements
Delete elements
Display the elements
Sort the list of elements Search for a data element
Examples of non-linear data structure
Tree
Decision tree
Graph Forest
1.2 Implement a program for stack that performs following operations using array. (a)
PUSH (b) POP (c) PEEP (d) CHANGE (e) DISPLAY
Program:
#include<stdio.h>
#define size 5
struct stack
{ int a[size],top; int temp[size];
}s;
// PUSH Operation void push()

{ int value; printf(" Enter value to be pushed:
"); scanf("%d", &value); s.top = s.top +
1;
s.a[s.top] = value;
17
Data Structure (3130702) 230160107100
}
// POP Operation void pop()
{ printf(" Popped element is %d\n", s.a[s.top]); s.top
= s.top - 1; }
// PEEP Operation void peep()

{ printf(" The value at top position is : %d\n", s.a[s.top]); }
// DISPLAY Operation void

display()
{ int i; printf(" The stack contains: "); for(i=s.top;
i>=0; i--)
{ printf("\t%d", s.a[i]);
}
printf("\n");
}
// CHANGE Operation
void change(int index, int new_element)

{ int i, j=-1;
for(i=s.top; i>index; i--)
{
s.temp[++j] = s.a[s.top--];
}
s.a[s.top] = new_element; for(i
= j; i>-1; i--)
{
s.a[++s.top] = s.temp[j--]; } }
void main()
{
s.top = -1; int choice, index,
new_element; do
{
printf("\n STACK IMPLEMENTATION PROGRAM"); printf("\n 1. PUSH
2. POP 3. PEEP 4. CHANGE 5. DISPLAY 0. EXIT\n"); printf("\n
Enter your choice: "); scanf("%d", &choice);
switch(choice) {
case 1:
if(s.top == size-1)
{
printf("\tSTACK OVERFLOW\n");
} else
18
Data Structure (3130702) 230160107100
{
push();
}
break;
case 2: if(s.top == -1)
{
printf("\tSTACK UNDERFLOW\n");
} else
pop();
}
break;
case 3: if(s.top == -1)
{ printf("\tStack is empty.\n");
} else
peep();
}
break;
case 4:
printf(" Enter index no : ");
scanf("%d",&index); if(index<0 || index>s.top)
{
printf("\tINVALID INDEX NUMBER\n");
} else
{ printf(" Enter new

element: ");
scanf("%d", &new_element); change(index, new_element); }
break;
case 5: if(s.top == - 1)
{
printf("\t Stack is empty.\n");
} else
19
Data Structure (3130702) 230160107100
{
display();
}
break;
case 0:
printf("\tEND OF
PROGRAM"); break; default :
printf("\tINVALID CHOICE\n");
}
} while(choice != 0); Output:
1.3 Implement a program to convert infix notation to postfix notation using stack.
Program:
#include <stdio.h> #include

<stdlib.h>
#include <conio.h> #include
<ctype.h>
#include <string.h>
#define MAX 20
20
Data Structure (3130702) 230160107100
char st[MAX];
int top=-1;
void push(char st[], char); char pop(char st[]);
void InfixtoPostfix(char source[], char target[]); int
getPriority(char);
int main()
{ char infix[100], postfix[100]; printf("\n Enter any infix

expression : ");
scanf("%s",infix); strcpy(postfix, "");
InfixtoPostfix(infix, postfix); printf("\n The
corresponding postfix expression is :
"); puts(postfix); getch(); return
0; }
void InfixtoPostfix(char source[], char target[])

{
int i=0, j=0; char temp;
strcpy(target,
""); while(source[i]!='\0'
)
{ if(source[i]=='(')
{ push(st, source[i]); i++;
} else if(source[i] ==
')')
{ while((top!=-1) &&
(st[top]!='('))
{ target[j] = pop(st); j++;
}
if(top==-1)
{
printf("\n INCORRECT EXPRESSION");exit(1);
} temp = pop(st);//remove left parenthesis
i++;
} else if(isdigit(source[i]) ||
isalpha(source[i]))
{ target[j] = source[i]; j++; i++;
} else if (source[i] == '+' || source[i] == '-' || source[i] == '*' || source[i] == '/' || source[i] ==
'%') { while( (top!=-1) && (st[top]!= '(') && (getPriority(st[top]) >= getPriority(source[i]))) {
target[j] = pop(st); j++;
} push(st, source[i]); i++; } else
{ printf("\n INCORRECT ELEMENT IN
21
Data Structure (3130702) 230160107100
EXPRESSION");exit(1);
}
} while((top!=-1) &&
(st[top]!='('))
{ target[j] = pop(st); j++;
}
target[j]='\0';
int getPriority(char op)

{ if(op=='/' || op == '*' || op=='%')
return 1; else if(op=='+' || op=='-')
return 0;
}
void push(char st[], char val)
{
if(top==MAX-1)
{
printf("\n STACK OVERFLOW");
} else
{ top++; st[top]=val
;
}
}
char pop(char st[])

{ char val=' '; if(top==-1) {
printf("\n STACK UNDERFLOW");
} else
{ val=st[top]; top--
;
}
return val;
}
Output:
22
Data Structure (3130702) 230160107100
1.4 Write a program to implement Tower of Hanoi problem.
Program:
#include <stdio.h> void
main()
{ int n; printf("\n Enter the number of rings: "); scanf("%d",

&n); move(n,'A',
'C', 'B');
} void move(int n, char source, char dest, char spare)
{ if (n==1) printf("\n Move from %c to %c",source,dest); else
{ move(n-1, source, spare, dest);
move(1, source, dest, spare); move(n-1, spare, dest,
source);
}
}
Output:
1.5 Identify widely used application which use stack data structure for implementation of its
important feature.
Stack Applications:
23
Data Structure (3130702) 230160107100
1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form. 4. In recursion, all
intermediate arguments and return values are stored on the processor’s stack.
5. During a function call the return address and arguments are pushed onto a stack and on return
they are popped off. 6. Depth first search uses a stack data structure to find an element from a
graph.
Conclusion:
Data structures are vital for efficient data organization and manipulation, enhancing algorithm
performance while minimizing resource usage. Choosing the right structure, whether linear (like
stacks and queues) or non-linear (like trees and graphs), is key to optimizing computational tasks.
Quiz:
(1) List various stack operations
Push: Add an element to the top of the stack.

Pop: Remove and return the top element from the stack.
Peek/Top: View the top element of the stack without removing it. isEmpty: Check
whether the stack is empty. isFull: Check whether the stack has reached its maximum
capacity (in case of a bounded stack).
Size: Return the number of elements currently in the stack.
(2) Differentiate FIFO and LIFO
Criteria FIFO (First In, First Out) LIFO (Last In, First Out)
Order The first element added is the first The last element added is the first
one removed (e.g., Queue). one removed (e.g., Stack).
Data Structure Queue (uses FIFO principle) Stack (uses LIFO principle)
24
Data Structure (3130702) 230160107100
Use Cases Used in scheduling tasks, buffering, Used in undo mechanisms,
managing tasks in order. function call management,
recursive algorithms.
Real-world Waiting in a line (first person in Stack of plates (you take the plate
Analogy line is served first). from the top).
(3) Explain infix, prefix and postfix expressions

Infix Expression: The operator is placed between the operands.
• Example: A + B
• Human-readable, and the most common way of writing expressions.
• Requires parentheses and operator precedence for evaluation.
Prefix Expression (Polish Notation): The operator is placed before the operands. • Example: +
AB
• No need for parentheses, as the order of operations is clear based on the position of operators.
• Easier for computers to parse than infix.
Postfix Expression (Reverse Polish Notation): The operator is placed after the operands.
•
Example: A B + • Also does not need parentheses or
precedence rules.
• Commonly used in stack-based calculators and evaluation algorithms.
Suggested Reference:
1. An Introduction to Data Structures with Applications. by Jean-Paul Tremblay & Paul G.

Sorenson Publisher-Tata McGraw Hill.
2. Data Structures using C & C++ -By Ten Baum Publisher – Prenctice-Hall International 3.
Fundamentals of Computer Algorithms by Horowitz, Sahni,Galgotia Pub. 2001 ed.
4. http://www.geeksforgeeks.org/data-structures/
5. http://www.coursera.org/specializations/data-structures-algorithms
References used by the students: Data

structure using c.
Rubric-wise marks obtained:
25
Data Structure (3130702) 230160107100
Problem Coding Completeness
Logic
Understanding Standards and accuracy Q&A
Building (2)
Rubrics (2) (2) (2) Total
Avg. Good Avg. Good Avg. Good Avg. Good Avg. Good
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
Experiment No: 2
AIM : Queue
2.1 Write a program to implement QUEUE using arrays that performs following
operations (a)INSERT (b) DELETE (c) DISPLAY
2.2 Write a program to implement Circular Queue using arrays that performs following
operations. (a) INSERT (b) DELETE (c) DISPLAY
2.3 Identify widely used application which uses Queue data structure for implementation
Date:
Relevant CO: CO2, CO5
Objectives: (a) To understand the concepts of Queue

(b) To analyze different algorithms on Queue
(c) To implement various operations on Queue
Equipment/Instruments: Computer System with turbo C/C++
Operate computer system carefully and responsibly. Use

required lab resources cautiously
Theory:
Queue
26
Data Structure (3130702) 230160107100
A queue is a data structure that follows the First In, First Out (FIFO) principle. It is a special type
of list where items are inserted at the rear and deleted from the front end. Queues can be compared
to real-world scenarios, such as people waiting in line at a bank.
There are various types of Queue in data structure
Queue Circular
Queue
D-Queue
Priority Queue
2.1 Write a program to implement QUEUE using arrays that performs following
operations. (a)INSERT (b) DELETE (c) DISPLAY
Program:
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
// Function to insert an element into the queue void

insert(int value) { if (rear ==
MAX - 1) { printf("Queue
Overflow\n");
} else { if
(front == -1) { front = 0; // Set front to 0 if inserting the first element
} rear++;
queue[rear] = value; printf("%d inserted into the queue\n",
value);
} }
// Function to delete an element from the queue void

delete() { if (front == -1 || front
> rear) { printf("Queue Underflow\n");
} else { printf("%d deleted from the queue\n",
queue[front]); front++; if (front > rear) { // Reset the queue when
empty front = rear = -1;
}
} }
27
Data Structure (3130702) 230160107100
// Function to display the elements of the
queue void display() { if (front == -1) {
printf("Queue is empty\n");
} else { printf("Queue elements are:
");
for (int i = front; i <= rear; i++) { printf("%d
", queue[i]); }
printf("\n");
} }
int main() { int choice, value;

while (1) {
printf("\nQueue
Operations:\n"); printf("1.
Insert\n2.
Delete\n3. Display\n4.
Exit\n");
printf("Enter your
choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the value to insert:
"); scanf("%d", &value); insert(value);
break; case 2: delete(); break; case 3:
display(); break; case 4: return 0; default:
printf("Invalid choice\n");
}
}
28
Data Structure (3130702) 230160107100
}
Output:
2.2 Write a program to implement Circular Queue using arrays that performs following
operations. (a) INSERT (b) DELETE (c) DISPLAY
Program:
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
// Function to insert an element into the circular queue void insert(int value) {
if ((front == 0 && rear == MAX - 1) || (rear == (front - 1) % (MAX - 1))) {
printf("Queue Overflow\n");
} else { if (front == -1) { // First element insertion
front = rear = 0;
} else if (rear == MAX - 1 && front != 0) { rear =
0; // Wrap around to the beginning
} else
29
Data Structure (3130702) 230160107100
{ rear++; } queue[rear] = value; printf("%d
inserted into the queue\n", value); } }
// Function to delete an element from the circular

queue void delete() { if (front == -1) { printf("Queue
Underflow\n");
} else { printf("%d deleted from the queue\n", queue[front]);
if (front == rear) { // Queue is empty after deletion front
= rear = -1;
} else if (front == MAX - 1) { front
= 0; // Wrap around
} else { front++;
}
} }
// Function to display the elements of the

circular queue void display() { if (front == -1) {
printf("Queue is empty\n"); return;
} printf("Queue elements are: ");
if (rear >= front) { for (int i =
front; i <= rear; i++) { printf("%d ",
queue[i]);
}
} else { for (int i = front; i <
MAX; i++) { printf("%d ",
queue[i]);
}
for (int i = 0; i <= rear; i++) {
printf("%d ", queue[i]);
} }
printf("\n");
}
int main() { int choice,

value;
while (1) { printf("\nCircular Queue

Operations:\n"); printf("1. Insert\n2. Delete\n3. Display\n4.
Exit\n"); printf("Enter your choice: "); scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the value to insert:
"); scanf("%d", &value); insert(value);
30
Data Structure (3130702) 230160107100
break; case 2: delete(); break; case 3:
display(); break; case 4: return 0; default:
printf("Invalid choice\n");
}
}
}
Output:
31
Data Structure (3130702) 230160107100
2.3 Identify widely used application which uses Queue data structure for implementation
One of the most widely used applications of the queue data structure is in printer spooling. In printer
spooling, documents that are to be printed are placed in a queue, and the printer processes them in a
32
Data Structure (3130702) 230160107100
FirstIn-First-Out (FIFO) order. Each job waits its turn, ensuring that the first job sent to the printer is
printed first, followed by subsequent jobs in the order they were received.
Other examples include:
• CPU task scheduling: Processes waiting to be executed are managed in a queue.

• Breadth-First Search (BFS) in graph traversal.
• Operating system I/O buffering: For managing incoming and outgoing data streams.
Conclusion:
A circular queue improves upon the limitations of a linear queue by efficiently utilizing memory through
its wrap-around mechanism, allowing the rear to loop back to the start when space is available. This
structure maintains the First-In-First-Out (FIFO) principle and is commonly used in applications like CPU
scheduling and network buffering. Unlike a linear queue, which can waste space after elements are
deleted, a circular queue ensures continuous, efficient use of available memory. Quiz:
(1) Explain concepts of Queue

A queue is a linear data structure that operates on the First-In-First-Out (FIFO) principle,
where the first element inserted is the first one to be removed. Elements are added at the
rear of the queue and removed from the front. This structure is used in various applications
such as task scheduling, buffering, and managing resources like CPU processes or printer
tasks. Queues are efficient for handling processes that need to be executed in a sequential
order, maintaining the order of requests.
(2) Define DQueue

A DQueue (Double-Ended Queue) is a type of queue that allows insertion and deletion of
elements at both the front and rear ends. Unlike a regular queue where elements are added
at the rear and removed from the front, a DQueue provides greater flexibility, enabling
operations at both ends. DQueues are used in applications like managing buffers, undo
operations, and in certain algorithms like the sliding window problem.
(3) Differentiate Circular Queue and Priority Queue
Circular Queue Priority Queue
A circular queue is a queue in which the last A priority queue is a queue where each element is
position is connected to the first, forming a circle. associated with a priority. Elements are removed
This allows the queue to reuse empty spaces created based on their priority, not necessarily in the order
by the removal of elements, making better use of they were inserted (higher-priority elements are
memory. dequeued first).
Operates on the FIFO principle but with circular Operates based on priority rather than FIFO, where
memory management. the highest-priority elements are processed first.
33
Data Structure (3130702) 230160107100
Used in scenarios like circular buffers and resource Used in scheduling systems, like CPU job
scheduling. scheduling, where tasks with higher priority are
executed first.
Insertion and deletion follow the FIFO order with Insertion order can differ from removal order based
wrap-around. on priority levels.
1. An Introduction to Data Structures with Applications. by Jean-Paul Tremblay & Paul G. Sorenson
Publisher-Tata McGraw Hill.
2. Data Structures using C & C++ -By Ten Baum Publisher – Prenctice-Hall International


Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
Experiment No: 3
AIM : Singly linked list
3.1 Write a menu driven program to implement following operations on the singly linked
list.
(c) Insert a node such that linked list is in ascending order. (According to INFO field)
(e) Delete a node before specified position. (f)
Delete a node after specified position.
34
Data Structure (3130702) 230160107100
3.2 Write a program to implement stack using linked list 3.3 Write
a program to implement queue using linked list.
Date:
Objectives: (a) To understand the concepts of singly linked list

(b) To analyze different algorithms on singly link list
(c) To implement various operations on singly link list

Theory: Singly link list
A linked list is a type of data structure that stores a collection of non-sequential data items. Unlike
arrays, linked lists are dynamic and their size can be changed during program execution. Each data
item in a linked list has a pointer that holds the memory address of the next data item in the list. The
data items in a linked list may not be stored in consecutive memory locations, but their pointers
make it easy to access them in any order.
A singly linked list, also known as a linear linked list, is a type of linked list in which all nodes are
connected together sequentially. Each node in a singly linked list contains data and a pointer to the
next node. The last node's pointer is set to null. The limitation of a singly linked list is that it can
only be traversed in one direction, in a forward direction.
Operations on singly linked list
Insert
- Insert at first position
- Insert at last position
- Insert into ordered list Delete
Traverse list (Print list) Copy linked list
35
Data Structure (3130702) 230160107100
3.1 Write a menu driven program to implement following operations on the singly linked
list.
(c) Insert a node such that linked list is in ascending order.(According to INFO field)
(e) Delete a node before specified position. (f)
Delete a node after specified position.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; struct Node*
next;
};
struct Node* head = NULL;
// Function to insert at the front void insertAtFront(int value) { struct

Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->data = value; newNode->next = head; head
= newNode;
printf("%d inserted at the front.\n", value); }
// Function to insert at the end void insertAtEnd(int value) { struct

Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data
= value; newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else { struct Node* temp = head;
while (temp->next != NULL) { temp
= temp->next;
}
temp->next = newNode;
} printf("%d inserted at the end.\n", value);
}
// Function to insert in ascending order void insertInOrder(int value)

{
36
Data Structure (3130702) 230160107100
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value; newNode->next = NULL;
if (head == NULL || head->data >= value) { newNode->next

= head; head = newNode;
while (temp->next != NULL && temp->next->data < value) {
temp = temp->next;
}
newNode->next = temp->next; temp->next
= newNode;
} printf("%d inserted in ascending order.\n", value);
}
// Function to delete the first node

void deleteFirstNode() { if (head
== NULL) {
printf("List is empty.\n");
head = head->next; free(temp);
printf("First node
deleted.\n");
} }
// Function to delete node before a specified position void

deleteBeforePosition(int pos) { if
(head == NULL || pos <= 1) { printf("Invalid position or list
is too short.\n");
return;
}
struct Node *temp = head, *prev = NULL, *del =

NULL; if (pos == 2) { del = head; head = head->next;
free(del); printf("Node before position %d deleted.\n",
pos); return;
} for (int i = 1; i < pos - 1 && temp->next != NULL;
i++)
{ prev = temp; temp = temp->next;
}
if (prev != NULL && prev->next != NULL) {

del = prev;
head = prev->next; free(del); printf("Node deleted before specified
position %d\n", pos);
37
Data Structure (3130702) 230160107100
} else { printf("Invalid
position.\n");
}
}
// Function to delete node after a specified position void

deleteAfterPosition(int pos) { if
(head == NULL) { printf("List is empty.\n"); return; }
struct Node* temp = head;

for (int i = 1; i < pos && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {

printf("No node exists after position %d.\n", pos); }
else {
struct Node* del = temp->next; temp-
>next = del->next; free(del); printf("Node after position %d
deleted.\n", pos);
} }
// Function to display the linked

list void displayList() { if
(head == NULL) { printf("List
is empty.\n"); return; } struct
Node* temp = head;
printf("Linked List: "); while (temp !=
NULL) { printf("%d -
> ", temp->data); temp = temp>next;
}
printf("NULL\n");
}
int main() { int choice, value, pos; while (1) { printf("\nMenu:\n"); printf("1. Insert at Front\n2. Insert
at End\n3. Insert in Ascending Order\n4. Delete First Node\n5. Delete Before Position\n6.
Delete After Position\n7. Display List\n8. Exit\n"); printf("Enter your choice: "); scanf("%d",
&choice);
switch (choice) {
case 1:
printf("Enter value to insert at front: ");
38
Data Structure (3130702) 230160107100
scanf("%d", &value);
insertAtFront(value);
break;
case 2:
printf("Enter value to insert at end: ");
scanf("%d", &value); insertAtEnd(value);
break; case
3:
printf("Enter value to insert in ascending order:
"); scanf("%d", &value);
insertInOrder(value); break;
case 4:
deleteFirstNode();
break;
case 5:
printf("Enter position before which to delete:
"); scanf("%d", &pos); deleteBeforePosition(pos);
break;
case 6:
printf("Enter position after which to delete:
"); scanf("%d", &pos); deleteAfterPosition(pos);
break;
case 7: displayList();
break; case 8:
exit(0);
default: printf("Invalid choice.\n");
} }
return 0;
} O u
t
p
39
Data Structure (3130702) 230160107100
u
t:
40
Data Structure (3130702) 230160107100
3.2 Write a program to implement stack using linked list
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct
Node* next; };
struct Node* top = NULL;
// Function to push an element onto the stack void push(int

value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->data = value; newNode->next = top; top =
newNode;
printf("%d pushed to stack.\n", value);
}
// Function to pop an element from the

stack void pop() { if (top == NULL) {
printf("Stack Underflow\n");
} else { struct Node* temp
41
Data Structure (3130702) 230160107100
= top; top = top->next; printf("%d popped from
stack.\n", temp->data); free(temp);
} }
// Function to display stack elements

void displayStack() { if (top ==
NULL) { printf("Stack is empty\n");
} else { struct Node* temp = top;
printf("Stack elements are: ");
while (temp != NULL) { printf("%d
-> ", temp->data); temp = temp-
>next;
}
printf("NULL\n");
} }
int main() {
int choice, value;
while (1) {
printf("\nStack Operations:\n"); printf("1. Push\n2.
Pop\n3. Display Stack\n4. Exit\n");
printf("Enter your choice: "); scanf("%d",
&choice);
switch (choice) {
case 1:
printf("Enter value to push:
"); scanf("%d", &value);
push(value); break; case 2:
pop(); break; case 3:
displayStack();
break; case 4: exit(0); default:
printf("Invalid choice.\n");
} } return 0;
}
Output:
42
Data Structure (3130702) 230160107100
3.3 Write a program to implement queue using linked list.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
43
Data Structure (3130702) 230160107100
int data; struct
Node* next;
};
struct Node* front = NULL; struct Node*

rear = NULL;
// Function to insert an element into the queue void enqueue(int value)

{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode-
>data = value; newNode->next
= NULL;
if (rear == NULL) {
front = rear = newNode;
} else { rear->next = newNode;
rear = newNode;
}
printf("%d enqueued to queue.\n", value); }
// Function to delete an element from the queue void

dequeue() { if (front == NULL)
{ printf("Queue Underflow\n");
= front; front = front->next;
if (front == NULL) {
rear = NULL;
}
printf("%d dequeued from queue.\n", temp->data);
free(temp);
}
}
// Function to display the queue

void displayQueue() { if (front
== NULL) { printf("Queue is
empty\n");
= front; printf("Queue elements are:
"); while (temp != NULL) {
printf("%d -> ", temp-
>data); temp = temp->next;
}
printf("NULL\n");
44
Data Structure (3130702) 230160107100
}
}
int main() { int

choice, value;
while (1) {
printf("\nQueue Operations:\n");
printf("1. Enqueue\n2. Dequeue\n3. Display Queue\n4. Exit\n");
printf("Enter your choice: "); scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to enqueue: ");
Output:
45
Data Structure (3130702) 230160107100
Conclusion:
The above program demonstrates the implementation of a queue using a linked

list, effectively managing dynamic memory allocation. Unlike array-based queues,
this linked list approach allows the queue to grow and shrink dynamically without
being constrained by a fixed size. The program handles key queue operations such
as enqueue, dequeue, and display while ensuring efficient memory usage and
flexibility for queue operations.
Quiz:
(1) Which are the operations on singly link list?
1. Traversal: Visit all the nodes in the linked list starting from the head.
2. Insertion: Insert a new node at the beginning, end, or at a specified position in the list.
o Insertion at the beginning (head). o Insertion at the end (tail).
o Insertion after a specified node. 3. Deletion: Remove a node from the
list. o Deletion at the beginning (head). o Deletion at the end (tail).
o Deletion of a specified node.
4. Search: Search for an element by value in the list.
5. Update: Modify the data of a node in the list.
6. Reversal: Reverse the order of the nodes in the list.
(2) State the limitation of singly link list

46
Data Structure (3130702) 230160107100
Unidirectional Traversal: Singly linked lists can only be traversed in one direction (from head to
tail), making reverse traversal difficult.
Extra Memory Usage: Each node requires additional memory for storing the pointer to the next
node, which can be more memory-intensive than arrays.
No Random Access: You can't directly access elements by index like in an array. You need to
traverse the list from the head to find an element.
Inefficient Search: Searching for an element requires traversing the list, which takes O(n) time.

3. Fundamentals of Computer Algorithms by Horowitz, Sahni,Galgotia Pub. 2001 ed.

Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
Experiment No: 4
AIM : Doubly linked list
4.1 Write a program to implement following operations on the doubly linked list.
(c) Delete a last node of the linked list. (d) Delete a node before specified position.
Date:
47
Data Structure (3130702) 230160107100
Objectives: (a) To understand the concepts of doubly linked list

(b) To analyze different algorithms on doubly link list
(c) To implement various operations on doubly link list

Theory:
Doubly linked list
A doubly linked list is a data structure where each node contains data and two pointers - one to point
to the previous node (LPTR) and another to point to the next node (RPTR). The main advantage of
a doubly linked list is that we can traverse it in any direction, either forward or backward. Another
advantage is that we can delete a node with ease since we have pointers to both the previous and
next nodes. In contrast, a node on a singly linked list cannot be removed unless we have a pointer
to its predecessor. However, the drawback of a doubly linked list is that it requires more memory
than a singly linked list since we need an extra pointer to point to the previous node. In the image,
L and R denote the leftmost and rightmost nodes in the list, respectively. The left link of the L node
and the right link of the R node are both NULL, indicating the end of the list for each direction.
Operations on doubly linked list
Insert
Traverse list (Print list) Copy linked list
4.1 Write a program to implement following operations on the doubly linked list.
(c) Delete a last node of the linked list. (d) Delete a node before specified position.
48
Data Structure (3130702) 230160107100
Program:
#include <stdio.h>
#include <stdlib.h>
// Node structure for doubly linked list

struct Node { int data; struct Node*
next; struct Node* prev;
};
// Function to insert a node at the front of the list void

insert_at_front(struct Node** head, int data) { struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = data; new_node->next =
*head; new_node->prev = NULL;
if (*head != NULL) { (*head)- >prev =

new_node;
}
*head = new_node;
printf("Inserted %d at the front\n", data);
}
// Function to display the list void display(struct

Node* node) { if
(node == NULL) {
printf("List is empty\n");
return;
}
while (node != NULL) {
printf("%d ", node->data); node
= node->next;
}
printf("\n");
}
// Main function to test insertion at front int

main() { struct Node* head = NULL;
49
Data Structure (3130702) 230160107100
insert_at_front(&head, 10);
insert_at_front(&head, 20);
insert_at_front(&head, 30); display(head);
return 0;
} Output:
Program:
#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct
Node* next; struct Node* prev;
};
// Function to insert a node at the end of the list void insert_at_end(struct

Node** head, int data) { struct Node* new_node = (struct
Node*)malloc(sizeof(struct
Node)); struct Node* last = *head; new_node->data = data; new_node->next = NULL;
if (*head == NULL) { new_node- >prev = NULL;

*head = new_node;
printf("Inserted %d at the end\n", data); return; }
while (last->next != NULL) {

last = last->next;
}
last->next = new_node; new_node- >prev =

last; printf("Inserted %d at the end\n",
data);
}

Node* node) { if (node == NULL) {
printf("List is empty\n"); return;
50
Data Structure (3130702) 230160107100
}
printf("%d ", node->data);
node = node->next;
} printf("\n");
}
// Main function to test insertion at end int

main() { struct Node* head
= NULL;
insert_at_end(&head, 10);
insert_at_end(&head, 20); insert_at_end(&head,
30); display(head);
return 0;
}
Output:
(c) Delete a last node of the linked list. Program:
#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct Node*
next; struct Node* prev;
};
// Function to delete the last node of the list

void delete_last_node(struct Node** head)
{ if (*head == NULL) { printf("List is
empty\n"); return;
}
struct Node* temp = *head;
51
Data Structure (3130702) 230160107100
// If there is only one node in the list if ((*head)->next ==
NULL) { printf("Deleted node with data %d\n", (*head)>data);
free(*head); *head = NULL; return;
}
// Traverse to the last node

while (temp->next != NULL) {
temp = temp->next;
}
printf("Deleted node with data %d\n", temp-

>data); temp->prev->next = NULL; free(temp);
}

Node* node) { if
(node == NULL) { printf("List
is empty\n");
return;
}
= node->next;
} printf("\n");
}
// Function to insert a node at the end (for testing purposes) void insert_at_end(struct
if (*head == NULL) {
new_node->prev = NULL;
*head = new_node;
return;
}
while (last->next != NULL) { last

= last->next;
}
last->next = new_node; new_node-
>prev = last;
}
52
Data Structure (3130702) 230160107100
// Main function to test deletion of the last node int main()
{
struct Node* head = NULL;
insert_at_end(&head, 20); insert_at_end(&head,
30);
display(head);
delete_last_node
(&head);
display(head);
return 0;
}
Output:
(d) Delete a node before specified position.
Program:
#include <stdio.h>
#include <stdlib.h>
// Node structure for doubly linked list struct

Node { int
data; struct
Node* next; struct Node*
prev;
};
// Function to delete the node before the specified position

void delete_before_position(struct Node** head, int pos)
{ if (*head == NULL || pos <= 1) { printf("Invalid
position\n"); return;
}
struct Node* temp = *head;

for (int i = 1; i < pos - 1; i++) { if (temp == NULL ||
temp->next == NULL) { printf("Position
out of bounds\n"); return;
53
Data Structure (3130702) 230160107100
}
temp = temp->next;
}
if (temp->prev == NULL) { printf("No node to delete

before position %d\n", pos);
return;
}
printf("Deleted node with data %d before position %d\n", temp->data, pos);

temp->prev->next = temp->next; if (temp->next != NULL) { temp- >next->prev = temp>prev;
} free(temp);
}

Node* node) { if (node
== NULL) {
printf("List is empty\n"); return;
}
= node->next;
}
printf("\n");
}
// Function to insert a node at the end (for testing purposes) void insert_at_end(struct
if (*head == NULL) {
new_node->prev = NULL;
*head =
new_node; return;
}
while (last->next != NULL) { last =

last->next;
}
last->next = new_node; new_node-
>prev = last;
}
54
Data Structure (3130702) 230160107100
// Main function to test deletion before a specified position int
main() { struct Node* head = NULL;
display(head);
delete_before_position(&head, 4); // Delete node before position 4

display(head);
return 0;
}
Output:
Conclusion:
In this implementation of the doubly linked list in C, we demonstrated several fundamental operations,
including inserting nodes at both the front and end of the list, deleting the last node, and deleting a node
before a specified position.
Quiz:
(1) Explain structure of a node of doubly link list A node in a doubly linked list consists of
three components:
1. Data Field: Stores the actual data or value of the node.

2. Next Pointer (next): Points to the next node in the sequence. It is used for forward
traversal.
55
Data Structure (3130702) 230160107100
3. Previous Pointer (prev): Points to the previous node in the sequence. It is used for
backward traversal.
(2) Which is the main advantage of doubly link list?

• You can move forward (using the next pointer) and backward (using the prev pointer)
through the list.
• It makes certain operations, like reversing the list, more efficient since you don’t need to
traverse the list from the start.
• It is more flexible in operations like deletion, insertion before a specific node, or moving
backward from a particular node.
(3) What is the drawback of doubly link list?
• Increased memory usage: Each node requires extra memory for storing the additional
pointer (prev). In comparison to a singly linked list, doubly linked lists take up more
space.
• More complex operations: Each operation (like insertion and deletion) needs careful
handling of both next and prev pointers, making the operations slightly more
complicated compared to singly linked lists.

Fundamentals of Computer Algorithms by Horowitz, Sahni, Galgotia Pub. 2001 ed.
References used by the students:
1. An Introduction to Data Structures with Applications. by Jean-Paul Tremblay & Paul G. Sorenson
Publisher-Tata McGraw Hill.
56
Data Structure (3130702) 230160107100

Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
Experiment No: 5
AIM : Circular linked list
5.1 Write a program to implement following operations on the circular linked list.
5.2 Identify widely used application which uses linked list for implementation of its
important feature.
Date:
Objectives: (a) To understand the concepts of circular linked list

(b) To analyze different algorithms on circular link list
(c) To implement various operations on circular link list

Theory:
57
Data Structure (3130702) 230160107100
Circular linked list
A circular linked list is similar to a singly linked list, except that the last node points to the first
node, creating a circular arrangement of nodes. Unlike a singly linked list, it does not contain null
pointers. Traversal can only be done in one direction, i.e., the forward direction. The biggest
advantage of a circular linked list is that it saves time when we want to go from the last node to the
first node because it directly points to the first node. A good example of an application where a
circular linked list can be used is a time-sharing problem that can be solved by the operating system.
Operations on circular linked list
Insert
Traverse list (Print list)
5.1 Write a program to implement following operations on the circular linked list.
(c) Delete a first node of the linked list. (d) Delete a node after specified position.
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; struct Node*
next;
};
struct Node* last = NULL;
void insert_end(int data) { struct Node* new_node = (struct

Node*)malloc(sizeof(struct Node)); new_node- >data = data;
if (last == NULL) {
last = new_node; last->next = last; // Pointing to
itself
} else { new_node->next = last-
>next; last->next =
new_node; last = new_node;
58
Data Structure (3130702) 230160107100
}
}
void display() { if (last == NULL) {

printf("List is
empty.\n"); return;
}
struct Node* temp = last->next;

do { printf("%d -> ", temp-
} while (temp != last->next); printf("\n"); }
int main() { insert_end(10);

insert_end(20);
insert_end(30);
display();
return 0; } Output:
Program:
#include <stdio.h>
#include <stdlib.h>
struct Node { int data;

struct Node* next;
};
struct Node* last = NULL; void insert_end(int data) { struct Node* new_node = (struct
Node*)malloc(sizeof(struct Node)); new_node- >data =
data;
if (last == NULL) {
last = new_node; last->next
= last;
} else {
new_node->next = last->next; last-
>next = new_node; last
59
Data Structure (3130702) 230160107100
= new_node;
}
}
void insert_before_position(int data, int pos) {

if (last == NULL) { printf("List is
empty.\n"); return; }
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node-

>data = data; struct Node* temp = last->next;
if (pos == 1) { // Insert before first node new_node- >next =

last->next; last->next = new_node;
} else { for (int i = 1; i < pos - 1; i++)
{ temp = temp->next; if (temp
== last->next) {
printf("Position out of bounds.\n");
return;
}
}
new_node->next = temp->next; temp->next
= new_node;
}
}

printf("List is
empty.\n"); return;
}

do { printf("%d -> ", temp- >data); temp =
temp->next;
} while (temp != last->next); printf("\n");
}
int main() {
insert_end(10);
insert_end(20);
insert_end(30);
display();
insert_before_position(15, 2);
display();
60
Data Structure (3130702) 230160107100
return 0;
}
Output:
Program:
#include <stdio.h>
#include <stdlib.h>

struct Node* next;
};
data;
if (last == NULL) {
= last;
} else {
new_node->next = last->next; last-
>next = new_node; last
= new_node;
}
}
void delete_first() { if (last ==

NULL) { printf("List is
empty.\n"); return;
61
Data Structure (3130702) 230160107100
}
struct Node* first_node = last->next;

if (last == first_node) { // Only one node last
= NULL; } else { last->next =
first_node->next;
} free(first_node);
}
void display() { if (last ==

NULL) { printf("List is
empty.\n"); return;
}

do { printf("%d -> ", temp->data);
temp = temp->next; } while
(temp != last->next); printf("\n"); }
int main() {
insert_end(10);
insert_end(20);
insert_end(30);
display();
delete_first(); display();
return 0; } Output:
Program:
#include <stdio.h>
#include <stdlib.h>

struct Node* next;
};
data;
62
Data Structure (3130702) 230160107100
if (last == NULL) {
= last;
} else { new_node->next =
last- >next; last->next =
new_node; last = new_node;
}
}
void delete_after_position(int pos) { if

(last == NULL) {
printf("List is empty.\n"); return; }
for (int i = 1; i < pos; i++) { temp

= temp->next; if (temp == last- >next) {
printf("Position out of bounds.\n"); return;
} }
struct Node* node_to_delete = temp->next; temp->next

= node_to_delete->next;
if (node_to_delete == last) { last

= temp;
}
free(node_to_delete);
}

printf("List is
empty.\n"); return;
}

do { printf("%d -> ", temp-
} while (temp != last>next);
printf("\n"); }
int main() {
insert_end(10);
insert_end(20);
63
Data Structure (3130702) 230160107100
insert_end(30); display();
delete_after_position(2); // Delete node after position 2

display();
return 0; }
Output:
5.2 Identify widely used application which uses linked list for implementation of its
important feature.
One widely used application of linked lists is the implementation of dynamic memory allocation
systems like the malloc() function in C. In systems that manage free and used memory blocks, a
linked list is used to track allocated and free memory segments, facilitating dynamic memory
allocation.
Conclusion:
In this exercise, we implemented various operations on a circular linked list in C, including inserting
a node at the end, inserting a node before a specified position, deleting the first node, and deleting a
node after a specified position. Each of these operations demonstrated how circular linked lists
maintain connectivity through circular pointers, making them efficient for situations where we need
continuous looping of data. Quiz:
(1) What are disadvantages of circular link list?
1. Complexity in Implementation: Circular linked lists are more complex to implement than linear
linked lists due to the need to manage the circular connections properly. This complexity can lead
to bugs and make maintenance more challenging.
2. Increased Memory Overhead: Each node in a circular linked list requires extra memory for the
pointer, which can be significant in cases where many small data elements are stored.
3. Traversal Issues: Traversing a circular linked list requires careful handling to avoid infinite loops.
Special conditions must be implemented to break out of the loop when needed, particularly when
performing operations like searching or deleting nodes.
4. Difficulty in Finding the Last Node: Unlike singly or doubly linked lists, where the last node can
be easily identified, in a circular linked list, there is no straightforward way to access the last node
without traversing the entire list.
64
Data Structure (3130702) 230160107100
5. Limited Use Cases: While circular linked lists have their advantages, they are not as widely
applicable as other data structures (like arrays or regular linked lists), limiting their use in certain
situations.
(2) Differentiate Circular link list and Queue
Feature Circular Linked List Queue
Structure A circular linked list consists A queue is a linear data

of nodes connected in a circle, structure that follows the First
with each node pointing to the In First Out (FIFO) principle,
next. where elements are added at
one end (rear) and removed
from the other (front).
Insertion and Deletion Nodes can be inserted or Insertion (enqueue) is done at

deleted at any position the rear, while deletion
(beginning, end, or middle). (dequeue) is done at the front.
Access Nodes can be accessed in any Access is restricted to the
order by traversing the list. front element for deletion and
rear for insertion.
Use Cases Used in applications like Commonly used for task

round-robin scheduling and scheduling, breadth-first
multiplayer gaming. search in trees, and handling
requests in print queues.
(3) Which are the operations on circular link list?  Insertion:

• At the End: Add a new node at the end of the list.
• At the Beginning: Add a new node at the start of the list.
• Before/After a Specified Position: Insert a new node before or after a given node.
 Deletion:
• Delete First Node: Remove the first node from the list.
• Delete Last Node: Remove the last node from the list.
• Delete a Specific Node: Remove a node based on its position or value.
 Traversal:
• Display: Show all the nodes in the list.  Search:
65
Data Structure (3130702) 230160107100
• Find a node with a specific value.  Count:
• Count the total number of nodes in the list.
•

(4) http://www.geeksforgeeks.org/data-structures/
(5) http://www.coursera.org/specializations/data-structures-algorithms

Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
66
Data Structure (3130702) 230160107100
Experiment No: 6
AIM : Tree

6.2 Implement recursive tree traversing methods in-order, pre-order and post-order
traversal.
6.3 Identify widely used applications which use Tree data structure for implementation of
Date:
Objectives: (a) To understand the concepts of Tree

(b) To analyze different algorithms on Tree
(c) To implement various operations on Tree

Theory:
Binary Search Tree
A binary search tree is a binary tree in which each node possessed a key that satisfy the following
conditions
1. All key (if any) in the left sub tree of the root precedes the key in the root.
2. The key in the root precedes all key (if any) in the right sub tree. 3. The left and right sub tree sub
trees of the root are again search trees.
Operations on tree
The most common operations performed on tree structure are that of traversal. This is a procedure by
which each node in the tree is processed exactly once in a systematic manner.
67
Data Structure (3130702) 230160107100
There are three ways of traversing a binary tree.

1. Pre-order Traversal
2. In-order Traversal
3. Post-order Traversal Pre-order
Pre-order traversal of a binary tree is defined as follow

• Process the root node
• Traverse the left sub tree in pre-order
• Traverse the right sub tree in pre-order
If particular sub tree is empty (i.e., node has no left or right descendant) the traversal is
performed by doing nothing, In other words, a null sub tree is considered to be fully traversed
when it is encountered.
In-order
The In-order traversal of a binary tree is given by following steps,

• Traverse the left sub tree in In-order
• Traverse the right sub tree in In-order
Post-order
The post-order traversal is given by

• Traverse the left sub tree in post-order
• Traverse the right sub tree in post-order
Program:
#include <stdio.h>
#include <stdlib.h>
// Definition of the tree

node struct Node { int
data; struct Node*
left; struct Node* right;
};
68
Data Structure (3130702) 230160107100
// Function to create a new node struct Node* createNode(int data) { struct Node* newNode =
(struct Node*)malloc(sizeof(struct Node)); newNode-
>data = data; newNode->left = newNode-
>right = NULL; return newNode;
}
// Function to insert a node into the BST struct Node* insert(struct

Node* root, int data) { if
(root == NULL) { return createNode(data);
}
if (data < root->data) { root->left = insert(root->left,

data);
} else if (data > root->data) { root->right = insert(root->right,
data); }
return root;
}
// Function to display the tree (inorder) void

inorder(struct Node* root)
{ if (root != NULL) { inorder(root>left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Main function
int main() { struct Node* root
= NULL;
// Inserting nodes into the BST root

= insert(root, 50); insert(root,
30); insert(root, 70);
insert(root, 20); insert(root,
40); insert(root,
// Displaying the tree using in-order traversal printf("In-order

traversal: ");
inorder(root); printf("\n");
return 0; } Output:
69
Data Structure (3130702) 230160107100
6.2 Implement recursive tree traversing methods in-order, preorder and post-order
traversal.
Program:
// Function to display the tree (in-

order) void inorder(struct Node* root)
{ if (root != NULL) {
inorder(root>left); printf("%d ",
root->data); inorder(root-
>right);
}
}
// Function to display the tree (pre- order) void

preorder(struct Node* root)
{ if (root != NULL) { printf("%d
", root->data); preorder(root->left); preorder(root-
>right);
} }
// Function to display the tree (post- order) void

postorder(struct Node* root)
{ if (root != NULL) {
postorder(root->left); postorder(root>right);
printf("%d ",
root->data);
} }
int main() { struct Node* root = NULL;
// Inserting nodes into the BST

root = insert(root, 50);
insert(root, 30); insert(root, 70);
insert(root, 20); insert(root,
40); insert(root,
70
Data Structure (3130702) 230160107100
// Traversals printf("In-
order traversal: ");
inorder(root);
printf("\n");
printf("Pre-order traversal: ");

preorder(root);
printf("\n"); printf("Post-
order traversal: ");
postorder(root);
printf("\n");
return 0; } Output:
6.3 Identify widely used applications which use Tree data structure for implementation of
• Hierarchical Data Representation: Trees represent hierarchical data structures, such as file
systems and organizational charts, allowing for efficient organization and retrieval.
• Database Indexing: Trees, especially B-trees and binary search trees, are commonly used in
databases to index data, enabling fast search, insertion, and deletion operations.
• Network Routing Algorithms: Trees are used in network routing protocols (e.g., spanning
trees) to minimize costs and optimize data transmission paths in network topologies.
• Expression Parsing and Evaluation: Abstract syntax trees (ASTs) are utilized in compilers
and interpreters to represent and evaluate expressions, making it easier to analyze and
transform code.
• Artificial Intelligence: Decision trees are widely used in machine learning for classification
and regression tasks, helping to make decisions based on input features.
Conclusion:
In this program, we successfully implemented the Binary Search Tree (BST) along with its insertion
operation and recursive tree traversal methods (in-order, pre-order, and post-order). The in-order
traversal provided sorted output of the BST, while pre-order and post-order gave different sequences
useful for various applications. Binary Search Trees are efficient for searching, insertion, and deletion
71
Data Structure (3130702) 230160107100
operations due to their structured arrangement, which makes them an essential data structure in both
theory and practical applications. The traversal techniques allow for systematic exploration of the tree
based on the specific order of node visitation. Quiz:
(1) Define binary search tree
A Binary Search Tree (BST) is a data structure that consists of nodes, where each node has
a maximum of two children: a left child and a right child. The left subtree of a node contains
only nodes with keys less than the node's key, and the right subtree contains only nodes with
keys greater than the node's key. This property allows for efficient searching, insertion, and
deletion operations, typically with a time complexity of O(log n) in a balanced tree.
(2) Explain pre-order, in-order and post order traversal techniques  Pre- order
Traversal:
• In pre-order traversal, the nodes are visited in the following order: Root, Left, Right. This means
the root node is visited first, then the left subtree, followed by the right subtree. It is commonly
used for creating a copy of the tree or in prefix expressions.
• Example: Pre-order of the tree 50, 30, 70, 20, 40, 60, 80 is 50 30 20 40 70 60 80.
 In-order Traversal:
• In in-order traversal, the nodes are visited in the following order: Left, Root, Right. This traversal
results in visiting the nodes in ascending order when applied to a Binary Search Tree. It is
commonly used for retrieving data in sorted order.
• Example: In-order of the tree 50, 30, 70, 20, 40, 60, 80 is 20 30 40 50 60 70 80.
 Post-order Traversal:
• In post-order traversal, the nodes are visited in the following order: Left, Right, Root. This means
the root node is visited last, after the left and right subtrees. It is often used in applications where
nodes need to be deleted or for postfix expressions.
• Example: Post-order of the tree 50, 30, 70, 20, 40, 60, 80 is 20 40 30 60 80 70 50.
(3) Which are the applications of binary search tree?

 Database Indexing:
• Binary Search Trees are used to maintain large sets of ordered data. B-trees and their variations are
widely used in databases to allow fast data retrieval, insertion, and deletion.  File Systems:
• File systems often use trees (or BST variants) to manage files and directories efficiently in a
hierarchical structure.
 Searching Algorithms:
• BSTs are used to implement search algorithms where the goal is to minimize the time spent
searching for an element. In a balanced BST, the average time complexity for search operations is
O(log n).
 Auto-complete Systems:
72
Data Structure (3130702) 230160107100
• In text input systems such as search engines or mobile keyboard auto-completion, binary search
trees can be used to suggest words by storing dictionary words in the tree structure.  Routing
Algorithms:
• Network routing algorithms use BSTs (or their variants) to determine the most efficient route for
data to travel from one node to another.


Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
73
Data Structure (3130702) 230160107100
Experiment No: 7
AIM : Graph
7.1 Write a program to perform BFS and DFS on given graph.

7.2 Identify widely used applications which use graphs data structure for implementation
Date:
Objectives: (a) To understand the concepts of graphs

(b) To analyze different algorithms on graphs
(c) To implement various operations on graphs

Theory:
Graph:
A graph G can be defined as a non-empty set of vertices or nodes (V) and a set of edges (E) that
represents the relationship or connection between those nodes. The edges can be defined as a
mapping from E to pairs of elements of V. A graph can be represented as G = (V, E), where V
represents the set of nodes and E represents the set of edges. Each edge of the graph G can be
associated with a pair of nodes of the graph. If an edge X belongs to E and is associated with a pair
of nodes (u, v), where u and v belong to V, then we say that edge X connects node u and node v.
Depth First Search (DFS):
DFS is a graph traversal algorithm that is similar to the preorder traversal of a tree. The traversal
can start from any vertex vi of the graph. Initially, the vertex vi is visited, and then all the adjacent
vertices to vi are traversed recursively using DFS. As a graph can have cycles, we need to avoid
74
Data Structure (3130702) 230160107100
revisiting a node. To achieve this, when a vertex V is visited, it is marked as visited and should not
be selected for traversal again.
Breadth First Search (BFS)
• Breadth First Search (BFS) starts from a vertex v0 and marks it as visited. Then, all the vertices
adjacent to v0 are visited next.
• Let the vertices adjacent to v0 be v1, v2, v3, and v4. These vertices are marked as visited.
• All unvisited vertices adjacent to v1, v2, v3, and v4 are visited next.
• The above process continues until all vertices are visited.
• The algorithm for BFS maintains a list of vertices that have been visited but not explored for
adjacent vertices. This list is stored in a queue. • The queue initially contains the starting vertex.
• In each iteration, a vertex is removed from the queue, and its adjacent vertices, which have not
been visited yet, are added to the queue. • The algorithm terminates when the queue becomes
empty.
7.1 Write a program to perform BFS and DFS on given graph.
Program:
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Structure for a node in the adjacency list

struct Node { int vertex; struct
Node* next;
};
// Graph structure with an adjacency list struct

Graph { int
numVertices;
struct Node* adjLists[MAX_VERTICES];
};
// Queue structure for BFS struct

Queue { int
items[MAX_VERTICES];
int front; int rear;
};
75
Data Structure (3130702) 230160107100
// Function to create a graph
struct Graph* createGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct
Graph)); graph- >numVertices = vertices;
for (int i = 0; i < vertices; i++) { graph- >adjLists[i] = NULL;

} return graph; }
// Function to create a new adjacency list node struct

Node* createNode(int v) { struct Node*
newNode = malloc(sizeof(struct
Node)); newNode->vertex = v; newNode->next =
NULL; return newNode;
}
// Function to add an edge to the graph void

addEdge(struct Graph* graph, int src, int dest) { struct
Node* newNode = createNode(dest); newNode->next
= graph->adjLists[src]; graph-
>adjLists[src] = newNode;
// Uncomment the following line for undirected graph

// newNode = createNode(src);
// newNode->next = graph->adjLists[dest];
// graph->adjLists[dest] = newNode;
}
// Function to create a queue struct

Queue* createQueue() { struct Queue* queue =
malloc(sizeof(struct Queue));
queue->front = -1; queue->rear = -1; return
queue;
}
// Function to check if the queue is empty int

isEmpty(struct Queue* queue) {
return queue->rear == -1;
}
// Function to enqueue an element void enqueue(struct

Queue* queue, int value) { if (queue->rear ==
MAX_VERTICES - 1) {
printf("Queue is
full\n"); return; } if
(queue->front == -1) {
queue->front = 0;
76
Data Structure (3130702) 230160107100
} queue-
>rear++; queue->items[queue->rear]
= value;
}
// Function to dequeue an element int dequeue(struct

Queue* queue) { if (isEmpty(queue)) {
printf("Queue is empty\n"); return -1; }
int item = queue->items[queue- >front];
queue->front++; if (queue-
>front > queue->rear) { queue->front =
queue->rear = -
1; // Reset the queue
} return item;
}
// BFS algorithm void bfs(struct Graph* graph, int

startVertex) { int
visited[MAX_VERTICES] = {0};
struct Queue* queue = createQueue();
visited[startVertex] = 1; enqueue(queue,
startVertex);
printf("BFS traversal: "); while (!isEmpty(queue))

{ int currentVertex = dequeue(queue); printf("%d ",
currentVertex);
struct Node* temp = graph->adjLists[currentVertex]; while

(temp) { int
adjVertex = temp->vertex; if
(!visited[adjVertex]) {
visited[adjVertex] = 1; enqueue(queue,
adjVertex);
}
temp = temp->next;
} }
printf("\n");
}
// DFS algorithm (using recursion) void dfs(struct Graph*

graph, int vertex, int visited[]) {
visited[vertex] = 1; printf("%d ", vertex);
77
Data Structure (3130702) 230160107100
struct Node* temp = graph- >adjLists[vertex]; while
(temp) { int
adjVertex = temp->vertex; if
(!visited[adjVertex]) { dfs(graph,
adjVertex, visited);
}
temp = temp->next;
} }
// Wrapper for DFS to initialize visited array void dfsTraversal(struct

Graph* graph, int startVertex) { int
visited[MAX_VERTICES] = {0};
printf("DFS traversal: "); dfs(graph,
startVertex, visited); printf("\n"); }
// Main function int main() { struct Graph* graph

= createGraph(5);
addEdge(graph, 0, 1);
bfs(graph, 0); // Start BFS from vertex 0 dfsTraversal(graph, 0);

// Start DFS from vertex 0
return 0;
}
Output:
7.2 Identify widely used applications which use graphs data structure for implementation
of its important feature. Social Networks:
Graphs are used to model social relationships. Nodes represent users, and edges represent
connections or friendships.
Web Page Link Structures:

78
Data Structure (3130702) 230160107100
The web can be represented as a directed graph where web pages are nodes, and
hyperlinks are edges.
Routing Algorithms:
Graphs are fundamental in network routing protocols to find the shortest path for data
transmission across a network (e.g., Dijkstra's algorithm).
Recommendation Systems:
Graphs are utilized to find relationships between users and items in recommendation
systems, enhancing user experience by suggesting relevant content.
Game Development:
Graphs are used for pathfinding algorithms (like A* or Dijkstra) in games to navigate
characters or vehicles through environments.
Dependency Resolution:
In build systems, tasks and their dependencies can be represented as graphs to determine
the order of execution.
Network Topologies:
Graphs are used to model various network topologies (e.g., star, mesh) in
telecommunications and computer networks.
Transportation Systems:
Graphs represent transportation networks, with nodes as locations and edges as paths,
allowing for route optimization.
Circuit Design:
Graphs model electrical circuits, where components are represented as nodes and
connections as edges, aiding in analysis and design.
Biological Networks:
Graphs are used to model biological systems, such as protein-protein interaction networks
or gene regulatory networks, for studying biological functions.
Conclusion:
In this section, we implemented both Breadth-First Search (BFS) and Depth-First Search (DFS)
algorithms for graph traversal using a graph represented by an adjacency list in C. BFS explores
nodes layer by layer, making it ideal for finding the shortest path in unweighted graphs, while DFS
explores as far as possible down one branch before backtracking, which is useful for scenarios such
as topological sorting or pathfinding in mazes. Quiz:
79
Data Structure (3130702) 230160107100
(1) Define Directed Acyclic Graph (DAG).

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles. This means that
there is no way to start at any vertex vvv and follow a consistently directed path that
eventually loops back to vvv. In a DAG, each edge has a direction, indicating a one-way
relationship between nodes, and the absence of cycles allows for the establishment of a
topological order among the vertices. DAGs are often used to represent structures where a
relationship is unidirectional and hierarchical, such as task scheduling, version control
systems, and data processing workflows.
(2) Differentiate DFS and BFS.
Feature Depth-First Search (DFS) Breadth-First Search (BFS)
Traversal Method Explores as far as possible down Uses a queue to keep track of the
one branch before backtracking. next node to visit.
Data Structure Used Uses a stack (or recursion) to Uses a queue to keep track of the
keep track of the next node to next node to visit.
visit.
Space Complexity O(h), where h is the height of the O(b^d), where b is the branching
tree; can be O(n) in the worst factor and d is the depth of the
case for highly unbalanced trees. shallowest solution; can be more
memory-intensive.
Traversal Order Visits nodes in depth order, Visits nodes in breadth order,
exploring child nodes before exploring all nodes at the current
sibling nodes. depth before moving to the next
level.
(3) State the applications of graph.
1. Social Networks:
o Modeling relationships between individuals, where nodes represent users and edges
represent friendships or connections.
2. Web Page Link Structures:
o Representing the internet as a graph, where web pages are nodes and hyperlinks are directed
edges. This structure is used in search engines for indexing and ranking.
3. Routing Algorithms: o Used in network routing protocols to find the shortest path for
data transmission between nodes (e.g., Dijkstra's algorithm, A* algorithm).
80
Data Structure (3130702) 230160107100
4. Transportation Systems:
o Modeling road networks where intersections are nodes and roads are edges. This is used for
route planning and optimization.
5. Recommendation Systems:
o Graphs can represent relationships between users and items, facilitating personalized content
suggestions in e-commerce or streaming services.
6. Dependency Resolution:
o Managing dependencies between tasks in project management tools, where nodes represent
tasks and edges represent dependencies.
7. Game Development:
o Pathfinding algorithms for character movement in games, using graphs to navigate complex
terrains.
8. Circuit Design:
o Modeling electrical circuits as graphs, where components are nodes and connections are
edges, aiding in analysis and design. o
9. Biological Networks: o Representing interactions in biological systems, such as protein-
protein interaction networks or gene regulatory networks.
10. Data Organization:
• Representing hierarchical data structures, such as file systems or organizational charts, using directed
graphs.
1. An Introduction to Data Structures with Applications. by Jean-Paul Tremblay & Paul

G. Sorenson Publisher-Tata McGraw Hill.

Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
81
Data Structure (3130702) 230160107100
Marks
Experiment No: 8
AIM : Searching

8.3 Identify widely used applications which use Searching technique for implementation
Date:
Objectives: (a) To understand the concepts of Searching

(b) To analyze different algorithms on Searching
(c) To implement various operations on Searching

Theory:
Linear/Sequential Search
• Linear search, also known as sequential search, is a technique used in computer science to find
a specific value in a list by sequentially checking each of its elements one at a time until the
desired one is found.
• It is the simplest search algorithm and a form of brute-force search. Its worst-case cost is
proportional to the number of elements in the list.
Binary Search
82
Data Structure (3130702) 230160107100
• If we have an array that is sorted, we can use a much more efficient algorithm called Binary
Search.
• In Binary Search, we divide the array into two equal halves and compare the middle element
with the search element.
• If the middle element is equal to the search element, we have found the element and return its
index; otherwise, if the middle element is less than the search element, we look at the right part
of the array, and if the middle element is greater than the search element, we
look at the left part of the array.
Program:
#include <stdio.h>
// Function to perform Linear Search int

linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) { if (arr[i]
== target) { return i; // Return the index of the found
element } }
return -1; // Element not found
}
// Main function int main() { int arr[] = {5,

3, 8, 4, 2}; int size = sizeof(arr) /
sizeof(arr[0]); int target = 4; int result =
linearSearch(arr, size, target);
if (result != -1) { printf("Element %d found at index

%d\n", target, result);
} else { printf("Element %d not found in the array\n",
target); }
return 0;
} Output:
83
Data Structure (3130702) 230160107100
Program:
#include <stdio.h>
// Function to perform Binary Search int

binarySearch(int arr[], int size, int target) {
int left = 0; int right = size - 1;
while (left <= right) { int mid =

left + (right - left) / 2;
// Check if target is present at mid if (arr[mid] ==

target) { return mid; // Return the index of the found element
}
// If target is greater, ignore the left half else
if (arr[mid] < target) { left = mid + 1;
}
// If target is smaller, ignore the right half else
{ right = mid - 1;
}
}
return -1; // Element not found }
// Main function
int main() { int arr[] = {1, 2, 3, 4, 5, 8};
// Sorted
array int size = sizeof(arr) / sizeof(arr[0]); int
target = 5; int result = binarySearch(arr, size,
target);
if (result != -1) { printf("Element %d found at index %d\n",

target, result); } else { printf("Element %d not found in the
array\n", target); }
return 0; } Output:
84
Data Structure (3130702) 230160107100
8.3 Identify widely used applications which use Searching technique for implementation
1. Database Querying:
Searching algorithms are used to efficiently retrieve records from databases based on specific
criteria.
2. Search Engines:
• Search engines utilize various searching techniques to retrieve relevant documents from a vast amount
of data based on user queries.
3. Text Editors:
• Functionality like "Find" in text editors implements searching algorithms to locate specific text within
documents.
4. File Systems:
• Searching techniques are employed in file systems to locate files and directories quickly based on
names or metadata.
5. Sorting and Searching Algorithms:
• Many algorithms, such as quicksort and mergesort, use searching techniques to efficiently organize
data.
6. E-commerce:
• Online shopping platforms use searching algorithms to help users find products quickly by name,
category, or other attributes.
7. Artificial Intelligence:
• In AI, searching techniques are employed in pathfinding algorithms (like A*) and game AI to find
optimal solutions.
8. Network Routing:
• Searching algorithms are used in routing protocols to find optimal paths for data packets across
networks.
9. Data Analysis:
• Searching techniques help in locating and extracting specific data points from large datasets for
analysis and visualization.
10. Machine Learning:
• In machine learning, searching algorithms can be used for feature selection, model optimization,
and hyperparameter tuning.
Conclusion:
In this section, we implemented two fundamental searching algorithms: Linear Search and Binary Search.
Linear Search traverses each element in a list until it finds the target, making it simple but inefficient for
large datasets, with a time complexity of O(n). On the other hand, Binary Search is significantly faster for
sorted arrays, reducing the search space by half with each iteration, achieving a time complexity of O(log
n)
Quiz:
85
Data Structure (3130702) 230160107100
(1) List out searching algorithms
• Linear Search: A simple search algorithm that checks each element in a list until the desired
element is found.
• Binary Search: An efficient algorithm that finds an item in a sorted array by repeatedly dividing
the search interval in half.
• Jump Search: A searching algorithm for sorted arrays that works by jumping ahead by fixed
steps and performing linear search in between.
• Exponential Search: An algorithm that finds the range where an element may exist and then
applies binary search within that range.
• Interpolation Search: A search algorithm that estimates the position of the target value within
a sorted array based on the values at the ends of the search range.
• Fibonacci Search: A searching technique that uses Fibonacci numbers to divide the array into
smaller parts.
• Ternary Search: A search algorithm that divides the array into three parts and eliminates one
of the three parts based on the comparison with the target value.
• Sublist Search: An algorithm to find a sublist within a list (or a substring within a string).
(2) Differentiate sequential search and binary search
Feature Sequential Search (Linear Binary Search

Search)
Definition Searches each element in the list Searches in a sorted array by

sequentially until the target is repeatedly dividing the search
found. interval in half.
Data Requirement Can be used on unsorted and Requires a sorted array to function
sorted lists. correctly.
Time Complexity O(n) (worst case, where n is the O(log n) (worst case, where n is
number of elements). the number of elements).
Best Use Case Best for small or unsorted lists Best for large, sorted lists where
where sorting is not feasible. search efficiency is crucial.
(3) Which are the applications of binary search algorithm?
• Searching in Databases: Efficiently locating records in sorted datasets.

• Search Engines: Finding relevant documents in a vast indexed dataset quickly.
• Library Systems: Locating books in sorted catalogs.
• E-commerce Platforms: Quickly finding products from a large inventory sorted by various
attributes.
86
Data Structure (3130702) 230160107100
• Version Control Systems: Finding specific versions or changes in a sorted history of commits. •
Autocomplete Features: Suggesting words from a sorted dictionary based on user input.


Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
Experiment No: 9
AIM : Sorting

9.4 Identify widely used applications which use Sorting technique for implementation of
Date:
87
Data Structure (3130702) 230160107100
Objectives: (a) To understand the concepts of Sorting

(b) To analyze different algorithms on Sorting
(c) To implement various operations on Sorting

Theory:
Bubble sort
Bubble sort, also known as sinking sort, is a comparison-based sorting algorithm. It works by
repeatedly scanning through the list to be sorted, comparing adjacent elements and swapping them
if they are not in the correct order. In each pass through the list, the largest element bubbles up to
the top. The algorithm repeats these processes until no more swaps are needed, indicating that the
list is sorted. Although it is simple to understand and implement, bubble sort has a worst-case and
average time complexity of O(n^2), making it too slow for large inputs. Insertion sort is a more
efficient alternative for small lists.
Merge Sort
• The merge sort algorithm is based on the classical divide-and-conquer paradigm. It operates as
follows:
 DIVIDE: Partition the n-element sequence to be sorted into two sub sequences of n/2
elements each.
 CONQUER: Sort the two sub sequences recursively using the merge sort.
 COMBINE: Merge the two sorted sub sequences of size n/2 each to produce the sorted
sequence consisting of n elements.
Quick Sort
Quicksort is currently the fastest known sorting algorithm and often the most practical choice for
sorting, with an average expected running time of O(n log(n)). Its operation consists of the following
steps: • Pick an element from the array, known as a pivot.
88
Data Structure (3130702) 230160107100
• Reorder the array so that all elements with values less than the pivot are placed before it, while
all elements with values greater than the pivot come after it (elements with equal values can go
either way). This operation is called partitioning, and at the end of it, the pivot is in its final
position.
• Recursively apply the above steps to the sub-arrays of elements with smaller and greater values,
respectively. Quicksort, like merge sort, is a divide-and-conquer recursive algorithm.
• The basic divide-and-conquer process for sorting a sub array is given in the following three easy
steps:
 Divide
 Conquer  Combine
Program:
#include <stdio.h>
// Function to swap two elements

void swap(int* a, int* b) { int
temp = *a; *a = *b; *b = temp;
}
// Partition function int partition(int arr[], int low, int high)

{ int pivot = arr[high];
// Choosing the last element as pivot int i
= (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {

// If current element is smaller than or equal to pivot if
(arr[j] <= pivot) { i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); return (i +
1); // Return the partition index }
// Quick Sort function void quickSort(int arr[], int low, int

high) { if (low < high) { int pi = partition(arr, low, high);
//
Partitioning index quickSort(arr, low, pi - 1); // Recursively sort
elements before partition quickSort(arr, pi + 1, high); // Recursively
sort elements after partition
}
}
89
Data Structure (3130702) 230160107100
// Main function int main() { int arr[] = {10, 7, 8,

9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr,
0, n - 1); printf("Sorted array (Quick
Sort): \n");
for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);
}
printf("\n");
return 0; } Output:
Program:
#include <stdio.h>
// Function to merge two halves void merge(int arr[],

int left, int mid, int right) {
int i, j, k; int n1 = mid - left + 1; int
n2 = right - mid;
// Create temporary arrays int L[n1],

R[n2];
// Copy data to temporary arrays L[] and R[] for

(i = 0; i < n1; i++)
L[i] = arr[left + i]; for (j = 0;
j < n2; j++) R[j] = arr[mid +
1 + j]; // Merge the temporary
arrays back into
arr[left..right]
i = 0; // Initial index of first sub-array j
= 0; // Initial index of second sub-array k=
left; // Initial index of merged sub-array while
(i < n1 && j < n2) { if (L[i] <=
R[j]) { arr[k] = L[i]; i++;
90
Data Structure (3130702) 230160107100
} else { arr[k] = R[j]; j++;
} k++;
}
// Copy the remaining elements of L[], if there are any while (i

< n1)
{ arr[k] = L[i]; i++; k++;
}
// Copy the remaining elements of R[], if there are any while

(j < n2) { arr[k]
= R[j];
j++; k++;
} }
// Merge Sort function

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort the first and second halves mergeSort(arr,

left, mid);
mergeSort(arr, mid + 1, right); merge(arr, left,
mid, right); } }
// Main function
int main() {
int arr[] = {12, 11, 13, 5, 6, 7}; int
n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1); printf("Sorted array
(Merge
Sort): \n");
for (int i = 0; i < n; i++) { printf("%d
", arr[i]);
} printf("\n");
return 0;
}
Output:
91
Data Structure (3130702) 230160107100
Program:
#include <stdio.h>
// Function to perform Bubble Sort

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { for
(int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) { // Swap
arr[j] and arr[j + 1]
int temp = arr[j]; arr[j] =
arr[j + 1]; arr[j + 1] = temp;
}
}
} }
// Main function int main() { int arr[]

= {64, 34, 25, 12, 22, 11, 90}; int n =
sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array (Bubble Sort): \n"); for

(int i = 0; i < n; i++) { printf("%d
", arr[i]);
} printf("\n");
return 0; } Output:
9.4 Identify widely used applications which use Sorting technique for implementation of
Sorting algorithms are foundational in computer science and are widely used in various applications. Here
are some notable applications:
92
Data Structure (3130702) 230160107100
1. Database Management: o Sorting is crucial for efficient querying and data retrieval. Indexing
in databases often involves sorting data to speed up search operations.
2. Data Analysis and Reporting:
o In analytics, sorting helps organize data for better interpretation and visualization. It’s common
to sort data by dates, values, or categories.
3. Search Algorithms: o Many search algorithms, like binary search, require sorted data to function
effectively.
Sorting is a prerequisite for these searches.
4. E-commerce Platforms: o Sorting is essential for product listings, allowing users to sort items
by price, rating, popularity, etc.
5. File Systems: o File systems often sort files and directories for efficient access and management,
such as displaying files in alphabetical order.
6. Graphics: o In computer graphics, sorting is used to determine the order in which objects are
rendered, especially in 3D graphics (z-ordering).
7. Machine Learning:
o Some machine learning algorithms, like k-means clustering, may require sorting data for
better performance and accuracy.
8. Scheduling: o Sorting is used in task scheduling algorithms to prioritize tasks based on certain
criteria like deadline, duration, or priority level.
9. Memory Management:
o In operating systems, sorting can help in memory allocation and managing free memory
blocks efficiently.
Conclusion:
Sorting algorithms are fundamental tools in computer science that organize data in a specific order, making
it easier to retrieve and analyze information efficiently. In this section, we implemented three widely-used
sorting algorithms: Quick Sort, Merge Sort, and Bubble Sort. Each algorithm has its strengths and
weaknesses, suitable for different scenarios depending on the dataset size and the required performance.
Quiz:
(1) Define sorting
Sorting is the process of arranging the elements of a list or an array in a specified order, typically in
ascending or descending numerical or lexicographical order. The primary goal of sorting is to organize
data so that it can be efficiently searched, analyzed, or displayed. Common sorting methods include
Bubble Sort, Quick Sort, Merge Sort, and Insertion Sort, each with different algorithms and
performance characteristics.
93
Data Structure (3130702) 230160107100
(2) What is divide-and-conquer strategy for sorting?
The divide-and-conquer strategy is a fundamental algorithm design paradigm that works by recursively
breaking down a problem into smaller subproblems until they become manageable and can be solved
directly. In the context of sorting algorithms, this strategy involves three main steps:
1. Divide: The array or list is divided into two (or more) smaller subarrays. This process continues
recursively until each subarray contains only one element or is empty, which is considered a sorted
state.
2. Conquer: The smaller subarrays are sorted independently. Since a single-element array is
inherently sorted, this step often requires merging or combining the sorted subarrays back together.
3. Combine: The sorted subarrays are combined to form a single sorted array. This step typically
involves comparing the elements from each subarray and merging them in the correct order.
(3) Which is the best suitable sorting algorithm as per its execution time?
• Quick Sort is often considered the best choice for large datasets due to its average-case time
complexity of O(n log n) and its in-place sorting mechanism. It is very efficient for average cases and
widely used in practice.
• Merge Sort also has a time complexity of O(n log n) but requires additional space, making it less
suitable for environments with limited memory. However, it is stable and works well for linked lists.
• For small datasets, Insertion Sort may be faster despite its O(n²) time complexity because of its low
overhead and efficiency for nearly sorted data.

94
Data Structure (3130702) 230160107100
Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
Marks
95
Data Structure (3130702) 230160107100
Experiment No: 10
AIM : Hashing and File Structure
10.1 Write a program to create hash table and handle the collision using linear probing.
10.2 Write a program to demonstrate the file primitives such as fopen, fclose, fprintf.
10.3 Identify widely used applications which use Hashing technique for implementation of
Date:
Objectives: (a) To understand the concepts of Hashing techniques

(b) To implement various file operations

Theory:
Hashing
Hashing is a method used to map a large number of data items to a smaller table by utilizing a
hashing function. This technique transforms a range of key values into a range of indexes of an
array.There are two different forms of hashing.
1. Open hashing or external hashing: Open or external hashing, allows records to be stored in
unlimited space (could be a hard disk). It places no limitation on the size of the tables.
2. Close hashing or internal hashing: Closed or internal hashing, uses a fixed space for storage
and thus limits the size of hash table.
Hashing Functions
Characteristics of a Good Hash Function

• A good hash function avoids collisions.
96
Data Structure (3130702) 230160107100
• A good hash function tends to spread keys evenly in the array.
• A good hash function is easy to compute. Different hashing functions
1. Division-Method
2. Folding Method
3. Algebraic Coding
4. Multiplicative Hashing
5. Digit Analysis
6. Mid-square Methods
7. Length Dependent Method
Collision Resolution Strategies
• Collision resolution is the main problem in hashing.

• If the element to be inserted is mapped to the same location, where an element is already inserted
then we have a collision and it must be resolved. • There are several strategies for collision
resolution. The most commonly used are :
1. Separate chaining - used with open hashing
2. Open addressing - used with closed hashing
File
In computing, a file is a group of records, where each record comprises one or more fields that have the
same sequence. Typically, each field has a predetermined length.
Different file organizations
1. Sequential files
2. Direct files
3. Index files
4. Indexed Sequential files
5. Relative files
Primitive Operations on a File
1. Creation
2. Insertion
3. Deletion
4. Updation
5. Reading
6. Searching
97
Data Structure (3130702) 230160107100
10.1 Write a program to create hash table and handle the collision using linear probing.
Program:
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
// Hash table
structure typedef
struct { int key; int
value;
} HashEntry;
HashEntry* hashTable[TABLE_SIZE];
// Hash function int hashFunction(int key)

{
return key % TABLE_SIZE;
}
// Function to insert a key-value

pair void insert(int key, int value) {
int index = hashFunction(key);
// Linear probing for collision resolution while (hashTable[index]

!= NULL) { index = (index + 1) % TABLE_SIZE; // Move to the
next index }
// Create new hash entry HashEntry*

newEntry =
(HashEntry*)malloc(sizeof(HashEntry)); newEntry->key = key; newEntry->value = value;
hashTable[index] = newEntry;
}
// Function to display the hash table void

displayHashTable() { printf("Hash
Table:\n"); for (int i = 0; i <
TABLE_SIZE; i++) {
if (hashTable[i] != NULL) { printf("Index %d: Key = %d, Value = %d\n", i, hashTable[i]->key,
hashTable[i]->value);
} else { printf("Index %d: Empty\n",
i); }
}
98
Data Structure (3130702) 230160107100
}
// Main
function int
main() {
insert(10, 100);
insert(20, 200);
insert(30, 300);
insert(40, 400);
insert(25, 250); //
Collision
occurs, will use
linear probing
insert(5, 50);
displayHashTable();
// Free allocated memory for (int i = 0;

i < TABLE_SIZE; i++) {
if (hashTable[i] != NULL) { free(hashTable[i]); }
}
return 0; }
Output:
10.2 Write a program to demonstrate the file primitives such as fopen, fclose, fprintf.
Program:
#include <stdio.h>
int main() {
FILE *filePointer;
99
Data Structure (3130702) 230160107100
// Open a file in write mode filePointer
= fopen("example.txt", "w"); if
(filePointer == NULL) { printf("Error
opening file!\n"); return 1;
}
// Write to the file fprintf(filePointer, "Hello, this is a test file.\n");

fprintf(filePointer, "This file demonstrates file operations in
C.\n");
// Close the file fclose(filePointer); printf("Data
written to file successfully.\n");
// Open the file in read mode to demonstrate reading

filePointer = fopen("example.txt", "r"); if (filePointer
== NULL) { printf("Error opening file!\n"); return
1;
}
char buffer[255];
// Read and display the content of the file
while (fgets(buffer, sizeof(buffer), filePointer) != NULL) {
printf("%s", buffer);
}
// Close the file fclose(filePointer)

; return 0; }
Output:
10.3 Identify widely used applications which use Hashing technique for implementation of
1. Database Indexing: Hashing is used to quickly locate a data record given its search key. It helps in
indexing databases for efficient data retrieval.
2. Caches: Hash tables are used in caching mechanisms to quickly retrieve data without searching
through all entries.
3. Symbol Tables: Compilers use hash tables to implement symbol tables for fast lookups of variable
names and their corresponding data.
100
Data Structure (3130702) 230160107100
4. Cryptography: Hash functions are crucial in security applications, such as password storage and
data integrity verification.
5. Memory Management: Operating systems use hashing techniques for managing memory blocks
efficiently, particularly in dynamic memory allocation.
6. Network Routing: Hashing algorithms are used in network routing protocols to determine the best
paths for data packets.
7. Distributed Systems: Hash tables are used in distributed systems for load balancing and
partitioning data across different nodes.
8. Text Processing: Hashing is used in algorithms for string matching, such as Rabin-Karp, to
efficiently find substrings.
Conclusion:
Hashing is a powerful technique used for efficient data retrieval and storage, allowing for quick access to
information through a calculated index. Internal and external hashing methods provide different ways to
manage hash tables, each with its advantages and use cases.
Quiz:
(1) What is internal hashing and external hashing?
• Internal Hashing: In internal hashing, the hash table is stored in the main memory (RAM). This
method allows for faster access since the hash table resides in memory, leading to quicker retrieval
times. Internal hashing is typically used for smaller datasets that can fit into memory, and it
employs techniques like linear probing or chaining for collision resolution.
• External Hashing: External hashing involves storing the hash table on secondary storage (such as a
disk). This method is useful for larger datasets that do not fit into memory. External hashing can
utilize methods like overflow areas on disk to handle collisions and may involve more complex I/O
operations. While access times may be slower compared to internal hashing, it allows for handling
larger volumes of data efficiently.
(2) Explain linear probing.
Linear Probing is a collision resolution technique used in hash tables. When a new entry is
inserted into a hash table and the computed index (from the hash function) is already occupied,
linear probing searches for the next available index sequentially.
(3) Which are primitive operations on file?
101
Data Structure (3130702) 230160107100
1. Open: This operation is used to create or access a file. It prepares the file for reading or
writing.
2. Close: This operation is used to terminate access to a file. It ensures that any changes made
to the file are saved and resources are released.
3. Read: This operation retrieves data from a file. It allows programs to access the contents
stored within the file.
4. Write: This operation allows data to be written to a file. It enables programs to store or
modify information in the file.
5. Delete: This operation removes a file from the storage system.

6. Seek: This operation is used to move the file pointer to a specific location within the file for
reading or writing data.
7. Flush: This operation ensures that any buffered data is written to the file, making it
immediately available.


Logic
Building (2)
(1) (2) (1) (2) (1) (2) (1) (2) (1) (2)
102
Data Structure (3130702) 230160107100
Marks
103

SHIVAM

Uploaded by

Copyright:

Available Formats

SHIVAM

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

SHIVAM

Uploaded by

Copyright:

Available Formats

Degree Engineering

A Laboratory Manual for

[ B.E. (COMPUTER ) : Semester - 3 ]

Name PRAJAPATI SHIVAM RAJARAM

Academic Term 2024-2025

Directorate of Technical Education, Gandhinagar, Gujarat

Signature of Course Faculty Head of the Department

 To provide globally competitive technical education

 To become a prominent department of Computer Engineering producing Competent professionals with

Programme Outcomes (POs)

▪ An ability to effectively integrate IT-based solutions into the user environment.

▪ Program Educational Objectives (PEOs) :-

Practical – Course Outcome matrix

Course Outcomes (COs)

Solve the given a problem using an appropriate data structure to achieve

1. Classification of Data Structure and Stack

1.1 Classify various data structures

3. Singly linked list

3.1 Write a menu driven program to implement

(a) Insert a node at the front of the linked list.

4. Doubly linked list

4.1 Write a program to implement following

5. Circular linked list

6.1 Write a program which create binary search tree.

7.1 Write a program to perform BFS and DFS on given

8.1 Write a program to implement Linear Search.

10 Hashing and File Structure

10.1 Write a program to create hash table and handle the

Industry Relevant Skills

Guidelines for Faculty members

Instructions for Students

Common Safety Instructions

Students are expected to

1. switch on the PC carefully (not to use wet hands)

1. Classification of Data Structure and Stack

1.1 Classify various data structures

2.1 Write a program to implement QUEUE

3. Singly linked list

3.1 Write a menu driven program to implement

4. Doubly linked list

4.1 Write a program to implement following

5. Circular linked list

5.1 Write a program to implement following

7.1 Write a program to perform BFS and DFS

7.2 Identify widely used application which use

10. Hashing and File Structure

1.1 Classify various data structures

Competency and Practical Skills: Logic building and programming

Relevant CO: CO1, CO2, CO5

Objectives: (a) To analyze various data structures

Equipment/Instruments: Computer System with C/C++ compiler

Safety and necessary Precautions:

Operate computer system carefully and responsibly. Use required

There are two operations applied on stack they are

1. Start scanning the infix expression from left to right.

1.1 Classify various data structures Classification

Data structures can be classified as

1. Primitive data structure

2. Non-primitive data structures: Non-primitive data structures are constructed using

struct Node temp = head, prev = NULL, *del =