Savitribai Phule Pune University

Second Year of Artificial Intelligence and Data Science - 2024 Pattern

PCC-204- AID: Data Structures Lab Manual Practical Journal

Teaching Scheme Credits Examination Scheme

Term Work : 25 Marks

Practical : 04 Hours/Week 02
Practical : 50 Marks

Companion Course if any: Data Structures

Course Objectives: The course aims to:

1. To understand practical implementation and usage of non- linear data structures for solving
problems of different domain.
2. To strengthen the ability to identify and apply the suitable data structure for the given real
world problems.
3. To analyze advanced data structures including hash table, dictionary, trees, graphs, sorting
algorithms and file organization.

Course Outcomes: Upon successful completion of this course, students will be able to:

• CO1: Use the ADT/libraries and hash tables to design algorithms for specific problem.

• CO2: Choose most appropriate data structures for graphical solutions of the problems.

• CO3: Apply non linear data structures to solve real world complex problems.

• CO4: Implement algorithm design techniques for indexing, sorting, multi-way searching.

• CO5: Analyze the efficiency of most appropriate data structure for creating efficient solutions
for engineering design situations.

Course Contents
Guidelines for Instructor’s Manual
The instructor’s manual/Lab Manual is to be developed as a hands-on resource and reference. The
instructor’s manual need to include prologue (about University/program/ institute/ depart-
ment/foreword/ preface), curriculum of course, conduction and Assessment guidelines, topics un-der
consideration-concept, objectives, outcomes, set of typical applications/assignments/guidelines,
references.
Guidelines for Student’s Laboratory Journal

The laboratory assignments are to be submitted by student in the form of journal. Journal con-sists of
prologue, Certificate, table of contents, and handwritten write-up of each assignment (Title, Objectives,
Problem Statement, Outcomes, software and Hardware requirements, Date of Completion, Assessment
grade/marks and assessor’s sign, Theory Concept in brief, algorithm, flowchart, test cases, Test Data
Set (if applicable), mathematical model (if applicable), conclusion/analysis. Program codes with sample
output of all performed assignments are to be submitted as softcopy.
As a conscious effort and little contribution towards Green IT and environment awareness, attaching
printed papers as part of write-ups and program listing to journal may be avoided. Students programs
maintained on cloud or college server by Laboratory In-charge is highly encouraged. For reference one
or two journals may be maintained with program prints at Laboratory for accreditation purpose.
Guidelines for Laboratory/Term Work Assessment

Continuous assessment of laboratory work should be done based on overall performance and
Laboratory assignments performance of student. Each Laboratory assignment assessment should be
assigned grade/marks based on parameters with appropriate weightage. Suggested parameters for
overall assessment as well as each Laboratory assignment assessment include timely completion
performance, innovation, efficient codes, punctuality and neatness.
Guidelines for Laboratory Conduction

The instructor is expected to frame the assignments by understanding the prerequisites, technolog-ical
aspects, utility and recent trends related to the topic. The assignment framing policy needs to address
the average students and inclusive of an element to attract and promote the intelligent stu-dents. The
instructor may set multiple sets of assignments and distribute them among batches of students.
It is appreciated if the assignments are based on real world problems/applications. Encourage stu-
dents for appropriate use of Hungarian notation, proper indentation and comments. Use of open source
software is to be encouraged. In addition to these, instructors may assign one real life ap-plication in
the form of a mini-project based on the concepts learned. Instructors may also set one assignment or
mini-project that is suitable to respective branch beyond the scope of the syllabus.

Set of suggested assignment lists is provided in groups- A, B, C, D, and E. Each student must perform at
least 9 assignments (All assignment for group A are compulsory, 2 from group B, 2 from group C, 1 from
group D and 1 from group E.)

• All assignments should be implemented in C/C++ language.

• Operating System Recommended: 64-bit Open Source Linux or its derivatives

• Programming Tools Recommended: Open Source C compiler such as GCC/G++.

• Development environments or text editors like Visual Studio Code, Geany, Code::Blocks, or
terminal-based editors like Vim or Emacs.

Guidelines for Practical Examination

Both internal and external examiners should jointly set problem statements. During practical
assessment, the expert evaluator should give the maximum weightage to the satisfactory
implementation of the problem statement. The supplementary and relevant questions may be asked at
the time of evaluation to test the student’s for advanced learning, understanding of the fundamentals,
effective and efficient implementation. So encouraging efforts, transparent evaluation and fair approach
of the evaluator will not create any uncertainty or doubt in the minds of the students. So adhering to
these principles will consummate our team efforts to the promising start of the student’s academics.
Learning Resources

Virtual Laboratory:

1. https://ds1-iiith.vlabs.ac.in/List%20of%20experiments.html

Suggested List of Laboratory Experiments/Assignments

Sr. No. Group A - (All)
Write menu based program-
1 a) Write a program to store roll numbers of student in array who attended a training
program in random order. Write a function for searching whether a particular student
attended a training program or not, using Linear search.
b) Write a program to store roll numbers of student array who attended training
programs in sorted order. Write a function for searching whether a particular student
attended a training program or not, using Binary search.
2 Write a program to store the first year percentage of students in an array. Write function
for sorting array of floating point numbers in ascending order using - Selection Sort -
Bubble sort and display top five scores.
3 Consider the telephone book database of N clients. Make use of a hash table
implementation to quickly look up a client’s telephone number. Make use of linear
probing, double hashing and quadratic collision handling techniques.
Group B - Assignments (Any TWO)
4 The Department of Computer Engineering has a student’s club named ’Pinnacle Club’.
Students of the second, third and final year of the department can be granted membership
on request. Similarly one may cancel the membership of the club. First node is reserved for
the president of the club and the last node is reserved for the secretary of the club. Write a
program to maintain club member‘s information using singly linked lists. Store student
PRN and Name. Write functions to:
a) Add and delete the members as well as president or even secretary. b) Compute total
number of members of club c) Display members d) Two linked lists exist for two
divisions. Concatenate two lists.
OR
Second year Computer Engineering class, set A of students like Vanilla Ice-cream and set B
of students like butterscotch ice-cream. Write a program to store two sets using a linked list.
compute and display-
a) Set of students who like both vanilla and butterscotch
b) Set of students who like either vanilla or butterscotch or not both
c) Number of students who like neither vanilla nor butterscotch
5 The ticket booking system of Cinemax theater has to be implemented. There are 10 rows
and 7 seats in each row. Doubly linked list has to be maintained to keep track of free seats
in rows. Assume some random booking to start with. Use an array to store pointers (Head
pointer) to each row. On demand
a) The list of available seats is to be displayed b) The seats are to be booked c) The
booking can be cancelled.
OR
Write a program to implement doubly linked list
a) Display free slots b) Book appointment c) Sort list based on time d) Cancel
appointment (check validity, time bounds, availability) e) Sort list based on time using
pointer manipulation (Unit II)
Group C- Assignments (Any TWO)
6 In any language program mostly syntax error occurs due to unbalancing delimiter such as
(), {}, []. Write a program using stack to check whether a given expression is well
parenthesized or not.
OR
 Implement a program for expression conversion as infix to postfix and its evaluation
using stack based on given conditions:
1. Operands and operators, both must be single characters.
2. Input Postfix expression must be in a desired format.
3. Only ”,”,” and operators are expected.
7 Pizza parlor accepting maximum M orders. Orders are served on a first come first served
basis. Queues are frequently used in computer programming, and a typical example is the
creation of a job queue by an operating system. If the operating system does not use
priorities, then the jobs are processed in the order they enter the system. Write a program
for simulating job queue. Write functions to add jobs and delete jobs from the queue.
OR
Queues are frequently used in computer programming, and a typical example is the
creation of a job queue by an operating system. If the operating system does not use
priorities, then the jobs are processed in the order they enter the system. Write C program
for simulating job queue. Write functions to add job and delete job from the queue.
Group D- Assignments (Any ONE)
8 Beginning with an empty binary search tree, Construct a binary search tree by inserting
the values in the order given. After constructing a binary tree -
i. Insert new node
ii. Find number of nodes in longest path from root
iii. Minimum data value found in the tree
iv. Change a tree so that the roles of the left and right pointers are swapped at every node
v. Search a value.
OR
A Dictionary stores keywords and its meanings. Provide facility for adding new keywords,
deleting keywords, updating values of any entry. Provide a facility to display whole data
sorted in ascending/ Descending order. Also find how many maximum comparisons may
require for finding any keyword. Use Binary Search Tree for implementation.
Group E - Assignments (Any ONE)
9 There are flight paths between cities. If there is a flight between city A and city B then
there is an edge between the cities. The cost of the edge can be the time that flight takes to
reach city B from A or the amount of fuel used for the journey. Represent this as a graph.
The node can be represented by the airport name or name of the city. Use adjacency list
representation of the graph or use adjacency matrix representation of the graph. Check
whether the graph is connected or not.
OR
You have a business with several offices; you want to lease phone lines to connect them up
with each other; and the phone company charges different amounts of money to connect
different pairs of cities. You want a set of lines that connects all your offices. With a
minimum total cost. Solve the problem by suggesting appropriate data structures.
Group F - Assignments
10 Design a mini project which will use the different data structure to show the use of
specific data structure and efficiency (performance) of the code.
 Practical No. 1
Title: Implementing Searching Algorithms.
Problem Statement:
Write menu based program-
a) Write a program to store roll numbers of student in array who attended a training program in random order.
Write a function for searching whether a particular student attended a training program or not, using Linear
search.
b) Write a program to store roll numbers of student array who attended training programs in sorted order. Write
a function for searching whether a particular student attended a training program or not, using Binary search.
Aim:
Write C/C++ menu based program to store roll numbers of student in array who attended training program. Write
function for-
• Searching whether particular student attended training program or not using linear search in random order.
• Searching whether particular student attended training program or not using binary search in sorted order.
Objectives:
• To study concept of Searching.
• To understand implementation of various searching algorithms like Linear Search and Binary Search.
Prerequisites:
• Knowledge of C and C++ Programming.
• Knowledge of Arrays.
Outcomes:
• Implement use of Array.
• Implement various searching algorithms.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Array
An array is a linear data structure that stores a collection of similar types of elements, in contiguous consecutive memory
locations. These elements are accessed using an index, which is a number for each position within the array.

Fig. Array

Searching
Searching means finding something. In Data Structures, Searching is finding a data element in a data structure. To
search an element in a given array, there are some popular algorithms available:
 1. Linear Search
2. Sentinel Search
3. Binary Search
4. Fibonacci Search

Linear Search
Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one
by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search
continues till the end of the data collection.
Features of Linear Search Algorithm:
1. It is used for unsorted and unordered small list of elements.
2. It has a time complexity of O(n), which means the time is linearly dependent on the number of elements,
which is not bad, but not that good too. The best-case time complexity would be O(1).
3. It has a very simple implementation.
Example- Lets look at the step-by-step searching of the key element (say 47) in an array using the linear search
method.

Step 1
The linear search starts from the 0th index. Compare the key element with the value in the 0th index, 34.

However, 47 34. So it moves to the next element.

Step 2
Now, the key is compared with value in the 1st index of the array.

Still, 47 10, making the algorithm move for another iteration.

Step 3
The next element 66 is compared with 47. They are both not a match so the algorithm compares the further elements.

Step 4
Now the element in 3rd index, 27, is compared with the key value, 47. They are not equal so the algorithm is pushed
forward to check the next element.
Step 5
Comparing the element in the 4th index of the array, 47, to the key 47. It is figured that both the elements match.
Now, the position in which 47 is present, i.e., 4 is returned.

The output achieved is Element found at 4th index.

Divide and Conquer Strategy

Divide and Conquer is an algorithm design strategy in which we can break a single big problem into smaller sub-
problems, and solve the smaller sub-problems and combine their solutions to find the solution for the original big
problem, it becomes easier to solve the whole problem. The concept of Divide and Conquer involves three steps:
1. Divide the problem into multiple small problems.
2. Conquer the sub problems by solving them. The idea is to break down the problem into atomic subproblems,
where they are actually solved.
3. Combine the solutions of the subproblems to find the solution of the actual problem.

Fig. Divide and Conquer Strategy

Binary Search
Binary search is a fast search algorithm with run-time complexity of Ο(log n). Binary Search is used with sorted
array or list. In binary search, we follow the following steps:
1. We start by comparing the element to be searched with the element in the middle of the list/array.
2. If we get a match, we return the index of the middle element.
3. If we do not get a match, we check whether the element to be searched is less or greater than in value than the
middle element.
4. If the element/number to be searched is greater in value than the middle number, then we pick the elements on
the right side of the middle element (as the list/array is sorted, hence on the right, we will have all the numbers
greater than the middle number), and start again from the step 1.
 5. If the element/number to be searched is lesser in value than the middle number, then we pick the elements on
the left side of the middle element, and start again from the step 1.
Binary Search is useful when there is large number of elements in an array and they are sorted. So a necessary
condition for Binary search to work is that the list/array should be sorted.
Features of Binary Search Algorithm:
1. It is great to search through large sorted arrays.
2. It has a time complexity of O(log n) which is a very good time complexity.
3. It has a simple implementation.
Example- For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of
binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the
location of value 31 using binary search.

First, we shall determine half of the array by using this formula –

mid = low + (high – low) / 2
Here it is, 0 + (9 – 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at
location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know
that the target value must be in the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.
Low = mid + 1
mid = low + (high – low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is less than what we are looking for. So, the value must be in
the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less
numbers.

Algorithm:
Below is the complete algorithm for Linear Search:
Let arr[0..n-1] be the input array and the element to be searched be x.
1. Initialize an index variable I = 0.
2. While I < n:
3. Compare arr[i] with x.
4. If arr[i] == x, return index i.
5. Else, increment I by 1 to check the next element.
6. If no element matches x after the loop ends, return -1 indicating x is not present.

Flowchart:

Fig. Flowchart for Linear Search

Algorithm:
Below is the complete algorithm for Binary Search:
Let arr[0..n-1] be the sorted input array and the element to be searched be x.
1. Initialize two variables: low = 0 and high = n – 1.
2. While low <= high:
3. Calculate the middle index: mid = low + (high – low) / 2.
4. Compare arr[mid] with x.
 5. If arr[mid] == x, return index mid.
6. If x < arr[mid], set high = mid – 1 to search in the left sub-array.
7. Else, set low = mid + 1 to search in the right sub-array.
8. If the loop ends and no match is found, return -1 indicating x is not present.
Flowchart:

Fig. Flowchart for Binary Search

Input: Size of array Elements of array and Student Roll Numbers.

Output: Result based on Linear Search and Binary Search on Student Roll Numbers who attended training Program.

Conclusion: Linear Search and Binary Search were studied, understood and implemented on menu based program to
store roll numbers of student in array who attended training program using random order and sorted order
respectively using their respective functions successfully.
 Practical No. 2
Title: Sorting of an array using selection and bubble sort.
Problem Statement:
Consider the telephone book database of N clients. Make use of a hash table implementation to quickly look
up a client’s telephone number. Make use of linear probing, double hashing and quadratic collision handling
techniques.
Aim:
Write C/C++ program to the first year percentage of students in an array and display top five scores. Write function
for sorting array of floating point numbers in ascending order using -
• Selection Sort
• Bubble Sort.
Objectives:
• To study concept of Sorting.
• To understand implementation of various sorting algorithms like Selection Sort and Bubble Sort.
Prerequisites:
• Knowledge of C and C++ Programming.
• Knowledge of Arrays.
Outcomes:
• Implement use of Array.
• Implement various sorting algorithms.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Sorting
Sorting means arranging something in a specific order. In Data Structures, Sorting is arranging data elements in a
data structure in ascending or descending order. To sort an element in a given array, there are some popular
algorithms available:
1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort
7. Radix Sort
8. Bucket Sort

Selection Sort
This sorting algorithm is an in-place comparison based algorithm in which the list is divided into two parts, sorted
part at left end and unsorted part at right end. Initially sorted part is empty and unsorted part is entire list. Smallest
element is selected from the unsorted array and swapped with the leftmost element and that element becomes part of
sorted array. This process continues moving unsorted array boundary by one element to the right. This algorithm is
not suitable for large data sets as its average and worst case complexity are of O(n2) where n are no. of items.

Example- Consider the following array for Selection Sort. For the first position in the sorted list, the whole list is
scanned sequentially. The first position where 29 is stored presently, search the whole list and find that 13 is the
lowest value. So replace 29 with 13. After one iteration 13, which happens to be the minimum value in the list,
appears in the first position of the sorted list. For the second position, where 72 is residing, start scanning the rest of
the list in a linear manner and find that 29 is the second lowest value in the list and it should appear at the second
place. Swap these values. After two iterations, two least values are positioned at the beginning in a sorted manner.
The same process is applied to the rest of the items in the array -
 Fig. Selection Sort

Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison based algorithm in which each pair of
adjacent elements is compared and elements are swapped if they are not in order. This algorithm is not suitable for
large data sets as its average and worst case complexity are of O(n2) where n are no. of items.

Example- Consider the following array for Bubble Sort. Bubble sort starts with very first two elements, comparing
them to check which one is greater. In this case, value 1 is smaller than 5, so swap them. Next, compare 5 with 4. It is
found that 4 is smaller than 5 and these two values must be swapped. Next compare 5 and 2. 2 is smaller than 5. So
swap them. Next compare 5 and 8. They both are in already sorted positions. After one iteration, array is not sorted.
Use this array in next iteration and repeat above sorting process as -
 Fig. Bubble Sort

Algorithm:
Below is the complete algorithm for Selection Sort:
Let arr[0..n-1] be the input array to be sorted in ascending order.
1. Start from the first element (index i = 0) and repeat until i < n - 1:
2. Set the current index i as the minimum: min = i.
3. Iterate from j = i + 1 to n - 1:
If arr[j] < arr[min], update min = j.
4. After the inner loop ends, swap arr[i] and arr[min].
5. Repeat the process for the next position (I = I + 1) until the entire array is sorted.
Flowchart:

Fig. Flowchart for Selection Sort

Algorithm:
Below is the complete algorithm for Bubble Sort:
Let arr[0..n-1] be the input array to be sorted in ascending order.
1. Repeat the following steps for i = 0 to n - 2:
2. For each pass, compare adjacent elements from index j = 0 to n - i - 2:
If arr[j] > arr[j + 1], swap arr[j] and arr[j + 1].
3. At the end of each pass, the largest unsorted element "bubbles up" to its correct position.
4. Repeat the process until the array is fully sorted.
Flowchart:

Fig. Flowchart for Bubble Sort

Input: Size of array Elements of array and Student Percentages.

Output: Result based on Selection Sort and Bubble Sort on First Year Student Percentages who attended training
Program and display top 5 scores.

Conclusion: Selection Sort and Bubble Sort were studied, understood and implemented on program to store the first
year percentage of students in an array using their respective floating point number functions in ascending order and
top 5 scores were displayed successfully.
 Practical No. 3

Title: Implementing Hashing on Telephone Book Database.

Problem Statement:
Consider the telephone book database of N clients. Make use of a hash table implementation to quickly
look up a client’s telephone number. Make use of linear probing, double hashing and quadratic collision
handling techniques.
Aim:
Write C/C++ program to make use of a hash table implementation to quickly look up a client’s telephone
number from telephone book database of N clients. Make use of -
• Linear Probing
• Quadratic Probing
• Double Hashing
Objectives:
• To study concept of Hashing.
• To understand implementation of various collision handling techniques like Linear Probing, Quadratic
Probing and Double Hashing.
• To find record quickly using Hash Function.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming.
• Knowledge of Arrays and Searching.
Outcomes:
• Implement use of Array.
• Implement various collision handling techniques.
• Implement concept of hash table.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Hashing
Hashing is finding an address where the data is to be stored as well as located using a key with the help of the
algorithmic function. Hashing is the process of mapping data to a specific index in a data structure (Hash Table).
Hashing is the process of converting a given key into another value. Hashing is a technique used in data
structures that efficiently stores and retrieves data in a way that allows for quick access. Hashing is a method of
directly computing the address of the record with the help of a key by using a suitable mathematical function.

Key
A Key can be anything string or integer which determines an index or location for storage of an item in a data
structure.
Hash Function
A function that maps a key into the range [0 to Max − 1] which gives result which is used as an index (or
address) to hash table for storing and retrieving record. It receives the input key and returns the index of an
element in an array. It is an algebraic function denoted by f(x) or f(k) or F(x) or F(k) or h(x) or h(k) or H(x) or
H(k) where x is value which is used as key and k is key.
Format: Hash_Function = Key/Value Operator Table_Size/Value.
Example: H(x) = x % 10 is the Hash Function in below:
 Fig. Hash Function

Bucket
Bucket is an index position in hash table that can store more than one record.

Fig. Bucket

Hash Table
A hash table is a data structure that stores records in an array. It used to stores data in key, value pairs.

Fig. Hash Table

Hashing Mechanism
In Hashing, a key is used by Hash Function which converts key into index called Hash Value and stores key at
respective index into Bucket.
 Collision
The result of two or more keys hashing into the same address or same index is called collision.

Fig. Collision

Types of Hash Function

There are many ways of calculating the hash function. Some common ways are:
1. Division-Modulo method
2. Digit Folding method
3. Mid Square method

Division-Modulo Method

In Division-Modulo Method, the hash function divides the value k by number or size M and then uses the
remainder obtained.
Formula: h(k) = k mod M.
Example: k = 12345, M = 95. h(12345) = 12345 mod 95 = 90, h(26) = 26 % 10 = 6

Digit Folding Method

This method involves two steps: Divide the key-value k into a number of parts i.e. k1, k2, k3, …. ,kn , where
each part has the same number of digits except for the last part that can have lesser digits than the other parts.
Add the individual parts. The hash value is obtained by ignoring the last carry if any.
Formula: k = k1, k2, k3, k4, ….. , kn. s = k1+ k2 + k3 + k4 +….+ kn. h(K)= s
Example: k = 12345. k1 = 12, k2 = 34, k3 = 5. s = k1 + k2 + k3 = 12 + 34 + 5 = 51. h(K) = 51
 Mid Square Method

It involves two steps to compute the hash value: Square the value of the key k i.e. k2 and Extract the middle
digits as the hash value.
Formula: h(k) = Middle Digits of k x k.
Example: k = 60. k x k = 60 x 60 = 3600. h(60) = 60.

Overflow

Overflow is the condition where hash value is inserted into already occupied bucket. It means filling the bucket
more than it’s capacity. Example: If bucket capacity is 3 and 4th Value is inserted into the bucket, Overflow
condition occurs.

Fig. Overflow

Collision Resolution Techniques/Collision Handling Techniques

When the two or more different values have the same value, then the problem occurs between the two values is
known as a collision. As in example, when bucket is full, there is no space which results in collision between 2
or more keys or values. To avoid collision, Collision Resolution/Handling Techniques are used. Following are
the Collision Resolution/Handling Techniques:

1. Open Hashing or Closed Addressing

2. Closed Hashing or Open Addressing

Open Addressing/Closed Hashing

Open addressing is a collision resolution technique used in hash tables where all key-value pairs are stored
directly within the hash table itself. When a collision occurs (two keys hash to the same index), open addressing
uses a probing strategy to find an alternative empty slot for the new key-value pair.
 Probing

Probing in hashing refers to the method used to find an appropriate slot in a hash table when a collision occurs.

Types of Open Addressing/Closed Hashing Collision Resolution/Handling Techniques

In Open Addressing/Closed hashing, three techniques are used to resolve the collision:
1. Linear Probing
2. Quadratic Probing
3. Double Hashing

Linear Probing

When the collision occurs by mapping a new key to the cell already occupied by another key, then linear probing
technique searches for the closest free locations and adds a new key to that empty cell. Searching is performed
sequentially, starting from the position where the collision occurs till the empty cell is not found. If linear
probing reaches end of the table, searching starts from the beginning of the table.

Formula: h(x) = x % m = u. When Collision occurs, h(x) becomes h(x) = (u + i) % m, where m = table
size/value, u = value obtained by original hash function, x = key and i = increment (usually i = 1 but when end of
table is reached, search starts from beginning where i ≠ 1).

Example: 2,3,5,22,34. h(x) = x % 5.

Table Size m is 5. Keys are 2,3,5,22,34.
Step 1: h(2) = 2 % 5 = 2. Key is placed at 2nd index. Insert 2.
Step 2: h(3) = 3 % 5 = 3. Key is placed at 3rd index. Insert 3.
Step 3: h(5) = 5 % 5 = 5. Key is placed at 0th index. Insert 5.

Index Key or Bucket

0 5
1 Inserting 22, Overflow,
2 2 Collision,
3 3 Bucket is Full.
4

Step 4: h(22) = 22 % 5 = 2. Key is placed at 2nd index. Collision, Bucket is Full. Find next empty space
sequentially. Empty Space found at 4th index. Insert 22.

Index Key or Bucket

0 5
1
2 2
3 3
4 22 Inserting 34, Collision, Bucket is Full.

Step 5: h(34) = 34 % 5 = 34. Key is placed at 4th index. Collision, Bucket is Full. Find next empty space
sequentially. Reached End of the Table/List. Search from Beginning. Empty Space found at 1st index. Insert 34.

Index Key or Bucket

0 5
1 34
2 2
3 3
4 22
 Quadratic Probing

When the collision occurs by mapping a new key to the cell already occupied by another key, then quadratic
probing technique adds a new key to the empty cell using quadratic function/polynomial.

Formula: h(x) = x % m = u. When Collision occurs, h(x) becomes h(x) = (u + i2) % m, where m = table
size/value, u = value obtained by original hash function, x = key and i = increment.

Example: 2,3,5,22,34. h(x) = x % 5.

Table Size m is 5. Keys are 2,3,5,22,34.
Step 1: h(2) = 2 % 5 = 2. Key is placed at 2nd index. Insert 2.
Step 2: h(3) = 3 % 5 = 3. Key is placed at 3rd index. Insert 3.
Step 3: h(5) = 5 % 5 = 5. Key is placed at 0th index. Insert 5.

Index Key or Bucket

0 5
1 Inserting 22, Overflow,
2 2 Collision,
3 3 Bucket is Full.
4

Step 4: h(22) = 22 % 5 = 2. Key is placed at 2nd index. Collision, Bucket is Full. u = 2. h(x) = (u + i2) % 5.
i = 1, h(22) = (2 + 12) % 5 = (2 + 1) % 5 = 3 % 5 = 3. Key is placed at 3rd index. Collision, Bucket is Full.
i = 2, h(22) = (2 + 22) % 5 = (2 + 4) % 5 = 6 % 5 = 1. Key is placed at 1st index. Insert 22.

Index Key or Bucket

0 5
1 22
2 2
3 3
4

Step 5: h(34) = 34 % 5 = 34. Key is placed at 4th index. Insert 34.

Index Key or Bucket

0 5
1 22
2 2
3 3
4 34

Double Hashing

Double hashing uses the idea of applying a second hash function to key when a collision occurs.

Example: h(x) = x % m. When Collision occurs, h(k) becomes h1(k).

h2(x) = c – (x% m) or h2(x) = 1 + [x % (m-1)]
h(x) = [h1(x) + i h2(x)] % m, where m = table size/value, c = constant, x = key and i = increment.
Consider keys = 2,3,5,22,34. h(x) = x % 5.
Table Size m is 5. Keys are 2,3,5,22,34.
Since c is not given, either consider any value as c or consider h2(x) = 1 + [x % (m-1)].
h2(x) = 1 + [x % (m-1)] = 1 + [x % (5-1)] = 1 + (x % 4).
h(x) = [h1(x) + i h2(x)] % m = h(x) = [h1(x) + i h2(x)] % 5
Step 1: h(2) = 2 % 5 = 2. Key is placed at 2nd index. Insert 2.
Step 2: h(3) = 3 % 5 = 3. Key is placed at 3rd index. Insert 3.
Step 3: h(5) = 5 % 5 = 5. Key is placed at 0th index. Insert 5.
 Index Key or Bucket
0 5
1 Inserting 22, Overflow,
2 2 Collision,
3 3 Bucket is Full.
4

Step 4: h(22) = 22 % 5 = 2. Key is placed at 2nd index. Collision, Bucket is Full. h1(22) = 2.
h2(22) = 1 + (22 % 4) = 1 + 2 = 3. i = 1, h(x) = [h1(x) + i h2(x)] % 5 = [2 + 1 * 3] % 5 = 5 % 5 = 0.
Key is placed at 0th index. Collision, Bucket is Full. Increment i.
i = 2, h(x) = [h1(x) + i h2(x)] % 5 = [2 + 2 * 3] % 5 = [2 + 6] % 5 = 8 % 5 = 3.
Key is placed at 3rd index. Collision, Bucket is Full. Increment i.
i = 3, h(x) = [h1(x) + i h2(x)] % 5 = [2 + 3 * 3] % 5 = [2 + 9] % 5 = 11 % 5 = 1.
Key is placed at 1st index. Insert 22.

Index Key or Bucket

0 5
1 22
2 2
3 3
4

Step 5: h(34) = 34 % 5 = 34. Key is placed at 4th index. Insert 34.

Index Key or Bucket

0 5
1 22
2 2
3 3
4 34

Searching in Hashing

To search any particular key, its hash value is obtained using the hash function used. Using the hash value, that
bucket of the hash table is checked. If the required key is found, the key is searched. Otherwise, the subsequent
buckets are checked until the required key or an empty bucket is found. The empty bucket indicates that the key
is not present in the hash table.

Implementation in Program

Take input from user as number of clients. Consider them as N clients. Consider N as table size. Now use Hash
Function to Begin Insertion in Hash Table. Use Linear Probing, Quadratic Probing and Double Hashing for
Collision Handling in the Hash Table. Display Entries once all Phone numbers are added. Look Up a Telephone
Number by Searching in the Hash Table. To implement a hash table in C, a dynamic array can be created using
malloc() and sizeof(). In C++, the new operator can be used for dynamic allocation. Additionally, C++ STL
containers such as vector (for dynamic arrays) and unordered_map (for built-in hash tables) can also be used.

Algorithm:
1: Create a hash table with maximum N size.
2: Define Hash function.
3: Read the telephone no & user’s information to insert it into the hash table.
4: Insert telephone no value in the hash table.
5: If collision occurs, apply a separate chaining.
6: If a user requires inserting another data, go to step 4.
7: Display all the user’s data.
8: Read the telephone no from the user to be found.
9: find the data from the hash table.
10: Display the data with minimum no. of comparisons.
Flowchart:

Fig. Flowchart for Hashing

Input: Telephone book database of N clients and their telephone numbers.

Output: Results based on hash table implementation of telephone book database of N clients by using collision
handling techniques like Linear Probing, Quadratic Probing, Double Hashing, displaying them and finding
client’s telephone number.

Conclusion: Collision handling techniques like Linear Probing, Quadratic Probing and Double Hashing were
studied, understood and implemented on program to make telephone book database of N clients using hash table,
store their telephone numbers, display them and quickly look them up successfully.
 Practical No. 4

Title: Implement singly linked list & its operations.

Problem Statement:
The Department of Computer Engineering has a student’s club named ’Pinnacle Club’. Students of the second,
third and final year of the department can be granted membership on request. Similarly one may cancel the
membership of the club. First node is reserved for the president of the club and the last node is reserved for the
secretary of the club. Write a program to maintain club member‘s information using singly linked lists. Store
student PRN and Name. Write functions to:
a) Add and delete the members as well as president or even secretary. b) Compute total number of members
of club c) Display members d) Two linked lists exist for two divisions. Concatenate two lists.
Aim:
Write C/C++ program to maintain Computer Engineering Department student’s club named ’Pinnacle Club’
member‘s information using singly linked lists, store student PRN and Name, use first node as president of the
club and the last node as the secretary of the club. Write functions to:
• Add and delete the members as well as president or even secretary.
• Compute total number of members of club.
• Display members.
• Two linked lists exist for two divisions. Concatenate two lists.
Objectives:
• To study Linked List Data Structure.
• To study & implement singly linked list.
• To maintain club member's information by performing different operations like add, delete, reverse,
concatenate on singly linked list.
Prerequisites:
• Knowledge of C and C++ Programming.
Outcomes:
• Implement Singly Linked list and perform various operations on it.
• Solve real world problem logically using Singly Linked List.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Linked List

A linked list is a linear data structure where elements (also called nodes) are stored in separate memory
locations. Unlike arrays, the nodes in a linked list are not stored in contiguous memory locations.
Each node contains two components:-
Data: The actual information stored in the node.
Pointer/Reference: A reference or pointer to the next node in the sequence (in the case of a singly linked list, or
it may reference both the next and previous nodes in the case of a doubly linked list).
Each node consists of its own data and the address of the next node and forms a chain.
 Fig. Linked List

Terminologies of Linked List

Node is an item in a linked list. Each node contains a piece of list data and the location of the next node (item).
Link (of a node) the location of the next node.
Head node is the first node in a linked list.
Head pointer points to the head node.
Null pointer is the pointer which is not need in it. (linked list is empty)

Fig. Linked List

Types of Linked List

There are 3 different implementations of Linked List available, they are:

1. Singly Linked List (SLL)
2. Doubly Linked List (DLL)
3. Circular Linked List (CLL)
1. Circular Singly Linked List (CSLL) or Singly Circular Linked List (SCLL)
2. Circular Doubly Linked List (CDLL) or Doubly Circular Linked List (DCLL)
 Singly Linked List (SLL)

A singly linked list consists of nodes, where each node contains data and a pointer to the next node. The last
node's pointer is set to NULL, indicating the end of the list.
Data: The actual value the node holds.
Next pointer: A reference to the next node in the list. If a node is the last node, its next pointer is set to NULL.

A singly linked list allows traversal in only one direction (from the first node to the last node).

Fig. Singly Linked List

Concepts of Singly Linked List:

Head: The first node in the linked list. This is the entry point to access the entire list.
Tail: The last node in the linked list. Its next pointer is NULL.
Node: Each element in the list that holds data and a reference to the next node.
Traversal: Moving from the head node to the last node (or NULL), accessing each node one by one.
Insertion: Adding a node at the beginning, middle, or end of the list.
Deletion: Removing a node from the beginning, middle, or end of the list.

Advantages of Singly Linked List

Dynamic Size: Linked lists allow dynamic memory allocation, meaning the list size can grow or shrink as
needed without wasting memory.
Efficient Insertion/Deletion: Inserting or deleting a node in a linked list (especially at the beginning or middle)
is much faster compared to arrays because no shifting of elements is required.
No Wasted Space: Unlike arrays, linked lists do not need a predefined size, so no extra space is wasted if the list
doesn't fill the entire allocated space.

Disadvantages of Singly Linked List

Random Access: Linked lists do not support random access. To access a specific element, you must traverse the
list from the beginning, which takes O(n) time.
Extra Memory: Each node requires extra memory for storing the pointer/reference to the next node. This leads
to higher memory overhead compared to arrays.
Complexity in Implementation: Manipulating pointers in a linked list is more complex than dealing with
arrays, especially when handling edge cases like empty lists, single-node lists, or deleting the last node.

Singly Linked List as an Abstract Data Type (ADT)/Operations on Singly Linked List

An Abstract Data Type (ADT) defines a data structure purely in terms of its operations without specifying the
implementation details. For a Singly Linked List (SLL), the ADT would include the following operations:
Insert: Add a new node at the beginning, end, or after a specified node.
Delete: Remove a node from the beginning, end, or a specified position.
Search: Find if a given element exists in the list.
Traversal: Visit all nodes in the list to process or print them.
Size: Return the number of nodes in the list.
Is Empty: Check if the list is empty.
Print: Prints the list
1. Insert - This function takes the start node and data to be inserted as arguments. New node is inserted at the
end so, iterate through the list till we encounter the last node. Then, allocate memory for the new node and put
data in it. Lastly, store the address in the next field of the new node as NULL.

2. Delete - This function takes the start node (as pointer) and data to be deleted as arguments. Firstly, go to the
node for which the node next to it has to be deleted, If that node points to NULL (i.e. pointer->next=NULL) then
the element to be deleted is not present in the list. Else, now pointer points to a node and the node next to it has
to be removed, declare a temporary node (temp) which points to the node which has to be removed. Store the
address of the node next to the temporary node in the next field of the node pointer (pointer->next = temp-
>next). Thus, by breaking the link we removed the node, which is next to the pointer (which is also temp).
Because we deleted the node, we no longer require the memory used for it, free() will deallocate the memory.

3. Find - This function takes the start node (as pointer) and data value of the node (key) to be found as
arguments. First node is dummy node so, start with the second node. Iterate through the entire linked list and
search for the key. Until next field of the pointer is equal to NULL, check if pointer->data = key. If it is then the
key is found else, move to the next node and search (pointer = pointer -> next). If key is not found return 0, else
return 1.

Creation in Singly Linked List

– Step 1: Define a Node structure with two members data and next
– Step 2: Define a Node pointer 'head' and set it to NULL.

Structure definition
typedef struct node {
int data;
struct node* next;
}Node;

Class definition
class Node {
int data;
Node* next;
};

Insertion in Singly Linked List

In a singly linked list, the insertion operation can be performed in three ways. They are as follows:
– Inserting At Beginning of the list
– Inserting At End of the list
– Inserting At Specific location in the list

INSERTING AT BEGINNING OF THE LIST

Following are the steps to insert a new node at beginning of the singly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether list is Empty (head == NULL)
– Step 3: If it is Empty then, set newNode→next = NULL and head = newNode.
– Step 4: If it is Not Empty then, set newNode→next = head and head = newNode.

INSERTING AT END OF THE LIST

Following are the steps to insert a new node at end of the singly linked list:
– Step 1: Create a newNode with given value and newNode → next as NULL.
– Step 2: Check whether list is Empty (head == NULL).
– Step 3: If it is Empty then, set head = newNode.
– Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
– Step 5: Keep moving the temp to its next node until it reaches to the last node in the list (until temp → next is
equal to NULL).
– Step 6: Set temp → next = newNode.

INSERTING AT SPECIFIC LOCATION IN THE LIST (AFTER A NODE)

Following are the steps to insert a new node after a node in the singly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether list is Empty (head == NULL)
– Step 3: If it is Empty then, set newNode → next = NULL and head = newNode.
– Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
– Step 5: Keep moving the temp to its next node until it reaches to the node after which we want to insert the
newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert
the newNode).
– Step 6: Every time check whether temp is reached to last node or not. If it is reached to last node then display
'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise move the
temp to next node.
– Step 7: Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion in Singly Linked List

In a singly linked list, the deletion operation can be performed in three ways. They are as follows:
– Deleting From Beginning of the list
– Deleting From End of the list
– Deleting a Specific Node by Value

DELETING FROM BEGINNING OF THE LIST

Following are the steps to delete a node from the beginning of the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If it is Not Empty, define a node pointer temp and assign it to head.
– Step 4: Move head to the next node (head = head → next).
– Step 5: Free the memory of temp (i.e., free(temp) in C/C++ or delete temp).

DELETING FROM END OF THE LIST

Following are the steps to delete a node from the end of the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the list has only one node (head → next == NULL), free that node and set head = NULL.
– Step 4: If there are multiple nodes, define two node pointers: temp and prev.
– Step 5: Initialize temp = head and loop until temp → next == NULL (to reach the last node).
– Step 6: Keep updating prev as the node before temp.
– Step 7: Set prev → next = NULL.
– Step 8: Free the memory of temp.
 DELETING A SPECIFIC NODE BY VALUE

Following are the steps to delete a node with a given value in the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the node to be deleted is the first node (head → data == value):
– Assign a temp pointer to head.
– Move head = head → next.
– Free the temp node.
– Step 4: If the node is not the first node, define two pointers: temp and prev.
– Step 5: Initialize temp = head and loop until temp → data == value or temp == NULL.
– Step 6: If temp == NULL, display "Given node not found in the list!!! Deletion not possible!!!" and terminate.
– Step 7: Else, set prev → next = temp → next.
– Step 8: Free the memory of temp.

Displaying in Singly Linked List

Following are the steps to display the elements of a singly linked list:
– Step 1: Check whether list is Empty (head == NULL)
– Step 2: If it is Empty then, display 'List is Empty!!!' and terminate the function.
– Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
– Step 4: Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
– Step 5: Finally display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Algorithm:

1. Start
2. Define node structure by using class or structure
3. Define head & tail pointer assign to null inside the constructor.
4. Define methods for create(),getnode(),insert_node(),delete_node(),display();
5. Create()
While(1)
Begin
Enter any more node to be added(y/n)
If(ans==n) then break
Else NewNode=GetNode();
Insert_node(NewNode);
End

Algorithm for creation of node()

Begin
Newnode=new Node;
Enter data for new node
Assign Link field to NULL;
Return that node to create function
End

Algorithm for Insertion of node()

Create one pointer which will start from head

Node *temp=head
Initialize count=1
Enter the position where you want insert the node;
if(pos==1) then
Assign the newnode at head position
Else while(count!=pos-1)
Begin temp=temp->link ; // increment the temp pointer
if(temp==NULL) then Begin
Flag=0;
break;
Count++;
End
If(flag==1) then
Begin NewNode->link=temp->link;
temp->link=NewNode;
End
Else
Print position is not found
End
End

Algorithm for Display of node()

Node *temp=head;
if(temp==NULL) then
print list is empty
Else Begin
While(temp!=NULL)
Begin
Display node data
Increment the pointer i.e. temp=temp->link;
End
End

Algorithm for Deletion of node()

Initialize int count=1,flag=1;

Node *curr,*temp;
temp=head;
if(pos==1) then
Begin head=head->link;
Delete temp;
End
Else
Begin
While (count!=pos-1)
Begin
Increment the pointer till that position temp=temp->link;
temp->link=curr->link;
delete curr;
End
Else
Print position is not found
End

Algorithm for Concatenation of node()

Begin
Node *concatenate (node *head1, node *head2) {
Node *p;
if (head1 == NULL) return head 2;
if (head2 == NULL) return head 1;
p=head 1;
while(p->next!=NULL)
End

PRN PRN PRN PRN

PRN PRN
Name Name Name Name Name Name
Fig. Implementation of Program (Singly Linked List)

Flowchart:

Fig. Flowchart for Singly Linked List

Input: Computer Engineering Department student’s club named ’Pinnacle Club’ member‘s information Student
PRN and Name.
Output: Results based on club member‘s information using singly linked lists operations like Addition and
deletion of the members as well as president or even secretary, Computation total number of members of club,
Displaying members, Two linked lists exist for two divisions and Concatenating two lists.

Conclusion: Computer Engineering Department student’s club named ’Pinnacle Club’ member‘s information
using singly linked lists was understood, implemented and maintained to perform operations like Addition and
deletion of the members as well as president or even secretary, Computation total number of members of club,
Displaying members, Two linked lists exist for two divisions and Concatenating two lists successfully.
 OR
Practical No. 4

Title: Implement singly linked list & its operations.

Problem Statement:
Second year Computer Engineering class, set A of students like Vanilla Ice-cream and set B of students like
butterscotch ice-cream. Write a program to store two sets using a linked list. compute and display-
a) Set of students who like both vanilla and butterscotch
b) Set of students who like either vanilla or butterscotch or not both
c) Number of students who like neither vanilla nor butterscotch
Aim:
Write C/C++ program to store two sets of Second year Computer Engineering class, set A of students like
Vanilla Ice-cream and set B of students like butterscotch ice-cream using a linked list. Compute and display:
• Set of students who like both vanilla and butterscotch.
• Set of students who like either vanilla or butterscotch or not both.
• Number of students who like neither vanilla nor butterscotch.
Objectives:
• To study Linked List Data Structure.
• To study & implement singly linked list.
• To understand the set and it’s operations.
• To store two sets using a linked list and perform Set Operations.
Prerequisites:
• Knowledge of C and C++ Programming, Sets and its Types, Operations, Properties/Laws.
Outcomes:
• Implement Singly Linked list and perform various operations on it.
• Solve real world problem logically using Singly Linked List.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Linked List

A linked list is a linear data structure where elements (also called nodes) are stored in separate memory
locations. Unlike arrays, the nodes in a linked list are not stored in contiguous memory locations.
Each node contains two components:-
Data: The actual information stored in the node.
Pointer/Reference: A reference or pointer to the next node in the sequence (in the case of a singly linked list, or
it may reference both the next and previous nodes in the case of a doubly linked list).
Each node consists of its own data and the address of the next node and forms a chain.
 Fig. Linked List

Terminologies of Linked List

Node is an item in a linked list. Each node contains a piece of list data and the location of the next node (item).
Link (of a node) the location of the next node.
Head node is the first node in a linked list.
Head pointer points to the head node.
Null pointer is the pointer which is not need in it. (linked list is empty)

Fig. Linked List

Types of Linked List

There are 3 different implementations of Linked List available, they are:

1. Singly Linked List (SLL)
2. Doubly Linked List (DLL)
3. Circular Linked List (CLL)
1. Circular Singly Linked List (CSLL) or Singly Circular Linked List (SCLL)
2. Circular Doubly Linked List (CDLL) or Doubly Circular Linked List (DCLL)
 Singly Linked List (SLL)

A singly linked list consists of nodes, where each node contains data and a pointer to the next node. The last
node's pointer is set to NULL, indicating the end of the list.
Data: The actual value the node holds.
Next pointer: A reference to the next node in the list. If a node is the last node, its next pointer is set to NULL.
A singly linked list allows traversal in only one direction (from the first node to the last node).

Fig. Singly Linked List

Concepts of Singly Linked List:

Head: The first node in the linked list. This is the entry point to access the entire list.
Tail: The last node in the linked list. Its next pointer is NULL.
Node: Each element in the list that holds data and a reference to the next node.
Traversal: Moving from the head node to the last node (or NULL), accessing each node one by one.
Insertion: Adding a node at the beginning, middle, or end of the list.
Deletion: Removing a node from the beginning, middle, or end of the list.

Singly Linked List as an Abstract Data Type (ADT)/Operations on Singly Linked List

An Abstract Data Type (ADT) defines a data structure purely in terms of its operations without specifying the
implementation details. For a Singly Linked List (SLL), the ADT would include the following operations:
Insert: Add a new node at the beginning, end, or after a specified node.
Delete: Remove a node from the beginning, end, or a specified position.
Search: Find if a given element exists in the list.
Traversal: Visit all nodes in the list to process or print them.
Size: Return the number of nodes in the list.
Is Empty: Check if the list is empty.
Print: Prints the list

1. Insert - This function takes the start node and data to be inserted as arguments. New node is inserted at the
end so, iterate through the list till we encounter the last node. Then, allocate memory for the new node and put
data in it. Lastly, store the address in the next field of the new node as NULL.

2. Delete - This function takes the start node (as pointer) and data to be deleted as arguments. Firstly, go to the
node for which the node next to it has to be deleted, If that node points to NULL (i.e. pointer->next=NULL) then
the element to be deleted is not present in the list. Else, now pointer points to a node and the node next to it has
to be removed, declare a temporary node (temp) which points to the node which has to be removed. Store the
address of the node next to the temporary node in the next field of the node pointer (pointer->next = temp-
>next). Thus, by breaking the link we removed the node, which is next to the pointer (which is also temp).
Because we deleted the node, we no longer require the memory used for it, free() will deallocate the memory.

3. Find - This function takes the start node (as pointer) and data value of the node (key) to be found as
arguments. First node is dummy node so, start with the second node. Iterate through the entire linked list and
search for the key. Until next field of the pointer is equal to NULL, check if pointer->data = key. If it is then the
key is found else, move to the next node and search (pointer = pointer -> next). If key is not found return 0, else
return 1.
 Creation in Singly Linked List

– Step 1: Define a Node structure with two members data and next
– Step 2: Define a Node pointer 'head' and set it to NULL.

Structure definition
typedef struct node {
int data;
struct node* next;
}Node;

Class definition
class Node {
int data;
Node* next;
};

Insertion in Singly Linked List

In a singly linked list, the insertion operation can be performed in three ways. They are as follows:
– Inserting At Beginning of the list
– Inserting At End of the list
– Inserting At Specific location in the list

INSERTING AT BEGINNING OF THE LIST

Following are the steps to insert a new node at beginning of the singly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether list is Empty (head == NULL)
– Step 3: If it is Empty then, set newNode→next = NULL and head = newNode.
– Step 4: If it is Not Empty then, set newNode→next = head and head = newNode.

INSERTING AT END OF THE LIST

Following are the steps to insert a new node at end of the singly linked list:
– Step 1: Create a newNode with given value and newNode → next as NULL.
– Step 2: Check whether list is Empty (head == NULL).
– Step 3: If it is Empty then, set head = newNode.
– Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
– Step 5: Keep moving the temp to its next node until it reaches to the last node in the list (until temp → next is
equal to NULL).
– Step 6: Set temp → next = newNode.

INSERTING AT SPECIFIC LOCATION IN THE LIST (AFTER A NODE)

Following are the steps to insert a new node after a node in the singly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether list is Empty (head == NULL)
– Step 3: If it is Empty then, set newNode → next = NULL and head = newNode.
– Step 4: If it is Not Empty then, define a node pointer temp and initialize with head.
– Step 5: Keep moving the temp to its next node until it reaches to the node after which we want to insert the
newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert
the newNode).
– Step 6: Every time check whether temp is reached to last node or not. If it is reached to last node then display
'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise move the
temp to next node.
– Step 7: Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion in Singly Linked List

In a singly linked list, the deletion operation can be performed in three ways. They are as follows:
– Deleting From Beginning of the list
– Deleting From End of the list
– Deleting a Specific Node by Value

DELETING FROM BEGINNING OF THE LIST

Following are the steps to delete a node from the beginning of the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If it is Not Empty, define a node pointer temp and assign it to head.
– Step 4: Move head to the next node (head = head → next).
– Step 5: Free the memory of temp (i.e., free(temp) in C/C++ or delete temp).

DELETING FROM END OF THE LIST

Following are the steps to delete a node from the end of the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the list has only one node (head → next == NULL), free that node and set head = NULL.
– Step 4: If there are multiple nodes, define two node pointers: temp and prev.
– Step 5: Initialize temp = head and loop until temp → next == NULL (to reach the last node).
– Step 6: Keep updating prev as the node before temp.
– Step 7: Set prev → next = NULL.
– Step 8: Free the memory of temp.

DELETING A SPECIFIC NODE BY VALUE

Following are the steps to delete a node with a given value in the singly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the node to be deleted is the first node (head → data == value):
– Assign a temp pointer to head.
– Move head = head → next.
– Free the temp node.
– Step 4: If the node is not the first node, define two pointers: temp and prev.
– Step 5: Initialize temp = head and loop until temp → data == value or temp == NULL.
– Step 6: If temp == NULL, display "Given node not found in the list!!! Deletion not possible!!!" and terminate.
– Step 7: Else, set prev → next = temp → next.
– Step 8: Free the memory of temp.

Displaying in Singly Linked List

Following are the steps to display the elements of a singly linked list:
– Step 1: Check whether list is Empty (head == NULL)
– Step 2: If it is Empty then, display 'List is Empty!!!' and terminate the function.
– Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
– Step 4: Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
– Step 5: Finally display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Set

A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using
set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any
changes in the set. Example: A = {1, 2, 3, 4, 5}

Types of Set

1. Empty Set or Null Set

2. Subset
3. Proper Subset
4. Superset
5. Disjoint Sets
6. Universal Set

Empty Set/Null Set

A set which does not contain any element is called an empty set or void set or null set. It is denoted by { } or Ø

Subset

A subset is a set whose elements are all members of another set. A set A is a subset of another set B if all
elements of the set A are elements of the set B. In other words, the set A is contained inside the set B. The subset
relationship is denoted as A ⊆ B. Example: A = {1,2,3}, B = {1,2}, B ⊆ A.

Proper Subset

A proper subset is a subset of a bigger set that has fewer members while still including unique elements from the
original set. A proper subset of a set A is a subset of A that is not equal to A. In other words, if B is a proper
subset of A, then all elements of B are in A but A contains at least one element that is not in B. Set A is a proper
subset of set B (A ⊂ B) if all of the elements of set A are members of set B, but there is at least one element of
set B that is not a member of set A (A ≠ B). Example: If A = {2,5,7} is a subset of B = {2,5,7} then it is not a
proper subset of B = {2,5,7} but, A = {2,5} is a subset of B = {2,5,7} and is a proper subset

Superset

A superset is a set of elements containing all of the elements of another set. In other words, A is a superset of B
if it contains all of the elements of B. It is represented as A ⊃ B. Example: If set A = {1, 2, 3, 4} and set B = {1,
3, 4}, then set A is the superset of B.

Disjoint Sets

Disjoint Sets are the two sets where there are no common elements in both sets. Example: A = {1,2,3,4} B =
{5,6,7,8}. Here, set A and set B are disjoint sets.

Universal Set

A universal set is a set which contains all the elements or objects of other sets, including its own elements. It is
usually denoted by the symbol 'U'. Example: If A = {1,2,3} and B = {2,3,4,5}, then universal set is
U = {1,2,3,4,5}
 Compliment of a Set

The complement of a set is the set of all elements in the universal set that are not in the original set. It is denoted
by A’ or Ac. Example: If A = {1,2,3} and universal set is U = {1,2,3,4,5} then A’ = {4,5}

Cardinal Number of a Set

The number of distinct elements or members in a finite set (set with limited number/finite number of elements) is
known as the cardinal number of a set. Basically, through cardinality, we define the size of a set. The cardinal
number of a set A is denoted as n(A), where A is any set and n(A) is the number of members in set A. Example:
If A = {2, 3, 5, 7} then n(A) = 4.

Operations of Set

Following are the operations of the Set:

1. Union
2. Intersection
3. Difference
4. Symmetric Difference

Union

The union of sets A and B (denoted by A ∪ B) is the set of elements which are in A, in B, or in both A and B.
Hence, A ∪ B = {x | x ∈ A OR x ∈ B}. Example − If A = {10, 11, 12, 13} and B = {13, 14, 15}, then A ∪ B =
{10, 11, 12, 13, 14, 15}. (The common element occurs only once)

Intersection

The intersection of sets A and B (denoted by A ∩ B) is the set of elements which are in both A and B. Hence,
A ∩ B = {x | x ∈ A AND x ∈ B}. Example − If A = {11, 12, 13} and B = {13, 14, 15}, then A ∩ B = {13}.

Figure: Intersection of Two Sets

 Difference

The difference of sets A and B (denoted by A − B) is the set of elements which are only in A but not in B.
Hence, A − B = {x | x ∈ A AND x ∉ B}. Example − If A = {10, 11, 12, 13} and B = {13, 14, 15}, then (A− B) =
{10, 11, 12} and (B − A) = {14, 15}. Here, (A − B) ≠ (B − A)

Figure: Difference between Two Sets

Symmetric Difference

The symmetric difference of sets A and B (denoted by A Δ B) is the difference between set of elements which
are only in A but not in B and set of elements which are only in B but not in A. Hence, A Δ B = (A - B) U (B -
A). There is an alternate formula for the symmetric difference of sets which says A Δ B = (A ∪ B) - (A ∩ B).
Example − If A = {10, 11, 12, 13} and B = {13, 14, 15}, then (A− B) = {10, 11, 12} and (B − A) = {14, 15}.
Thus, A Δ B = (A - B) U (B - A) = {}
 Properties of Sets/Laws of Sets

Commutative Property:
• A∪B=B∪A
• A∩B=B∩A

Associative Property:
• A ∪ (B ∪ C) = (A ∪ B) ∪ C
• A ∩ (B ∩ C) = (A ∩ B) ∩ C

Distributive Property:
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

De morgan’s Law:
• Law of union:
(A ∪ B)’ = A’ ∩ B’
• Law of intersection:
(A ∩ B)’ = A’ ∪ B’

Complement Law:
• A ∪ A’ = A’ ∪ A = U
• A ∩ A’ = ∅

Idempotent Law and Law of a null and universal set:

For any finite set A
• A∪A=A
• A∩A=A
• ∅’ = U
• ∅ = U’

Algorithm:

1. Start
2. Define node structure by using class or structure
3. Define head & tail pointer assign to null inside the constructor.
4. Define methods for create(), getnode(), append(), delete_node(), display(), Union(), Intersection(),
Difference();
5. Create()
While(1)
Begin
Enter any more node to be added(y/n)
If(ans==n) then break
Else
NewNode=GetNode();
Append(NewNode);
Union();
Intersection();
Difference();
End
Algorithm for Creation of node create()

Begin
Newnode=new Node;
Enter data for new node
Assign Link field to NULL;
Return that node to create function
End

Algorithm for Insertion of node()

Create one pointer which will start from head

Node *temp=head
Initialize count=1
Enter the position where you want insert the node;
if(pos == 1) then
Assign the newnode at head position
Else
while(count != pos-1)
Begin temp = temp -> link ; // increment the temp pointer
if(temp == NULL) then Begin
Flag=0;
break;
Count++;
End
If(flag == 1) then
Begin NewNode->link = temp->link;
temp->link = NewNode;
End
Else
Print position is not found
End
End

Algorithm for getting data of node getnode()

Begin
Newnode = new Node;
Enter data for new node
Assign Link field to NULL;
Return that node to create function
End

Algorithm for display()

Node *temp=head;
if(temp==NULL) then
print list is empty
Else Begin
While(temp != NULL)
Begin
Display node data
Increment the pointer i.e. temp=temp->link;
End
End
Algorithm for appending a node append()

if(head==NULL) then
head=NewNode;
tail=NewNode;
Else
Begin
tail->link=NewNode;
tail=NewNode;
End

Algorithm for Deletion of node delete_node()

Initialize int count=1, flag=1;

Node *curr, *temp;
temp=head;
if(pos==1) then
Begin head=head->link;
Delete temp;
End
Else
Begin
While (count != pos-1)
Begin
Increment the pointer till that position temp=temp->link;
temp->link = curr->link;
delete curr;
End
Else
Print position is not found
End

Algorithm to find Union of two linked list Union()

Initialization flag = 0;
Node *temp1 = List1.head, *temp2 = List2.head;
Copy the rollno. of vanilla list into resultant list
While(temp2 != Null)
Begin
While(temp1!=Null)
Begin
If (List2[i])==List1[j]) then
Set flag=1;
break;
If(flag==0) then
Add the remaining rollno. to resultant list
End
End

Algorithm to find intersection of two linked list Intersection()

Node *temp1 = List1.head, *temp2 = List2.head;

While(temp1!=Null)
begin
While(temp2!=Null)
begin
If(List[i]==List[j]) then
Add that rollno. into the resultant list
End
Display resultant list

Algorithm to find Difference of two linked list Difference()

Initialization flag=1;
Node *temp1 = List1.head, *temp2 = List2.head;
While(temp1 != Null)
Begin
While(temp2 != Null)
Begin
If (list1[i]==list2[j])
Flag=0;
Break;
If(flag==1)
Copy list2 rollno. to resultant list
End
End
Display resultant list

Flowchart:

Union Operation

Fig. Flowchart for Union Operation

 Intersection Operation

Fig. Flowchart for Intersection Operation

 Difference Operation

Fig. Flowchart for Difference Operation

Input: Second year Computer Engineering class having two sets set A of students liking Vanilla Ice-cream and
set B of students liking butterscotch ice-cream information Student Roll Number and Name.
Output: Results based on operations on two sets of students liking Vanilla Ice-cream and liking butterscotch
ice-cream like Union, Intersection and Difference using singly linked lists operations like Addition and deletion
of the students, Computation total number of students who neither like vanilla nor butterscotch, Displaying Set
of students liking vanilla and butterscotch and Set of students who either like vanilla or butterscotch but not both,
Two linked lists exist for two sets and Appending two lists.

Conclusion: Computer Engineering Second year class having two sets set A of students liking Vanilla Ice-cream
and set B of students liking butterscotch ice-cream information using singly linked lists was understood,
implemented and stored to perform operations like Union, Intersection, Difference, Addition and deletion of the
students, Computation total number of students who neither like vanilla nor butterscotch, Displaying Set of
students liking vanilla and butterscotch and Set of students who either like vanilla or butterscotch but not both,
Two linked lists exist for two sets and Appending two lists successfully.
 Practical No. 5

Title: Implement doubly linked list & its operations.

Problem Statement:
The ticket booking system of Cinemax theater has to be implemented. There are 10 rows and 7 seats in each row.
Doubly linked list has to be maintained to keep track of free seats in rows. Assume some random booking to start
with. Use an array to store pointers (Head pointer) to each row. On demand
a) The list of available seats is to be displayed b) The seats are to be booked c) The booking can be
cancelled.
Aim:
Write C/C++ program to implement ticket booking system of Cinemax theater having 10 rows and 7 seats in
each row using Doubly linked list to keep track of free seats in rows and array to store pointers (Head pointer) to
each row. On demand:
• The list of available seats is to be displayed.
• The seats are to be booked.
• The booking can be cancelled.
Objectives:
• To study Linked List Data Structure.
• To study & implement doubly linked list.
• To perform Doubly linked list for cinemax ticket booking.
• To display available seats, book and cancel seats.
Prerequisites:
• Knowledge of C and C++ Programming, Knowledge of ticket booking.
Outcomes:
• Implement Doubly Linked list and perform various operations on it.
• Solve real world problem logically using Doubly Linked List.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Linked List

A linked list is a linear data structure where elements (also called nodes) are stored in separate memory
locations. Unlike arrays, the nodes in a linked list are not stored in contiguous memory locations.
Each node contains two components:-
Data: The actual information stored in the node.
Pointer/Reference: A reference or pointer to the next node in the sequence (in the case of a singly linked list, or
it may reference both the next and previous nodes in the case of a doubly linked list).
Each node consists of its own data and the address of the next node and forms a chain.
 Fig. Linked List

Terminologies of Linked List

Node is an item in a linked list. Each node contains a piece of list data and the location of the next node (item).
Link (of a node) the location of the next node.
Head node is the first node in a linked list.
Head pointer points to the head node.
Null pointer is the pointer which is not need in it. (linked list is empty)

Fig. Linked List

Types of Linked List

There are 3 different implementations of Linked List available, they are:

1. Singly Linked List (SLL)
2. Doubly Linked List (DLL)
3. Circular Linked List (CLL)
1. Circular Singly Linked List (CSLL) or Singly Circular Linked List (SCLL)
2. Circular Doubly Linked List (CDLL) or Doubly Circular Linked List (DCLL)
 Doubly Linked List (DLL)

A doubly linked list is a type of linked list in which each node contains 3 parts, a data part and two addresses,
one points to the previous node and one for the next node. It differs from the singly linked list as it has an extra
pointer called previous that points to the previous node, allowing the traversal in both forward and backward
directions.

A doubly linked list is represented as the pointer to the head (i.e. first node) in the list. Each node in a doubly
linked list contains three components:-
1. Data: data is the actual information stored in the node.
2. Next: next is a pointer that links to the next node in the list.
3. Prev: previous is a pointer that links to the previous node in the list.

Fig. Doubly Linked List

Concepts of Doubly Linked List:

Head: The first node in the linked list. This is the entry point to access the entire list.
Tail: The last node in the linked list. Its next pointer is NULL.
Node: Each element in the list that holds data and a reference to the next node.
Prev/Left/Previous Pointer/Left Pointer: A reference or pointer to the previous node in the list.
Next/Right/Next Pointer/Right Pointer: A reference or pointer to the next node in the list.

Doubly Linked List as an Abstract Data Type (ADT)/Operations on Doubly Linked List

An Abstract Data Type (ADT) defines a data structure in terms of its operations and behavior, without
specifying the internal implementation. For a Doubly Linked List (DLL), the ADT would include the following
operations:
 • Insert: Add a new node at the beginning, end, or after a specified node.
• Delete: Remove a node from the beginning, end, or a specified position.
• Search: Find if a given element exists in the list.
• Traversal: Visit all nodes in the list to process or print them.
• Size: Return the number of nodes in the list.
• Is Empty: Check if the list is empty.
• Print: Prints the list.

1. Insert - This function takes the start node and data to be inserted as arguments. The new node is inserted at
the end, so iterate through the list until the last node is reached. Then, allocate memory for the new node and
store the data in it. Set the next field of the last node to point to the new node, and set the previous field of the
new node to point to the last node. Lastly, set the next field of the new node as NULL.

2. Delete - This function takes the start node (as pointer) and data to be deleted as arguments. Traverse the list to
find the node that contains the given data. If such a node is found, adjust the next pointer of the previous node to
skip the node to be deleted, and adjust the previous pointer of the next node to bypass the node being removed. If
the node to be deleted is at the beginning or end, update the necessary head or tail pointers accordingly. Once the
node is disconnected from the list, its memory is no longer required and can be deallocated.

3. Find - This function takes the start node (as pointer) and the data value (key) to be found as arguments. Start
from the first actual node and traverse the list one node at a time. At each step, check whether the current node’s
data matches the key. If a match is found, the key exists in the list. If the end of the list is reached without
finding the key, then the element is not present

Creation in Doubly Linked List

– Step 1: Define a Node structure with two members data, prev and next
– Step 2: Define a Node pointer 'head' and set it to NULL.

Structure definition
typedef struct node {
int data;
struct node* prev;
struct node* next;
}Node;

Class definition
class Node {
int data;
Node* prev;
Node* next;
};

Insertion in Doubly Linked List

In a doubly linked list, the insertion operation can be performed in three ways. They are as follows:
– Inserting At Beginning of the list
– Inserting At End of the list
– Inserting At Specific location in the list

INSERTING AT BEGINNING OF THE LIST

Following are the steps to insert a new node at the beginning of the doubly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → next = NULL, newNode → prev = NULL, and head = newNode.
– Step 4: If it is Not Empty, then set newNode → next = head, head → prev = newNode, and head = newNode.

INSERTING AT END OF THE LIST

Following are the steps to insert a new node at the end of the doubly linked list:
– Step 1: Create a newNode with given value and set newNode → next = NULL.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → prev = NULL and head = newNode.
– Step 4: If it is Not Empty, then define a node pointer temp and initialize it with head.
– Step 5: Keep moving the temp to its next node until it reaches the last node in the list (until temp → next is
equal to NULL).
– Step 6: Set temp → next = newNode and newNode → prev = temp.

INSERTING AT SPECIFIC LOCATION IN THE LIST (AFTER A NODE)

Following are the steps to insert a new node after a node in the doubly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → next = NULL, newNode → prev = NULL, and head = newNode.
– Step 4: If it is Not Empty, then define a node pointer temp and initialize it with head.
– Step 5: Keep moving the temp to its next node until it reaches the node after which we want to insert the
newNode (until temp → data is equal to location; here, location is the node value after which we want to insert
the newNode).
– Step 6: Every time, check whether temp has reached the last node. If it has reached the last node and the value
does not match, then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the
function. Otherwise, move temp to the next node.
– Step 7: Finally, set newNode → next = temp → next, newNode → prev = temp. If temp → next is not NULL,
set temp → next → prev = newNode. Then set temp → next = newNode.

Deletion in Doubly Linked List

In a doubly linked list, the deletion operation can be performed in three ways. They are as follows:
– Deleting From Beginning of the list
– Deleting From End of the list
– Deleting a Specific Node by Value

DELETING FROM BEGINNING OF THE LIST

Following are the steps to delete a node from the beginning of the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If it is Not Empty, define a node pointer temp and assign it to head.
– Step 4: Move head to the next node (head = head → next).
– Step 5: If head is not NULL, set head → prev = NULL.
– Step 6: Free the memory of temp.

DELETING FROM END OF THE LIST

Following are the steps to delete a node from the end of the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the list has only one node (head → next == NULL), free that node and set head = NULL.
– Step 4: If there are multiple nodes, define a node pointer temp and initialize it with head.
– Step 5: Move temp to the last node (loop until temp → next == NULL).
– Step 6: Set temp → prev → next = NULL.
– Step 7: Free the memory of temp.

DELETING A SPECIFIC NODE BY VALUE

Following are the steps to delete a node with a given value in the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the node to be deleted is the first node (head → data == value):
– Assign a temp pointer to head.
– Move head = head → next.
– If head is not NULL, set head → prev = NULL.
– Free the temp node.
– Step 4: If the node is not the first node, define a pointer temp and initialize it with head.
– Step 5: Loop through the list until temp → data == value or temp == NULL.
– Step 6: If temp == NULL, display "Given node not found in the list!!! Deletion not possible!!!" and terminate.
– Step 7: Else, update temp → prev → next = temp → next.
– Step 8: If temp → next is not NULL, set temp → next → prev = temp → prev.
– Step 9: Free the memory of temp.

Displaying in Doubly Linked List

Following are the steps to display the elements of a doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, then display "List is Empty!!!" and terminate the function.
– Step 3: If it is Not Empty, then define a Node pointer temp and initialize it with head.
– Step 4: Keep displaying temp → data with an arrow (--->) as you move through each node until temp → next
becomes NULL.
– Step 5: Finally, display the last node's data followed by ---> NULL to indicate the end of the list.

Algorithm:

1. Start
2. Define node structure using a class or struct with data, next pointer, prev pointer
3. Define head and tail pointers and assign them to NULL inside the constructor.
4. Define methods for create(), getnode(), insert_node(), delete_node(), display()
5. create()
While (1)
Begin
Ask user: “Do you want to add a new node? (y/n)”
If (answer == 'n') then break
Else
NewNode = getnode();
insert_node(NewNode);
End

Algorithm for Creation of node create()

Begin
NewNode = new Node;
Enter data for new node;
Assign next field to NULL;
Assign prev field to NULL;
Return that node to create function;
End

Algorithm for Insertion of node()

Create one pointer which will start from head

Node *temp = head
Initialize count = 1
Enter the position where you want to insert the node
If(pos == 1) then
Assign the newNode at head position
Set newNode → next = head
If head is not NULL, then set head → prev = newNode
Set head = newNode
Else
While(count != pos - 1)
Begin
temp = temp → next // increment the temp pointer
If(temp == NULL) then
Begin
flag = 0;
break;
End
count++;
End
If(flag == 1) then
Begin
newNode → next = temp → next;
newNode → prev = temp;
If(temp → next != NULL) then
temp → next → prev = newNode;
temp → next = newNode;
End
Else
Print "Position not found";
End

Algorithm for getting data of node getnode()

Begin
Newnode = new Node;
Enter data for new node;
Assign Previous link field to NULL;
Assign Next link field to NULL;
Return that node to create function;
End

Algorithm for display()

Begin
Temp = Head;
If (Temp == NULL) then
Print "List is empty";
Else
Begin
While (Temp != NULL)
Begin
 Display node data;
Increment the pointer i.e. Temp = Temp → next;
End
End
End

Algorithm for Deletion of node delete_node()

Begin
Initialize count = 1, flag = 1;
Declare pointers: Curr, Temp;
Temp = Head;
If (pos == 1) then
Begin
Head = Head → next;
If (Head ≠ NULL) then
Head → prev = NULL;
Delete Temp;
End
Else
Begin
While (count ≠ pos - 1 AND Temp ≠ NULL)
Begin
Temp = Temp → next;
Increment count;
End
If (Temp == NULL OR Temp → next == NULL) then
Print "Position not found";
Else
Begin
Curr = Temp → next;
Temp → next = Curr → next;
If (Curr → next ≠ NULL) then
Curr → next → prev = Temp;
Delete Curr;
End
End
End

Flowchart:

Create your own flowchart from algorithm.

Input: Cinemax theater’s ticket booking system customer‘s information Booking No, Seat No, Name, Row No
and Seat No to book seat.
Output: Results based on customer‘s information using doubly linked list operations like Addition and deletion
of the customers, Computation of list of available seats, Displaying seats and customers, Seats to be booked and
booking to be cancelled of customer.

Conclusion: Cinemax theater’s ticket booking system customer‘s information using doubly linked lists and an
array to store pointers (Head pointer) to each row was understood, implemented and maintained to keep track of
free seats in rows from 10 rows and 7 seats in each row using operations like Addition and deletion of the
customers, Computation of list of available seats, Displaying seats and customers, Seats to be booked and
booking to be cancelled of customer successfully.
 OR
Practical No. 5

Title: Implement doubly linked list & its operations.

Problem Statement:
Write a program to implement doubly linked list
a) Display free slots b) Book appointment c) Sort list based on time d) Cancel appointment (check validity, time
bounds, availability) e) Sort list based on time using pointer manipulation
Aim:
Write C/C++ program to implement doubly linked list:
• Display free slots.
• Book appointment.
• Sort list based on time.
• Cancel appointment (check validity, time bounds, availability)
• Sort list based on time using pointer manipulation
Objectives:
• To study Linked List Data Structure.
• To study & implement doubly linked list.
• To perform Doubly linked list for storing appointment schedule for day.
• To display free slots, book and cancel appointment, Sort list based on time without and with using pointer
manipulation.
Prerequisites:
• Knowledge of C and C++ Programming, Knowledge of booking appointments.
Outcomes:
• Implement Doubly Linked list and perform various operations on it.
• Solve real world problem logically using Doubly Linked List.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Linked List

A linked list is a linear data structure where elements (also called nodes) are stored in separate memory
locations. Unlike arrays, the nodes in a linked list are not stored in contiguous memory locations.
Each node contains two components:-
Data: The actual information stored in the node.
Pointer/Reference: A reference or pointer to the next node in the sequence (in the case of a singly linked list, or
it may reference both the next and previous nodes in the case of a doubly linked list).
Each node consists of its own data and the address of the next node and forms a chain.
 Fig. Linked List

Terminologies of Linked List

Node is an item in a linked list. Each node contains a piece of list data and the location of the next node (item).
Link (of a node) the location of the next node.
Head node is the first node in a linked list.
Head pointer points to the head node.
Null pointer is the pointer which is not need in it. (linked list is empty)

Fig. Linked List

Types of Linked List

There are 3 different implementations of Linked List available, they are:

1. Singly Linked List (SLL)
2. Doubly Linked List (DLL)
3. Circular Linked List (CLL)
1. Circular Singly Linked List (CSLL) or Singly Circular Linked List (SCLL)
2. Circular Doubly Linked List (CDLL) or Doubly Circular Linked List (DCLL)
 Doubly Linked List (DLL)

A doubly linked list is a type of linked list in which each node contains 3 parts, a data part and two addresses,
one points to the previous node and one for the next node. It differs from the singly linked list as it has an extra
pointer called previous that points to the previous node, allowing the traversal in both forward and backward
directions.

A doubly linked list is represented as the pointer to the head (i.e. first node) in the list. Each node in a doubly
linked list contains three components:-
4. Data: data is the actual information stored in the node.
5. Next: next is a pointer that links to the next node in the list.
6. Prev: previous is a pointer that links to the previous node in the list.

Fig. Doubly Linked List

Concepts of Doubly Linked List:

Head: The first node in the linked list. This is the entry point to access the entire list.
Tail: The last node in the linked list. Its next pointer is NULL.
Node: Each element in the list that holds data and a reference to the next node.
Prev/Left/Previous Pointer/Left Pointer: A reference or pointer to the previous node in the list.
Next/Right/Next Pointer/Right Pointer: A reference or pointer to the next node in the list.

Doubly Linked List as an Abstract Data Type (ADT)/Operations on Doubly Linked List

An Abstract Data Type (ADT) defines a data structure in terms of its operations and behavior, without
specifying the internal implementation. For a Doubly Linked List (DLL), the ADT would include the following
operations:
 • Insert: Add a new node at the beginning, end, or after a specified node.
• Delete: Remove a node from the beginning, end, or a specified position.
• Search: Find if a given element exists in the list.
• Traversal: Visit all nodes in the list to process or print them.
• Size: Return the number of nodes in the list.
• Is Empty: Check if the list is empty.
• Print: Prints the list.

1. Insert - This function takes the start node and data to be inserted as arguments. The new node is inserted at
the end, so iterate through the list until the last node is reached. Then, allocate memory for the new node and
store the data in it. Set the next field of the last node to point to the new node, and set the previous field of the
new node to point to the last node. Lastly, set the next field of the new node as NULL.

2. Delete - This function takes the start node (as pointer) and data to be deleted as arguments. Traverse the list to
find the node that contains the given data. If such a node is found, adjust the next pointer of the previous node to
skip the node to be deleted, and adjust the previous pointer of the next node to bypass the node being removed. If
the node to be deleted is at the beginning or end, update the necessary head or tail pointers accordingly. Once the
node is disconnected from the list, its memory is no longer required and can be deallocated.

3. Find - This function takes the start node (as pointer) and the data value (key) to be found as arguments. Start
from the first actual node and traverse the list one node at a time. At each step, check whether the current node’s
data matches the key. If a match is found, the key exists in the list. If the end of the list is reached without
finding the key, then the element is not present

Creation in Doubly Linked List

– Step 1: Define a Node structure with two members data, prev and next
– Step 2: Define a Node pointer 'head' and set it to NULL.

Structure definition
typedef struct node {
int data;
struct node* prev;
struct node* next;
}Node;

Class definition
class Node {
int data;
Node* prev;
Node* next;
};

Insertion in Doubly Linked List

In a doubly linked list, the insertion operation can be performed in three ways. They are as follows:
– Inserting At Beginning of the list
– Inserting At End of the list
– Inserting At Specific location in the list

INSERTING AT BEGINNING OF THE LIST

Following are the steps to insert a new node at the beginning of the doubly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → next = NULL, newNode → prev = NULL, and head = newNode.
– Step 4: If it is Not Empty, then set newNode → next = head, head → prev = newNode, and head = newNode.

INSERTING AT END OF THE LIST

Following are the steps to insert a new node at the end of the doubly linked list:
– Step 1: Create a newNode with given value and set newNode → next = NULL.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → prev = NULL and head = newNode.
– Step 4: If it is Not Empty, then define a node pointer temp and initialize it with head.
– Step 5: Keep moving the temp to its next node until it reaches the last node in the list (until temp → next is
equal to NULL).
– Step 6: Set temp → next = newNode and newNode → prev = temp.

INSERTING AT SPECIFIC LOCATION IN THE LIST (AFTER A NODE)

Following are the steps to insert a new node after a node in the doubly linked list:
– Step 1: Create a newNode with given value.
– Step 2: Check whether the list is Empty (head == NULL).
– Step 3: If it is Empty, then set newNode → next = NULL, newNode → prev = NULL, and head = newNode.
– Step 4: If it is Not Empty, then define a node pointer temp and initialize it with head.
– Step 5: Keep moving the temp to its next node until it reaches the node after which we want to insert the
newNode (until temp → data is equal to location; here, location is the node value after which we want to insert
the newNode).
– Step 6: Every time, check whether temp has reached the last node. If it has reached the last node and the value
does not match, then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the
function. Otherwise, move temp to the next node.
– Step 7: Finally, set newNode → next = temp → next, newNode → prev = temp. If temp → next is not NULL,
set temp → next → prev = newNode. Then set temp → next = newNode.

Deletion in Doubly Linked List

In a doubly linked list, the deletion operation can be performed in three ways. They are as follows:
– Deleting From Beginning of the list
– Deleting From End of the list
– Deleting a Specific Node by Value

DELETING FROM BEGINNING OF THE LIST

Following are the steps to delete a node from the beginning of the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If it is Not Empty, define a node pointer temp and assign it to head.
– Step 4: Move head to the next node (head = head → next).
– Step 5: If head is not NULL, set head → prev = NULL.
– Step 6: Free the memory of temp.

DELETING FROM END OF THE LIST

Following are the steps to delete a node from the end of the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the list has only one node (head → next == NULL), free that node and set head = NULL.
– Step 4: If there are multiple nodes, define a node pointer temp and initialize it with head.
– Step 5: Move temp to the last node (loop until temp → next == NULL).
– Step 6: Set temp → prev → next = NULL.
– Step 7: Free the memory of temp.

DELETING A SPECIFIC NODE BY VALUE

Following are the steps to delete a node with a given value in the doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, display "List is empty!!! Deletion not possible!!!" and terminate.
– Step 3: If the node to be deleted is the first node (head → data == value):
– Assign a temp pointer to head.
– Move head = head → next.
– If head is not NULL, set head → prev = NULL.
– Free the temp node.
– Step 4: If the node is not the first node, define a pointer temp and initialize it with head.
– Step 5: Loop through the list until temp → data == value or temp == NULL.
– Step 6: If temp == NULL, display "Given node not found in the list!!! Deletion not possible!!!" and terminate.
– Step 7: Else, update temp → prev → next = temp → next.
– Step 8: If temp → next is not NULL, set temp → next → prev = temp → prev.
– Step 9: Free the memory of temp.

Displaying in Doubly Linked List

Following are the steps to display the elements of a doubly linked list:
– Step 1: Check whether the list is Empty (head == NULL).
– Step 2: If it is Empty, then display "List is Empty!!!" and terminate the function.
– Step 3: If it is Not Empty, then define a Node pointer temp and initialize it with head.
– Step 4: Keep displaying temp → data with an arrow (--->) as you move through each node until temp → next
becomes NULL.
– Step 5: Finally, display the last node's data followed by ---> NULL to indicate the end of the list.

Algorithm:

6. Start
7. Define node structure using a class or struct with data, next pointer, prev pointer
8. Define head and tail pointers and assign them to NULL inside the constructor.
9. Define methods for create(), getnode(), insert_node(), delete_node(), display()
10. create()
While (1)
Begin
Ask user: “Do you want to add a new node? (y/n)”
If (answer == 'n') then break
Else
NewNode = getnode();
insert_node(NewNode);
End

Algorithm for Creation of node create()

Begin
NewNode = new Node;
Enter data for new node;
Assign next field to NULL;
Assign prev field to NULL;
Return that node to create function;
End

Algorithm for Insertion of node()

Create one pointer which will start from head

Node *temp = head
Initialize count = 1
Enter the position where you want to insert the node
If(pos == 1) then
Assign the newNode at head position
Set newNode → next = head
If head is not NULL, then set head → prev = newNode
Set head = newNode
Else
While(count != pos - 1)
Begin
temp = temp → next // increment the temp pointer
If(temp == NULL) then
Begin
flag = 0;
break;
End
count++;
End
If(flag == 1) then
Begin
newNode → next = temp → next;
newNode → prev = temp;
If(temp → next != NULL) then
temp → next → prev = newNode;
temp → next = newNode;
End
Else
Print "Position not found";
End

Algorithm for getting data of node getnode()

Begin
Newnode = new Node;
Enter data for new node;
Assign Previous link field to NULL;
Assign Next link field to NULL;
Return that node to create function;
End

Algorithm for display()

Begin
Temp = Head;
If (Temp == NULL) then
Print "List is empty";
Else
Begin
While (Temp != NULL)
Begin
 Display node data;
Increment the pointer i.e. Temp = Temp → next;
End
End
End

Algorithm for Deletion of node delete_node()

Begin
Initialize count = 1, flag = 1;
Declare pointers: Curr, Temp;
Temp = Head;
If (pos == 1) then
Begin
Head = Head → next;
If (Head ≠ NULL) then
Head → prev = NULL;
Delete Temp;
End
Else
Begin
While (count ≠ pos - 1 AND Temp ≠ NULL)
Begin
Temp = Temp → next;
Increment count;
End
If (Temp == NULL OR Temp → next == NULL) then
Print "Position not found";
Else
Begin
Curr = Temp → next;
Temp → next = Curr → next;
If (Curr → next ≠ NULL) then
Curr → next → prev = Temp;
Delete Curr;
End
End
End

Flowchart:

Create your own flowchart from algorithm.

Input: Appointment booking system customer‘s information Booking No, Name, Start time, end time, min and
max time and Status as booked or free.
Output: Results based on customer‘s information using doubly linked list operations like Addition and deletion
of the customers, Displaying Appointment schedule, appointment booking status and customers, Appointment to
be cancelled of customer, Sort appointment as per start time without and with using pointer manipulation.

Conclusion: Appointment booking system customer‘s information using doubly linked lists was understood,
implemented and maintained to store appointment schedule for day using operations like Addition and deletion
of the customers, Displaying Appointment schedule, appointment booking status and customers, Appointment to
be cancelled of customer, Sort appointment as per start time without and with using pointer manipulation
successfully.
 Practical No. 6

Title: Implementing Stack to check whether the given expression is well parenthesized or not.
Problem Statement:
In any language program mostly syntax error occurs due to unbalancing delimiter such as (), {}, []. Write a
program using stack to check whether a given expression is well parenthesized or not.
Aim:
Write C/C++ program using stack to check whether a given expression is well parenthesized or not for checking
programming language syntax error occurs due to unbalancing delimiter such as (), {}, [].
Objectives:
• To study & implement Stack Data Structure.
• To check syntax error occurs due to unbalancing delimiter such as (), {}, [].
• To check whether a given expression is well parenthesized or not.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming, Array and Linked List.
Outcomes:
• Implement Stack and perform various operations on it.
• Checking well formedness of parenthesis.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Stack

A stack is a linear data structure where elements are stored in the LIFO (Last In First Out) manner where the last
element inserted would be the first element to be deleted. Insertion and Deletion happens from one end only
called top of the stack. There are many real-life examples of a stack. Consider an example of books stacked over
one another in the library. The book which is at the top is the first one to be removed, i.e. the book which has
been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply
seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

Fig. Stack
 Stack as an ADT/Operations of Stack

Push: push() - Adds an element to the top of the stack.

Pop: pop() - Removes the top element from the stack.
Peek/Top: top() - Returns the top element without removing it.
IsEmpty: isEmpty() - Checks whether the stack is empty.
IsFull: isFull() - Checks whether the stack is full.
Size: size() - Returns the number of elements in the stack.

Applications of Stack

Stacks are commonly used in situations such as: Reversing data (e.g., reversing a string), Implementing recursive
function calls, Parsing expressions (e.g., balancing parentheses) and Backtracking algorithm.

Implementation of Stack

A stack can be implemented by means of Array, Structure, Pointer and Linked-List. Stack can either be a fixed
size one or it may have a sense of dynamic resizing.

Array Implementation of Stack

A one dimensional array can be used to hold elements of stack. Another variable “top” is used to keep track of
the index of the top most elements.

Fig. Array Representation of Stack

The following operations can be done on the stack by using array:

1) Initialization:-

void init(stack *stck)

{
int i;
for(i=0;i<MAX;i++)
stck->data[i]='\0';
stck->top=-1;
}

2) Is empty condition:-

int isempty(stack stck)

{
return stck.top==-1?1:0;
}

3) Is full condition:-

int isfull(stack stck)

{
return stck.top==MAX-1?1:0;
}

4) Push Condition:-

void push(stack *stck, char data)

{
stck->top+=1;
stck->data[stck->top]=data;
}

5) Pop Condition:-

char pop(stack *stck)

{
char data;
data=stck->data[stck->top];
stck->data[stck->top]='\0';
stck->top-=1; return data;
}

Linked List Implementation of Stack

Each stack node points to the next node, with the top element pointing to the first node.

Fig. Linked List Representation of Stack

 Parenthesized

Parenthesized can be defined as in which statement is completed by using opening and closing brackets.
For eg:- 1. (a+b)
2. {a+b}
3. [a+b]
4. {q[h+k(a+v)]}

Concept of Well-Formed Parenthesis

A string containing parenthesis (or any type of bracket) is said to be well-formed if:
• Each opening parenthesis has a matching closing parenthesis.
• The parentheses are correctly nested, meaning the parentheses must close in the reverse order of their
opening.
For example, the string "(())" is well-formed because each opening parenthesis ( has a corresponding closing
parenthesis ), and they are correctly nested.

Conditions for Well-formed Parenthesis:

• Every opening parenthesis (must have a corresponding closing parenthesis).

• The closing parenthesis ) should occur after the matching opening parenthesis (.
• The parentheses must be properly nested, i.e., no closing parenthesis should appear before a matching
opening parenthesis.

Well-formed examples:

() : One pair of parentheses, correctly matched.

(()) : Nested pairs of parentheses.
(()()) : Correctly nested with multiple pairs.
(((()))) : Deeply nested and correctly formed. Not well-formed examples:
( : Missing closing parenthesis.
(() : One closing parenthesis is missing.
()) : Closing parenthesis comes before opening one.
())( : Improper nesting.

Operation

Stack is used to complete the operation using parenthesize. When an opening bracket is given in the statement,
push the bracket in stack and in the case of closing bracket, pop the top most opening bracket and compare with
the closing bracket.

1. If the brackets are equal to each other the case of valid statement gets printed in the test case.
2. If the brackets are unequal to each other the case of invalid statement gets printed in the test case.
3. If the stack is not empty and a series of closing brackets has been exhausted then also the statement is not well
parenthesized.
4. If the stack is empty and series of closing brackets hasn’t been exhausted then also the statement is not well
parenthesized and invalid statement message occurs.

Fig. Well parenthesized in Stack

 Algorithm for Well-formed Parenthesis

1. Traverse the string from left to right.

2. For each character:
If the character is an opening parenthesis (, push it onto the stack.
If the character is a closing parenthesis ), pop an element from the stack.
If the stack is empty, it means there is no matching opening parenthesis, so the string is not well-formed.
3. After traversing the entire string, if the stack is empty, the parentheses are well-formed.
4. Otherwise, there are unmatched opening parentheses, and the string is not well-formed.

Algorithm:

S:stack of characters
X:character type

1) x<-read the next token

2) if(x==‘(’) Push(s,x);
3) if(x==‘)’)
If(top element of the stack is ‘(’)
Pop(s);
Else
Print”mismatch”
4) if(more tokens)
Goto step 1
5) if(stack is not empty)
Print”mismatch”
Else
Print”match”
6) stop

Algorithm for push() operation

begin procedure push: stack, data

if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure

Algorithm for pop() operation

begin procedure pop: stack

if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure

Algorithm of top() function

begin procedure top

return stack[top]
end procedure
Algorithm of isfull() function

begin procedure isfull

if top equals to MAXSIZE
return true
else
return false
endif
end procedure

Algorithm of isempty() function

begin procedure isempty

if top less than 1
return true
else
return false
endif
end procedure

Flowchart:

Fig. Flowchart for Stack Implementation to check well parenthesized expression

Input: Expression using {},(),[].

Output: Results based on Parenthesized Expression whether they are well parenthesized or not.

Conclusion: Concept of stack, it’s operations and implementations, parenthesis, well parenthesized expression
were studied, understood and implemented to check whether a given expression is well parenthesized or not for
checking programming language syntax error occurs due to unbalancing delimiter such as (), {}, [] successfully.
 OR
Practical No. 6
Title: Implementing Stack for expression conversion as infix to postfix and its evaluation.

Problem Statement:
Implement a program for expression conversion as infix to postfix and its evaluation using stack based on given
conditions:
1. Operands and operators both must be single characters.
2. Input Infix and converted Postfix expression must be in a desired format.
3. Only '+', '-', '*' and '/ ' operators are expected.

Aim:
Write C/C++ program for expression conversion as infix to postfix and its evaluation using stack based on given
conditions:
• Operands and operators, both must be single characters.
• Input Infix and converted Postfix expression must be in a desired format.
• Only '+', '-', '*' and '/ ' operators are expected.

Objectives:
• To study & implement Stack Data Structure.
• To study & perform different operations on stack.
• To convert the expression from infix to postfix.
• To evaluate the expression.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming, Array and Linked List,
Expression, Operator Precedence and Evaluation of an Expression.
Outcomes:
• Implement Stack and perform various operations on it.
• Conversion of infix to postfix expression.
• Result of evaluation of an expression.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Stack

A stack is a linear data structure where elements are stored in the LIFO (Last In First Out) manner where the last
element inserted would be the first element to be deleted. Insertion and Deletion happens from one end only
called top of the stack. There are many real-life examples of a stack. Consider an example of books stacked over
one another in the library. The book which is at the top is the first one to be removed, i.e. the book which has
been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply
seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

Fig. Stack
 Stack as an ADT/Operations of Stack

Push: push() - Adds an element to the top of the stack.

Pop: pop() - Removes the top element from the stack.
Peek/Top: top() - Returns the top element without removing it.
IsEmpty: isEmpty() - Checks whether the stack is empty.
IsFull: isFull() - Checks whether the stack is full.
Size: size() - Returns the number of elements in the stack.

Applications of Stack

Stacks are commonly used in situations such as: Reversing data (e.g., reversing a string), Implementing recursive
function calls, Parsing expressions (e.g., balancing parentheses) and Backtracking algorithm.

Implementation of Stack

A stack can be implemented by means of Array, Structure, Pointer and Linked-List. Stack can either be a fixed
size one or it may have a sense of dynamic resizing.

Array Implementation of Stack

A one dimensional array can be used to hold elements of stack. Another variable “top” is used to keep track of
the index of the top most elements.

Fig. Array Representation of Stack

The following operations can be done on the stack by using array:

1) Initialization:-

void init(stack *stck)

{
int i;
for(i=0;i<MAX;i++)
stck->data[i]='\0';
stck->top=-1;
}

2) Is empty condition:-

int isempty(stack stck)

{
return stck.top==-1?1:0;
}

3) Is full condition:-

int isfull(stack stck)

{
return stck.top==MAX-1?1:0;
}

4) Push Condition:-

void push(stack *stck, char data)

{
stck->top+=1;
stck->data[stck->top]=data;
}

5) Pop Condition:-

char pop(stack *stck)

{
char data;
data=stck->data[stck->top];
stck->data[stck->top]='\0';
stck->top-=1;
return data;
}
Linked List Implementation of Stack

Each stack node points to the next node, with the top element pointing to the first node.

Fig. Linked List Representation of Stack

 Expression

An expression is a combination of numbers, variables, and mathematical operations (like addition, subtraction,
multiplication, division) that represents a value or quantity. It's a phrase that doesn't include an equals sign,
unlike an equation. For eg:- a+b, 2-z, x/2, 2*x, 3x+2y-3z/5abc, 8+2-(25678231/3)+{78-[63/(16*2)]}%8, etc.

Operand

The operands indicate what items to apply the action to. An operand can be Constants like numbers and
Variables like alphabets or special characters.

Operator

The operators indicate what action or operation to perform. An operator is a symbol or function that performs
an operation on one or more values, called operands, to produce a result. Common examples include addition
(+), subtraction (-), multiplication (× or *), and division (÷ or /).

Composition of Expression

An expression is a combination of one or more operands, zero or more operators, and zero or more pairs of
parentheses. An expression is formed by operand operator operand or oprand1 operator operand2. Example:
A+B, where A and B are Operands and + are Operator.

Types of Expressions

There are two kinds of expressions based on operations:

• An arithmetic expression evaluates to a single arithmetic value.
• A logical or relational expression evaluates to a single logical value.

Notation is a way of writing arithmetic expression. Polish is a way of expressing arithmetic expression that
avoids the use of brackets to define priorities for evaluation of operators.
There are three kinds of expressions based on notations:
1. Infix Expression
2. Prefix Expression
3. Postfix Expression

Infix Expression

Infix expressions are mathematical expressions where the operator is placed between its operands. For
example: the expression "2 + 3" is an infix expression, where the operator "+" is placed between the operands
"2" and "3".

Prefix Expression (Polish Notation)

Prefix expressions are also known as Polish notation, are a mathematical notation where the operator precedes
its operands. In prefix notation, the operator is written first, followed by its operands. For example, the infix
expression "a + b" would be written as "+ a b" in prefix notation.

Postfix Expression (Reverse Polish Notation)

Postfix expressions are also known as Reverse Polish Notation (RPN), are a mathematical notation where
the operator follows its operands. In postfix notation, operands are written first, followed by the operator. For
example, the infix expression "5 + 2" would be written as "5 2 +" in postfix notation.

Operator Precedence
Operator precedence specifies the order of operations in expressions that contain more than one operator.

Fig. Operator Precedence

Operator Associativity

Operator associativity determines how operators of the same precedence are grouped in the absence of
parentheses. It defines the direction (left-to-right or right-to-left) in which operations are performed when
multiple operators with the same precedence are present in an expression. Associativity is only used when there
are two or more operators of the same precedence.

Left-Associative Operators:
• These operators are evaluated from left to right.
• For example, in the expression a - b + c, the subtraction and addition operators have the same precedence
and are left-associative. Therefore, the expression is evaluated as (a - b) + c.

Right-Associative Operators:
o These operators are evaluated from right to left.
o For example, the assignment operator (=) is right-associative. In the expression a = b = c, the value
of c is first assigned to b, and then the result (the value of b) is assigned to a.
 Fig. Operator Precedence

Operator Precedence and Associativity Table

The following tables list the operator precedence from highest to lowest and the associativity for each of the
operators:
Operator
Precedence Description Associativity

() Parentheses (function call)

[] Array Subscript (Square Brackets)

. Dot Operator
1 Left-to-Right

-> Structure Pointer Operator

++ , -- Postfix increment, decrement

++ / -- Prefix increment, decrement

+/- Unary plus, minus

!,~ Logical NOT, Bitwise complement

2 Right-to-Left
(type) Cast Operator

* Dereference Operator

& Addressof Operator

sizeof Determine size in bytes

3 *,/,% Multiplication, division, modulus Left-to-Right

4 +/- Addition, subtraction Left-to-Right

5 << , >> Bitwise shift left, Bitwise shift right Left-to-Right

< , <= Relational less than, less than or equal to

6 Left-to-Right
> , >= Relational greater than, greater than or equal to

7 == , != Relational is equal to, is not equal to Left-to-Right

 Operator
Precedence Description Associativity

8 & Bitwise AND Left-to-Right

9 ^ Bitwise exclusive OR Left-to-Right

10 | Bitwise inclusive OR Left-to-Right

11 && Logical AND Left-to-Right

12 || Logical OR Left-to-Right

13 ?: Ternary conditional Right-to-Left

= Assignment

+= , -= Addition, subtraction assignment

*= , /= Multiplication, division assignment

14 Right-to-Left
%= , &= Modulus, bitwise AND assignment

^= , |= Bitwise exclusive, inclusive OR assignment

<<=, >>= Bitwise shift left, right assignment

15 , comma (expression separator) Left-to-Right

Infix to Postfix Conversion

In order to evaluate an infix expression using a computer, it is usually converted to postfix. This is because
compiler first scans the expression to evaluate the expression, then again scans the expression again until end of
expression is reached. The repeated scanning makes it very inefficient and evaluating postfix expressions can be
done more easily using a stack. Also, postfix notation removes the need for parentheses to indicate precedence.

Fig. Moving Operators to the Right for Postfix Notation

An Expression with Parentheses

Infix Expression Prefix Expression Postfix Expression

(A + B) * C *+ABC AB+C*

Below are the steps to implement the infix to postfix conversion:

1. Scan the infix expression from left to right.
 2. If the scanned character is an operand, put it in the postfix expression.
3. Otherwise, do the following
• If the precedence of the current scanned operator is higher than the precedence of the operator on
top of the stack, or if the stack is empty, or if the stack contains a ‘(‘, then push the current
operator onto the stack.
• Else, pop all operators from the stack that have precedence higher than or equal to that of the
current operator. After that push the current operator onto the stack.
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘is encountered, and discard both the
parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the operators in the postfix expression until it is not
empty.
8. Finally, print the postfix expression.

Example: Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

For each token, the elements in the stack as well as the corresponding postfix expression up to that point is
shown using the table below:
Element Stack contents Postfix Expression
K K
+ +
L + KL
- - KL+
M - KL+M
* -* KL+M
N -* KL+MN
+ + KL+MN*-
( +( KL+MN*-
O +(^ KL+MN*-O
^ +(^ KL+MN*-O
P +(^ KL+MN*-OP
) + KL+MN*-OP^
* +* K L + M N* - O P ^
W +* K L + M N* - O P ^ W
/ +/ K L + M N* - O P ^ W *
U +/ K L + M N* - O P ^W * U
/ +/ K L + M N* - O P ^W * U /
V +/ K L + M N* - O P ^ W * U / V
* +* K L + M N* - O P ^W * U / V /
T +* K L + M N* - O P ^W * U / V / T
+ + K L + M N* - O P ^W * U / V / T * +
Q + K L + M N* - O P ^W * U / V / T * + Q
K L + M N* - O P ^W * U / V / T * + Q+
The final postfix expression is KL+MN∗−OPW∗U/V/T∗+Q+KL+MN∗−OPW∗U/V/T∗+Q+

Evaluation of Postfix Expression

Follow the steps mentioned below to evaluate postfix expression using stack:
• Create a stack to store operands (values).
• Scan the given expression from left to right and do the following for every element in array.
o If the element is a number, push it into the stack.
o If the element is an operator, pop operands for the operator from the stack. Evaluate the operator
and push the result back to the stack.
 • When the expression is ended, the number in the stack is the final answer.

Example: Postfix expression: 3 4 * 2 5 * +

Input Stack Postfix evaluation

34*25*+ empty Push 3 into stack

4*25*+ 3 Push 4 into stack

*25*+ 43 Pop 4 & pop 3 from stack. do 3*4, Push 12

25*+ 12 Push 2 into stack

5*+ 2 12 Push 5 into stack

*+ 5 2 12 Pop 5, Pop 2 from stack. do 2*5, Push 10 into stack

+ 10 12 Pop 10 & Pop 12 from stack. do 12 + 10, push 22 into stack

22

Algorithm:

S:stack of characters
X:character type

1) x<-read the next token

2) if(x==‘(’) Push(s,x);
3) if(x==‘)’)
If(top element of the stack is ‘(’)
Pop(s);
Else
Print”mismatch”
4) if(more tokens)
Goto step 1
5) if(stack is not empty)
Print”mismatch”
Else
Print”match”
6) stop

Algorithm for push() operation

begin procedure push: stack, data

if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure

Algorithm for pop() operation

begin procedure pop: stack

if stack is empty
 return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure

Algorithm of top() function

begin procedure top

return stack[top]
end procedure

Algorithm of isfull() function

begin procedure isfull

if top equals to MAXSIZE
return true
else
return false
endif
end procedure

Algorithm of isempty() function

begin procedure isempty

if top less than 1
return true
else
return false
endif
end procedure

Algorithm for conversion INFIX TO POSTFIX

Stack S
Char ch
Char element
while(Tokens are Available)
{
ch = Read(Token);
if(ch is Operand)
{
Print ch ;
}
else
{
while(Priority(ch) <= Priority(Top Most Stack))
{
element = Pop(S);
Print(ele);
}
Push(S,ch);
}
}
while(!Empty(S))
{
 element = Pop(S);
Print(ele);
}

Algorithm for evaluation of POSTFIX Expression

Initialize(Stack S)
x = ReadToken(); // Read Token
while(x)
{
if ( x is Operand )
Push ( x ) Onto Stack S.
if ( x is Operator )
{
Operand1 = Pop(Stack S);
Operand2 = Pop(Stack S);
Evaluate (Operand1,Operand2,Operator x);
}
x = ReadNextToken(); // Read Token
}

Flowchart:

(a)Infix to Postfix

Fig. Flowchart for Stack Implementation to convert Infix to Postfix expression

(b)Evaluate Postfix

Fig. Flowchart for Stack Implementation to evaluate Postfix expression

Input: Infix Expression with '+', '-', '*' and '/ ' operators.
Output: Results based on conversion of Infix Expression to Postfix Expression and it’s evaluation.

Conclusion: Concept of stack, it’s operations and implementations, Infix, Prefix, Postfix expression, conversion
of infix to postfix and its evaluation using stack were studied, understood and implemented to check whether a
given expression infix or not, converted expression is postfix or not and their evaluation successfully.
 Practical No. 7

Title: Implement Linear Queue as Real World Job Queue & its operations.
Problem Statement:
Pizza parlor accepting maximum M orders. Orders are served in first come first served basis. Order once placed
cannot be cancelled. Write a program to simulate the system using job queue using array. Write functions to add
jobs and delete jobs from the queue.
Aim:
Write C/C++ program to simulate the Pizza ordering system using job queue using array of Pizza parlor
accepting maximum M orders served in first come first served basis which cannot be cancelled once placed
using job queue using array. Write functions to add jobs and delete jobs from the queue.
Objectives:
• To study Queue Data Structure.
• To study & implement Job Queue.
• To perform Job Queue for Pizza ordering using array.
• To display available orders/jobs, book/add and cancel/delete (modify) jobs/orders.
Prerequisites:
• Knowledge of C and C++ Programming, Knowledge of pizza ordering, Object Oriented Programming,
Array and Linked List.
Outcomes:
• Implement Queue and perform various operations on it.
• Solve real world problem logically using Queue Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Queue

A queue is a linear data structure where elements are stored in the FIFO (First In First Out) manner where the
first element inserted would be the first element to be deleted. Insertion happens from rear end only and Deletion
happens from front end only.
 Fig. Queue Data Structure

Types of Queue

1. Simple/Linear Queue
2. Circular Queue
3. Double Ended Queue (Deque)
1. Input Restricted Queue
2. Output Restricted Queue
4. Priority Queue
1. Min Priority Queue/Min Queue/Ascending Priority Queue
2. Max Priority Queue/Max Queue/Descending Priority Queue

Simple Queue/Linear Queue

A basic queue where elements are added at the rear and removed from the front.

Queue as an ADT/Operations of Queue

Enqueue: enqueue() - Adds (or stores) an element to the end of the queue.
Dequeue: dequeue() - Removes an element from the front of the queue.
Peek/Front: peek() or front() - Returns the front end element without removing it.
Rear: rear() - Returns the element at the rear end without removing it.
IsEmpty: isEmpty() or isNull() - Checks whether the queue is empty or not.
IsFull: isFull() - Checks whether the queue is full or not.
Size: size() - Returns the number of elements in the queue.
 Applications of Queue

Queues are commonly used in situations such as waiting lists for a single shared resource likeprinter, disk, CPU,
asynchronous transfer of data (where data is not being transferred at the same rate between two processes),
Scheduling processes in operating systems, Handling requests in web servers, Print job management in printers.

Implementation of Queue

A queue can be implemented by means of Array, Structure, Pointer and Linked-List. Queue can either be a fixed
size one or it may have a sense of dynamic resizing.

Array Implementation of Queue

A one dimensional array can be used to hold elements of Queue. A variable “front” is used to keep track of the
index of the front element and variable “rear” is used to keep track of the index of the rear element.

Fig. Array Representation of Queue

A queue using array may be defined formally as follows:

# define MAX 30
typedef struct queue
{
int data[MAX];
int front, rear;
}queue;
The following operations can be done on the queue by using array:

1) Initialization:-

void init(struct que *q)

{
int i;
for(i=0;i<MAX;i++)
q->arr[i]=-1;
q->front=0;
q->rear=-1;
}

2) Print Function:-

for(i=0;i<MAX;i++)
cout<<“ ”<q.arr[i];
cout<<“/t/tFront=”<<q.front<<“rear=”<<q.rear<<“/n/n”;
ch=getchar();

3) Is empty condition:-

int isempty(que *que.int data)

{
return q.rear<q.front?1:0;
}

4) Is full condition:-

int isfull(struct que q)

{
return q.rear==MAX-1?1:0;
}

5) Enqueue Condition:-

void enqueue(struct que *q, int data)

{
q->rear+=1;
q->arr [q->rear]=data;
}

6) Dequeue Condition:-

char dequeue(queue *q)

{
char data;
data = q->data[q->front];
q->data[q->front] = '\0'; // Clear the data (optional)
q->front += 1;
return data;
}
 Linked List Implementation of Queue

Each queue node points to the next node, with the front pointer pointing to the first node and rear pointer
pointing to last node.

Fig. Linked List Representation of Queue

A queue using linked list may be defined formally as follows:

typedef struct node

{
int data;
struct node* next;
} node;

typedef struct queue

{
node* front;
node* rear;
} queue;

The following operations can be done on the queue by using array:

1) Initialization:-

void init(struct queue *q)

{
q->front = NULL;
q->rear = NULL;
}

2) Print Function:-

node* temp;
temp = q.front;
while(temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
}
cout << "\t\tFront=" << (q.front ? q.front->data : -1)
<< " Rear=" << (q.rear ? q.rear->data : -1) << "\n\n";
ch = getchar();

3) Is empty condition:-

int isempty(struct queue *q)

{
return q->front == NULL ? 1 : 0;
}

4) Is full condition:-

int isfull(struct queue *q)

{
node *temp = (node*)malloc(sizeof(node));
if (temp == NULL)
return 1;
free(temp);
return 0;
}

5) Enqueue Condition:-

void enqueue(struct queue *q, int data)

{
node *newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = NULL;
if (q->rear == NULL)
{
q->front = q->rear = newNode;
}
else
{
q->rear->next = newNode;
q->rear = newNode;
}
}

6) Dequeue Condition:-

int dequeue(struct queue *q)

{
int data;
node *temp;
if (q->front == NULL)
return -1; // Queue underflow
temp = q->front;
data = temp->data;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
 free(temp);
return data;
}

Job Queue in terms of Pizza Ordering

In the context of pizza ordering, a job queue is a first-in, first-out (FIFO) system that manages customer orders
as "jobs" to be processed by the kitchen or delivery staff.
▪ Each pizza order is a job.
▪ These jobs are added to a queue as customers place orders.
▪ The kitchen processes the jobs in the order they were received — the first order placed is the first to be
prepared and delivered.

Concept Meaning in Pizza Context

Job A customer's pizza order (e.g., Order #123)
Enqueue A customer places a new order
Dequeue An order is prepared and sent out for delivery
Front of queue The next order to be processed
Rear of queue The most recently placed order
FIFO Orders are served in the order they are placed

Algorithm:

Q: queue of pizza orders

X: character or string (command token)

1) X ← read the next token

2) if (X == 'place')
read order ID
if (queue is not full)
Enqueue(Q, order ID)
Print "Order placed"
else
Print "Queue Full"
3) if (X == 'serve')
if (queue is not empty)
Dequeue(Q)
Print "Order served"
else
Print "No Pending Orders"
4) if (X == 'modify')
read old order ID and new order ID
search Q for old order ID
if found
replace with new order ID
Print "Order modified"
else
Print "Order not found"
5) if (X == 'cancel')
Print "Orders cannot be cancelled"
6) if (more tokens)
Goto step 1
7) Print "Simulation Complete"
8) Stop
Algorithm for enqueue(data/value)

enqueue(value) - Inserting value into the queue

Step 1: Check whether queue is FULL. (rear == SIZE-1)

Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function.
Step 3: If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.

begin procedure enqueue(data)

if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure

Algorithm for dequeue

dequeue() - Deleting a value from the Queue

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the
function.
Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as
deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front
and rear to '-1' (front = rear = - 1).

begin procedure dequeue

if queue is empty
return underflow
endif
data = queue[front]
front ← front + 1
return true
end procedure

Algorithm of isfull() function

begin procedure isfull

if rear equals to MAXSIZE
return true
else return false
endif
end procedure

Algorithm of isempty() function

begin procedure isempty

if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
Algorithm for display() function

display() - Displays the elements of a Queue.

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
Step 4: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is equal to
rear (i <= rear)

Flowchart:

Fig. Flowchart for Job Queue Implementation of Pizza Ordering

Input: Size of array, Orders as Elements in queue, order details like Order _ID, Customer_Name.
Output: Results based on addition and deletion(modification) of jobs/orders in job queue.

Conclusion: Concept of Queue, it’s operations and implementations, Real World Job Queue using Linear Queue
were studied, understood and implemented to simulate the system using job queue using array successfully.
 OR
Practical No. 7

Title: Implement Linear Queue as Job Queue & its operations.

Problem Statement:
Queues are frequently used in computer programming, and a typical example is the creation of a job queue by an
operating system. If the operating system does not use priorities, then the jobs are processed in the order they
enter the system. Write a program for simulating job queue. Write functions to add job and delete job from
queue.
Aim:
Write C/C++ program for simulating job queue of an operating system. Write functions to add jobs and delete
jobs from the queue.
Objectives:
• To study Queue Data Structure.
• To study & implement Job Queue.
• To perform Job Queue for processing OS jobs.
• To display available orders/jobs, book/add and cancel/delete jobs.
Prerequisites:
• Knowledge of C and C++ Programming, Knowledge of operating systems jobs, Object Oriented
Programming, Array and Linked List.
Outcomes:
• Implement Queue and perform various operations on it.
• Solve operating system problems logically using Queue Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.

Theory Concept:
Queue

A queue is a linear data structure where elements are stored in the FIFO (First In First Out) manner where the
first element inserted would be the first element to be deleted. Insertion happens from rear end only and Deletion
happens from front end only.
 Fig. Queue Data Structure

Types of Queue

1. Simple/Linear Queue
2. Circular Queue
3. Double Ended Queue (Deque)
1. Input Restricted Queue
2. Output Restricted Queue
4. Priority Queue
1. Min Priority Queue/Min Queue/Ascending Priority Queue
2. Max Priority Queue/Max Queue/Descending Priority Queue

Simple Queue/Linear Queue

A basic queue where elements are added at the rear and removed from the front.

Queue as an ADT/Operations of Queue

Enqueue: enqueue() - Adds (or stores) an element to the end of the queue.
Dequeue: dequeue() - Removes an element from the front of the queue.
Peek/Front: peek() or front() - Returns the front end element without removing it.
Rear: rear() - Returns the element at the rear end without removing it.
IsEmpty: isEmpty() or isNull() - Checks whether the queue is empty or not.
IsFull: isFull() - Checks whether the queue is full or not.
Size: size() - Returns the number of elements in the queue.
 Applications of Queue

Queues are commonly used in situations such as waiting lists for a single shared resource likeprinter, disk, CPU,
asynchronous transfer of data (where data is not being transferred at the same rate between two processes),
Scheduling processes in operating systems, Handling requests in web servers, Print job management in printers.

Implementation of Queue

A queue can be implemented by means of Array, Structure, Pointer and Linked-List. Queue can either be a fixed
size one or it may have a sense of dynamic resizing.

Array Implementation of Queue

A one dimensional array can be used to hold elements of Queue. A variable “front” is used to keep track of the
index of the front element and variable “rear” is used to keep track of the index of the rear element.

Fig. Array Representation of Queue

A queue using array may be defined formally as follows:

# define MAX 30
typedef struct queue
{
int data[MAX];
int front, rear;
}queue;
The following operations can be done on the queue by using array:

1) Initialization:-

void init(struct que *q)

{
int i;
for(i=0;i<MAX;i++)
q->arr[i]=-1;
q->front=0;
q->rear=-1;
}

2) Print Function:-

for(i=0;i<MAX;i++)
cout<<“ ”<q.arr[i];
cout<<“/t/tFront=”<<q.front<<“rear=”<<q.rear<<“/n/n”;
ch=getchar();

3) Is empty condition:-

int isempty(que *que.int data)

{
return q.rear<q.front?1:0;
}

4) Is full condition:-

int isfull(struct que q)

{
return q.rear==MAX-1?1:0;
}

5) Enqueue Condition:-

void enqueue(struct que *q, int data)

{
q->rear+=1;
q->arr [q->rear]=data;
}

6) Dequeue Condition:-

char dequeue(queue *q)

{
char data;
data = q->data[q->front];
q->data[q->front] = '\0'; // Clear the data (optional)
q->front += 1;
return data;
}
 Linked List Implementation of Queue

Each queue node points to the next node, with the front pointer pointing to the first node and rear pointer
pointing to last node.

Fig. Linked List Representation of Queue

A queue using linked list may be defined formally as follows:

typedef struct node

{
int data;
struct node* next;
} node;

typedef struct queue

{
node* front;
node* rear;
} queue;

The following operations can be done on the queue by using array:

1) Initialization:-

void init(struct queue *q)

{
q->front = NULL;
q->rear = NULL;
}

2) Print Function:-

node* temp;
temp = q.front;
while(temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
}
cout << "\t\tFront=" << (q.front ? q.front->data : -1)
<< " Rear=" << (q.rear ? q.rear->data : -1) << "\n\n";
ch = getchar();

3) Is empty condition:-

int isempty(struct queue *q)

{
return q->front == NULL ? 1 : 0;
}

4) Is full condition:-

int isfull(struct queue *q)

{
node *temp = (node*)malloc(sizeof(node));
if (temp == NULL)
return 1;
free(temp);
return 0;
}

5) Enqueue Condition:-

void enqueue(struct queue *q, int data)

{
node *newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = NULL;
if (q->rear == NULL)
{
q->front = q->rear = newNode;
}
else
{
q->rear->next = newNode;
q->rear = newNode;
}
}

6) Dequeue Condition:-

int dequeue(struct queue *q)

{
int data;
node *temp;
if (q->front == NULL)
return -1; // Queue underflow
temp = q->front;
data = temp->data;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
 free(temp);
return data;
}

Job Queue in terms of Operating System

In the context of pizza ordering, a job queue is a first-in, first-out (FIFO) system that is used by the OS to
manage programs waiting to be executed.
Job Scheduling: The computer has a task to execute a particular number of jobs that are scheduled to be
executed one after another. These jobs are assigned to the processor one by one which is organized using a
queue.
▪ When a program (job) is submitted to the system, it is added to the job queue.
▪ Jobs in the queue wait to be admitted into main memory for execution.
▪ The OS scheduler picks jobs from the job queue based on policies like First Come First Serve (FCFS),
Shortest Job First (SJF), Priority Scheduling, etc.
✅ Basic Queue Operations:
Operation Meaning
enqueue() Add a new job to the end of queue
dequeue() Remove the job from front (to serve)
peek() View the next job without removing
isEmpty() Check if queue has jobs
isFull() Check if queue is at capacity

Algorithm:

Q: queue of jobs
X: character or string (command token)

1) X ← read the next token

2) if (X == 'add')
read job ID
if (queue is not full)
Enqueue(Q, job ID)
Print "Job added to queue"
else
Print "Job Queue Full"
3) if (X == 'delete')
if (queue is not empty)
Dequeue(Q)
Print "Job removed from queue"
else
Print "No jobs in queue"
4) if (more tokens)
Goto step 1
5) Print "Job Queue Simulation Complete"
6) Stop

Algorithm for enqueue(data/value)

enqueue(value) - Inserting value into the queue

Step 1: Check whether queue is FULL. (rear == SIZE-1)

Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function.
Step 3: If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.
begin procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure

Algorithm for dequeue

dequeue() - Deleting a value from the Queue

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the
function.
Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as
deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front
and rear to '-1' (front = rear = - 1).

begin procedure dequeue

if queue is empty
return underflow
endif
data = queue[front]
front ← front + 1
return true
end procedure

Algorithm of isfull() function

begin procedure isfull

if rear equals to MAXSIZE
return true
else return false
endif
end procedure

Algorithm of isempty() function

begin procedure isempty

if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure

Algorithm for display() function

display() - Displays the elements of a Queue.

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
Step 4: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is equal to
rear (i <= rear).
Flowchart:

Fig. Flowchart for Job Queue Implementation of Operating System

Input: Size of array, Jobs as Elements in queue, Job details like Job _ID.
Output: Results based on addition and deletion of jobs/tasks in job queue.

Conclusion: Concept of Queue, it’s operations and implementations, Operating System Job Queue using Linear
Queue were studied, understood and implemented to simulate job queue of an operating system successfully.
 Practical No. 8
Title: Implementing Binary Search Tree and it’s operations.
Problem Statement:
Beginning with an empty binary search tree, construct a binary search tree by inserting the values in
the order given. After constructing a binary tree -
i. Insert new node
ii. Find number of nodes in longest path from root
iii. Minimum data value found in the tree
iv. Change a tree so that the roles of the left and right pointers are swapped at every node
v. Search a value.
Aim:
Write C/C++ program to construct a binary search tree from an empty binary search tree by inserting
the values in the order given. After constructing a binary tree -
• Insert new node
• Find number of nodes in longest path from root
• Minimum data value found in the tree
• Change a tree so that the roles of the left and right pointers are swapped at every node.
• Search a value.
Objectives:
• To study and understand the basic concept of Non-Linear Data Structure.
• To study and understand tree, binary tree, binary search tree and it’s basic operation in Data structure.
• To implement Binary Search Tree and perform various operations on it.
• To swap the left and right pointers at every node in binary search tree.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming.
• Knowledge of Arrays, Linked Lists, Stack and Queue.
Outcomes:
• Classify the Tree data structures.
• Implement Binary Search Tree to store a number in it.
• Perform basic Tree Operations like Insertion, Searching and Traversal.
• Solve real world problem logically using Tree Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Tree

A tree is a hierarchical, non-linear data structure composed of nodes connected by edges. It represents data with
a parent-child relationship, where each node can have multiple child nodes, except for the root, which has no
parent.

Fig. Tree Data Structure

 Basic Terminologies of Tree

• Node: A node is an entity that contains a key or value and pointers to its child nodes. The last
nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to
child nodes. The node having at least a child node is called an internal node.
• Edge: It is the link between any two nodes.
• Path: Path refers to the sequence of nodes along the edges of a tree.
• Root: The node at the top of the tree is called root. There is only one root per tree and one path
from the root node to any node.
• Parent: Any node except the root node has one edge upward to a node called parent.
• Child: The node below a given node connected by its edge downward is called its child node.
• Siblings: Nodes with the same parent are called siblings.
• Leaf: The node which does not have any child node is called the leaf node.
• Subtree: Subtree represents the descendants of a node.
• Visiting: Visiting refers to checking the value of a node when control is on the node.
• Traversing: Traversing means passing through nodes in a specific order.
• Levels: Level of a node represents the generation of a node. If the root node is at level 0, then its
next child node is at level 1, its grandchild is at level 2, and so on.
• Keys: Key represents a value of a node based on which a search operation is to be carried out for
a node.
• Height of a Node: The height of a node is the number of edges from the node to the deepest leaf
(i.e. the longest path from the node to a leaf node).
• Depth of a Node: The depth of a node is the number of edges from the root to the node.
• Height of a Tree: The height of a Tree is the height of the root node or the depth of the
deepest node.
• Degree of a Node: The degree of a node is the total number of branches of that node.
• Level of a Node: Level of a node refers to the distance of a node from the root.

Fig. Basic Terminologies of Tree Data Structure

Binary Tree

A binary tree is a tree data structure in which each parent node can have at most two children. A binary
tree is a special kind/type of tree in which each node can have at most two children: they are
distinguished as a left child and a right child. The subtree rooted at the left child of a node is called its
left subtree and the subtree rooted at the right child of a node is called its right subtree.
 Fig. Binary Tree

Binary Search Tree (BST)

A Binary Search Tree (BST) is a Binary Tree where every node's left child has a lower value, and every
node's right child has a higher value. Thus, BST divides all its sub-trees into two segments: the left sub-tree
and the right sub-tree and can be defined as –

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Tree Node Structure
Following Structure is used for Node creation:
struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
};

BST Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following:

• Insert: Inserts an element in a tree/create a tree.

• Search: Searches an element in a tree.
• Traversal: A traversal is a systematic way to visiting all nodes of Tree.

Types of Tree Traversals

Following are the types of Tree Traversals:
1. Breadth First Search (BFS) Traversal
2. Depth First Search (DFS) Traversal
1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal

Breadth First Search (BFS) Traversal

Breadth First Search (BFS) is a traversal algorithm that explores all the nodes of a tree level by level. It starts
at the root node or an arbitrary node and visits all the nodes at the same level before moving on to the next
level. It is also called level wise traversal or level order traversal. Nodes are visited from left to right. A queue
is used in Breadth-First Search (BFS) to manage the order in which nodes are visited, ensuring a level-by-level
traversal of tree.

Fig. BFS Traversal of Binary Search Tree

 Depth First Search (DFS) Traversal

Depth-First Search (DFS) is a traversal algorithm used to explore all the nodes in a tree by going as deep as
possible along each branch before moving to the next one (backtracking). It starts at the root node and visits
every node in the tree. A stack is used in Depth-First Search (DFS) to manage the order in which nodes are
visited, particularly when exploring a tree.

Fig. DFS Traversal of Binary Search Tree

Types of DFS Traversals

Following are the types of DFS Traversals:

1. Pre-order Traversal (Root-Left-Right): It is default traversal method for DFS Traversal. Following are
the steps for Preorder Traversal:
• Visit the root node.
• Recursively traverse the left subtree.
• Recursively traverse the right subtree.

2. In-order Traversal (Left-Root-Right): This traversal method is particularly useful for binary search trees
as it visits nodes in ascending order of their values. Following are the steps for Inorder Traversal:
• Recursively traverse the left subtree.
• Visit the root node.
• Recursively traverse the right subtree.

3. Post-order Traversal (Left-Right-Root): This traversal is often used when deleting nodes in a tree, as it
ensures child nodes are processed before their parent. Following are the steps for Postorder Traversal:
• Recursively traverse the left subtree.
• Recursively traverse the right subtree.
• Visit the root node.
 Implementation of Binary Search Tree

Binary Search Tree can be similarly represented as Tree and Binary Tree. A binary search tree is represented
using two methods. Those methods are as follows:

1. Array Implementation
2. Linked List Implementation

Array Implementation of Binary Search Tree

Tree nodes are stored in a contiguous array, and relationships (parent-child) are determined by index
calculations. If a node is at index i, its left child is at 2i + 1 and its right child is at 2i + 2. One Dimensional array
(1-D Array) to represent a binary search tree. To represent a binary search tree of depth 'n' using array
representation, one dimensional array with a maximum size of 2n + 1 is used. The height of a binary tree denotes
the maximum number of nodes in the longest path of the tree. A binary search tree of height ‘h’ can have at most
2h+1 - 1 nodes. Thus, the size of the array required to represent a complete binary search tree of height h is
2h+1 – 1.
Start giving Nodes numbering from 1 from left to right from root to leaf nodes levelwise. Thus, root has number
1, left child has number 2 and right child has number 3, left subtree left child number 4, right child number 5 and
so on. If there is no node present, make an empty node with no value and give it a number. For above BST, array
representation will be:

0 1 2 3 4 5 6 7
- 40 30 50 25 35 45 60

For above BST, there are some nodes missing, so add empty nodes wherever missing on all levels to make it
have all left child nodes and right child nodes at all nodes.
1

2 3

4 5 12 13 7

8 10 11 14
9 15

For above BST, array representation will be:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 8 3 10 1 6 - 14 - - 4 7 - - 13 -

Linked List Implementation of Binary Search Tree

A double linked list to represent a binary tree. In a double linked list, every node consists of three fields. First
field for storing left child address, second for storing actual data and third for storing right child address.

In this linked list representation, a node has the following structure:

Fig. Node Structure of Linked List Representation

For below BST, Linked List Representation is:

 40

30 50

25 35 45 60

For above BST, there are some nodes missing, so add empty nodes wherever missing to make it have all left
child nodes and right child nodes at all non empty parent nodes.
For above BST, linked list representation will be:

3 10

1 6 NULL 14

NULL NULL 4 7 6 NULL

Algorithm:

Algorithm to insert a node in the binary tree:

1. Create a new BST node and assign values to it.
2. insert(node, key)
i) if root == NULL,
return the new node to the calling function.
ii) if root=>data < key
call the insert function with root=>right and assign the return value in root=>right.
root->right = insert(root=>right,key)
iii) if root=>data > key
3. call the insert function with root->left and assign the return value in root=>left.
4. root=>left = insert(root=>left,key)
5. Finally, return the original root pointer to the calling function.

Algorithm to find the minimum value in binary tree:

1. Define Node class which has three attributes namely: data, left and right. Here, left represents the left
child of the node and right represents the right child of the node.
2. When a node is created, data will pass to the data attribute of node and both left and right will be set to
null.
3. Define another class which has an attribute root.
Flowchart:

Fig. Flowchart for Implementation of Binary Search Tree

Input: An empty Binary Search Tree.

Output: Results based on formation of binary search tree structure with its basic operations like insertion, searching
and Traversal in tree.

Conclusion: Concept of tree, binary tree, binary search tree, it’s basic operations like insertion, searching,
traversal, swapping of left and right pointers and it’s implementations were studied, understood and implemented
to construct binary search tree successfully.
 OR
Practical No. 8

Title: Implementing Binary Search Tree and it’s operations.

Problem Statement:
A Dictionary stores keywords and its meanings. Provide facility for adding new keywords, deleting keywords,
updating values of any entry. Provide a facility to display whole data sorted in ascending/ Descending order.
Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for
implementation.
Aim:
Write C/C++ program to implement a dictionary storing keywords and its meanings using a binary
search tree. Give the following –
• Provide facility for adding new keywords, deleting keywords and updating values of any entry.
• Provide facility for displaying whole data sorted in Ascending/ Descending order.
• Find maximum comparisons may require for finding any keyword.
Objectives:
• To study and understand the basic concept of Non-Linear Data Structure.
• To study and understand tree, binary tree, binary search tree and it’s basic operation in Data structure.
• To implement Binary Search Tree and perform various operations on it.
• To swap the left and right pointers at every node in binary search tree.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming.
• Knowledge of Arrays, Linked Lists, Stack and Queue.
Outcomes:
• Classify the Tree data structures.
• Implement Binary Search Tree to store a number in it.
• Perform basic Tree Operations like Insertion, Searching and Traversal.
• Solve real world problem logically using Tree Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Tree

A tree is a hierarchical, non-linear data structure composed of nodes connected by edges. It represents data with
a parent-child relationship, where each node can have multiple child nodes, except for the root, which has no
parent.

Fig. Tree Data Structure

Basic Terminologies of Tree
 • Node: A node is an entity that contains a key or value and pointers to its child nodes. The last
nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to
child nodes. The node having at least a child node is called an internal node.
• Edge: It is the link between any two nodes.
• Path: Path refers to the sequence of nodes along the edges of a tree.
• Root: The node at the top of the tree is called root. There is only one root per tree and one path
from the root node to any node.
• Parent: Any node except the root node has one edge upward to a node called parent.
• Child: The node below a given node connected by its edge downward is called its child node.
• Siblings: Nodes with the same parent are called siblings.
• Leaf: The node which does not have any child node is called the leaf node.
• Subtree: Subtree represents the descendants of a node.
• Visiting: Visiting refers to checking the value of a node when control is on the node.
• Traversing: Traversing means passing through nodes in a specific order.
• Levels: Level of a node represents the generation of a node. If the root node is at level 0, then its
next child node is at level 1, its grandchild is at level 2, and so on.
• Keys: Key represents a value of a node based on which a search operation is to be carried out for
a node.
• Height of a Node: The height of a node is the number of edges from the node to the deepest leaf
(i.e. the longest path from the node to a leaf node).
• Depth of a Node: The depth of a node is the number of edges from the root to the node.
• Height of a Tree: The height of a Tree is the height of the root node or the depth of the
deepest node.
• Degree of a Node: The degree of a node is the total number of branches of that node.
• Level of a Node: Level of a node refers to the distance of a node from the root.

Fig. Basic Terminologies of Tree Data Structure

Binary Tree

A binary tree is a tree data structure in which each parent node can have at most two children. A binary
tree is a special kind/type of tree in which each node can have at most two children: they are
distinguished as a left child and a right child. The subtree rooted at the left child of a node is called its
left subtree and the subtree rooted at the right child of a node is called its right subtree.
 Fig. Binary Tree

Binary Search Tree (BST)

A Binary Search Tree (BST) is a Binary Tree where every node's left child has a lower value, and every
node's right child has a higher value. Thus, BST divides all its sub-trees into two segments: the left sub-tree
and the right sub-tree and can be defined as –

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

 Tree Node Structure
Following Structure is used for Node creation:
struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
};

BST Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following:

• Insert: Inserts an element in a tree/create a tree.

• Delete: Deletes a node from the tree.
• Search: Searches an element in a tree.

Deleting in Binary Search Tree

Case 1: Deleting a leaf node

Step 1 - Find the node to be deleted using search operation

Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has only one child then create a link between its parent node and child node.
Step 3 - Delete the node using free function and terminate the function.
Case 3: Deleting a node with two children

Step 1 - Find the node to be deleted using search operation

Step 2 - If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right
subtree.
Step 3 - Swap both deleting node and node which is found in the above step.
Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 2.
Step 5 - If it comes to case 1, then delete using case 1 logic.
Step 6 - If it comes to case 2, then delete using case 2 logic.
Step 7 - Repeat the same process until the node is deleted from the tree.
 Implementation of Binary Search Tree

Binary Search Tree can be similarly represented as Tree and Binary Tree. A binary search tree is represented
using two methods. Those methods are as follows:

1. Array Implementation
2. Linked List Implementation

Array Implementation of Binary Search Tree

Tree nodes are stored in a contiguous array, and relationships (parent-child) are determined by index
calculations. If a node is at index i, its left child is at 2i + 1 and its right child is at 2i + 2. One Dimensional array
(1-D Array) to represent a binary search tree. To represent a binary search tree of depth 'n' using array
representation, one dimensional array with a maximum size of 2n + 1 is used. The height of a binary tree denotes
the maximum number of nodes in the longest path of the tree. A binary search tree of height ‘h’ can have at most
2h+1 - 1 nodes. Thus, the size of the array required to represent a complete binary search tree of height h is
2h+1 – 1.

Start giving Nodes numbering from 1 from left to right from root to leaf nodes levelwise. Thus, root has number
1, left child has number 2 and right child has number 3, left subtree left child number 4, right child number 5 and
so on. If there is no node present, make an empty node with no value and give it a number. For above BST, array
representation will be:
 0 1 2 3 4 5 6 7
- 40 30 50 25 35 45 60

For above BST, there are some nodes missing, so add empty nodes wherever missing on all levels to make it
have all left child nodes and right child nodes at all nodes.
1

2 3

4 5 12 13 7

10 11 14
8 9 15

For above BST, array representation will be:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 8 3 10 1 6 - 14 - - 4 7 - - 13 -

Linked List Implementation of Binary Search Tree

A double linked list to represent a binary tree. In a double linked list, every node consists of three fields. First
field for storing left child address, second for storing actual data and third for storing right child address.

In this linked list representation, a node has the following structure:

Fig. Node Structure of Linked List Representation

For below BST, Linked List Representation is:

 40

30 50

25 35 45 60

For above BST, there are some nodes missing, so add empty nodes wherever missing to make it have all left
child nodes and right child nodes at all non empty parent nodes.
For above BST, linked list representation will be:

10
3

NULL
1 6 14

NULL 6 NULL
NULL 4 7
Algorithm:

Algorithm to insert a node in the Binary Search Tree:

1. Create a new BST node and assign values to it.
2. insert(node, key)
i) if root == NULL,
ii) return the new node to the calling function.
iii) if root=>data < key
iv) call the insert function with root=>right and assign the return value in root=>right.
v) root->right = insert(root=>right,key)
vi) if root=>data > key
3. call the insert function with root->left and assign the return value in root=>left.
4. root=>left = insert(root=>left,key)
5. Finally, return the original root pointer to the calling function.

Algorithm to Deleting a node in a Binary Search Tree:

case 1: delete a node with zero child-

if x is left of its parent,
set parent(x).left = null
else set parent(x).right = null
case 2: delete a node with one child link
parent(x) to the child of x.
case 3: delete a node with 2 children
Replace inorder successor to deleted node position.

Flowchart:

Create your own flowchart from algorithm.

Input: A Binary Search Tree, Dictionary Word and its meaning.

Output: Results based on binary search tree structure with its basic operations like Add, delete operations,
displaying data in sorted order and maximum number of comparisons required to find any keyword.

Conclusion: Concept of tree, binary tree, binary search tree, it’s basic operations like insertion, deletion,
searching, traversal and it’s implementations were studied, understood and implemented on Dictionary using
binary search tree successfully.
 Practical No. 9
Title: Implementing Graph and it’s representations.
Problem Statement:
There are flight paths between cities. If there is a flight between city A and city B then there is an edge between
the cities. The cost of the edge can be the time that flight takes to reach city B from A or the amount of fuel
used for the journey. Represent this as a graph. The node can be represented by the airport name or name of the
city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Check
whether the graph is connected or not.
Aim:
Write C/C++ program to represent flight paths between cities with cost of the edges as a graph. After
representing the graph -
• Use adjacency list representation of the graph.
• Use adjacency matrix representation of the graph.
• Check whether the graph is connected or not.
Objectives:
• To study and understand the basic concept of Non-Linear Data Structure.
• To study and understand graph, types of graph and it’s representations.
• To implement flight paths between cities with cost of the edges as a graph.
• To implement adjacency list and matrix representations and show whether they are connected or not.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming.
• Knowledge of Arrays and Linked Lists.
Outcomes:
• Understand the Graph data structure.
• Implement flight paths between cities with cost of the edges as a graph.
• Represent Graph’s adjacency list and adjacency matrix.
• Check Graph is a Connected Graph or not.
• Solve real world problem logically using Graph Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Graph

A graph is a non-linear data structure consisting of nodes or vertices which are connected to other nodes through
edges or links. Nodes are circles represented by numbers or alphabets. They store the data. Two nodes are
connected by a line called Edge. Edge can be directed or undirected. Basically, pairs of vertices are called edges.
A graph is formally defined as G = (V, E), where V is the set of vertices and E is the set of edges.

Fig. Graph Data Structure

In the above example, the edge can go from 1 to 4 or from 4 to 1, i.e. a bidirectional edge can be in both
directions, hence called an undirected edge. Thus, the pairs (1,4) and (4,1) represent the same edge.

Types of Graphs
1. Undirected Graph
2. Directed Graph

Undirected Graph
An undirected graph is a graph where edges are bidirectional, with no direction associated with them, i.e, there
will be an undirected edge. In an undirected graph, the pair of vertices representing any edge is unordered. Thus,
the pairs (u, v) and (v, u) represent the same edge.

Directed Graph
A directed graph is a graph where all the edges are directed from one vertex to another, i.e, there will be a
directed edge. It contains an ordered pair of vertices. It implies each edge is represented by a directed pair <u,
v>. Therefore, <u, v> and <v, u> represent two different edges.

Cycle
A cycle is a path in a graph that starts and ends at the same vertex, with no other vertex or edge repeated, except
for the first and last vertices. A graph containing at least one cycle is called a cyclic graph. If a graph contains no
cycles, it is called an acyclic graph.

Fig. Cycle

Fig. Cyclic Graph

 Fig. Acyclic Graph

Loop
Loop in a graph is path starting from same vertex and ends to same vertex but uses at least one other vertex.
Example: Vertices w and z form a loop.

Loop

Fig. Loop in a Graph

Weight
A weight is a numerical value assigned to an edge, representing some attribute like distance, cost, or time
between connected nodes. An edge with a weight is called Weighted Edge.
Weight

Fig. Weighted Edge

Weighted Graph
A graph with weighted edges or a graph with some weighted assigned to it’s edges is called Weighted Graph.

Fig. Weighted Graph

Connected Graph

A connected graph is a graph where a path exists between any two vertices. The graph in which from one node
any other node can be visited in the graph is known as a connected graph. There are no isolated nodes in
connected graph.
 Fig. Connected Graph

Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

Representations of the Graph

Following two are the most commonly used representations of graph.

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph.

Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency
matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If
adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
The adjacency matrix for the above example graph is:

Fig. Adjacency Matrix representation of Undirected Graph

For an undirected graph, where there is an edge, 1 is placed at the node’s places in the matrix.
For a directed graph, the direction of edge going from one edge to the other edge, 1 is placed at that node’s
place.

1 and 0 can also be represented as True and False respectively.

Fig. Adjacency Matrix representation of Directed Graph

 Fig. Adjacency Matrix representation of Weighted Undirected Graph/Undirected Weighted Graph

For an undirected weighted graph, where there is a weighted edge, place the weights at the node’s places in the
matrix.
For a directed weighted graph, where there is a weighted directed edge from one edge to the other edge, place
the weights at the node’s places in the matrix.

Fig. Adjacency Matrix representation of Weighted Directed Graph/Directed Weighted Graph

Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether
there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).
Cons: Consumes more space O(V2). Even if the graph is sparse(contains less number of edges), it consumes the
same space. Adding a vertex is O(V2) time.

Adjacency List/Edge List

An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[ ].
An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can
also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.
Following is adjacency list representation of the above graph:

Fig. Adjacency List representation of Undirected Graph

For an undirected graph, select a graph node as a head node and create a linked list to the next node to the head
node. Check if there is any connected edge to any other node from head node. If there is no other node connected
to the head node, terminate/end the linked list. If there exists such nodes, add to the linked list. Repeat until there
are no more other nodes connected to the head node which are not added in the linked list. Then terminate/end
the linked list.

For a directed graph, select a graph node as a head node and create a linked list to the next node to the head
node based on the direction of the directed edge. Check if there is any directed edge to any other node from head
node. If there is no other directed edge to the head node, terminate/end the linked list. If there exists such nodes,
add to the linked list. Repeat until there are no more other nodes connected to the head node which are not added
in the linked list. Then terminate/end the linked list.
 Fig. Adjacency List representation of Undirected Graph

Fig. Adjacency List representation of Weighted Undirected Graph/Undirected Weighted Graph

For an undirected weighted graph, select a graph node as a head node and create a linked list to the next node
to the head node. Add the weight of the edge in next slot of the node from the head node in the linked list. Check
if there is any connected edge to any other node from head node. If there is no other node connected to the head
node, terminate/end the linked list. If there exists such nodes, add to the linked list with their weights in the next
slots. Repeat until there are no more other nodes connected to the head node which are not added in the linked
list. Then terminate/end the linked list.

For a directed weighted graph, select a graph node as a head node and create a linked list to the next node to
the head node based on the direction of the directed edge. Add the weight of the edge in next slot of the node
from the head node in the linked list. Check if there is any directed edge to any other node from head node. If
there is no other directed edge to the head node, terminate/end the linked list. If there exists such nodes, add to
the linked list with their weights in the next slots. Repeat until there are no more other nodes connected to the
head node which are not added in the linked list. Then terminate/end the linked list.
 Fig. Adjacency List representation of Weighted Directed Graph/Directed Weighted Graph

Pros: Space-efficient for sparse graphs as it consumes only O(V + E) space. Adding a vertex takes O(1) time
(amortized, if using dynamic arrays or hash maps). Iterating over all edges of a vertex is efficient—only takes
time proportional to the vertex’s degree. More memory-efficient for large, sparse graphs compared to adjacency
matrix.
Cons: Checking if there is an edge from vertex ‘u’ to vertex ‘v’ is O(degree of u) in worst case. Removing an
edge can take O(degree of u) time due to the need to search the list. Slightly more complex to implement
compared to adjacency matrix.

Algorithm:

Algorithm for Graph creation using Adjacency Matrix:

1. Declare an array of M[size][size] which will store the graph.

2. Enter how many nodes you want in a graph.
3. Enter the edges of the graph by two vertices each, say Vi , Vj indicates some
edge
i. If the graph is directed set M[i][j]=1.
ii. If graph is undirected set M[i][j] =1 and M[j][i] =1.
4. When all the edges of the desired graph is entered print the graph M[i][j].

Algorithm for Graph creation using Adjacency List:

1. Declare node structure for creating adjacency list.

2. Initialize an array of nodes. This array will act as head nodes. The index of head[ ] will be the starting
vertex.
3. The create function will create the adjacency list.
Flowchart:

Fig. Flowchart for representation of Graph

Input: A Weighted Graph as a representation of flight paths between cities.

Output: Results based on the implemented flight paths between cities as a weighted graph’s adjacency list or
adjacency matrix and checked whether the graph is connected or not.

Conclusion: Concept of graph, types of graph and it’s representations were studied, understood and
implemented on flight paths between cities successfully.
 OR
Practical No. 9

Title: Implementing Graph and it’s Spanning Tree.

Problem Statement:
You have a business with several offices; you want to lease phone lines to connect them up with each other; and
the phone company charges different amounts of money to connect different pairs of cities. You want a set of
lines that connects all your offices with a minimum total cost. Solve the problem by suggesting appropriate data
structures.
Aim:
Write C/C++ program to represent phone lines to connect them up with each other that connects all offices with
a minimum total cost as a graph. Solve the problem by suggesting appropriate data structures.
Objectives:
• To study and understand the basic concept of Non-Linear Data Structure.
• To study and understand graph, types of graph and it’s representations.
• To implement phone lines between cities connecting all offices with costs of the edges as a graph.
• To implement Minimum Spanning Tree to find the minimum distance between the vertices of Graph in
Data Structure.
Prerequisites:
• Knowledge of C and C++ Programming, Object Oriented Programming.
• Knowledge of Arrays and Linked Lists.
Outcomes:
• Understand the Graph data structure.
• Implement phone lines between cities connecting all offices with costs of the edges as a graph.
• Implement Minimum Spanning Tree
• Check Graph is a Connected Graph or not.
• Solve real world problem logically using Graph Data Structure.
Software & Hardware requirements:
• Open Source C/C++ Programming tools like G++/GCC or Eclipse.
• 64-bit Open source Linux or its derivative.
Theory Concept:
Graph

A graph is a non-linear data structure consisting of nodes or vertices which are connected to other nodes through
edges or links. Nodes are circles represented by numbers or alphabets. They store the data. Two nodes are
connected by a line called Edge. Edge can be directed or undirected. Basically, pairs of vertices are called edges.
A graph is formally defined as G = (V, E), where V is the set of vertices and E is the set of edges.

Fig. Graph Data Structure

In the above example, the edge can go from 1 to 4 or from 4 to 1, i.e. a bidirectional edge can be in both
directions, hence called an undirected edge. Thus, the pairs (1,4) and (4,1) represent the same edge.
Types of Graphs
1. Undirected Graph
2. Directed Graph

Undirected Graph
An undirected graph is a graph where edges are bidirectional, with no direction associated with them, i.e, there
will be an undirected edge. In an undirected graph, the pair of vertices representing any edge is unordered. Thus,
the pairs (u, v) and (v, u) represent the same edge.

Directed Graph
A directed graph is a graph where all the edges are directed from one vertex to another, i.e, there will be a
directed edge. It contains an ordered pair of vertices. It implies each edge is represented by a directed pair <u,
v>. Therefore, <u, v> and <v, u> represent two different edges.

Cycle
A cycle is a path in a graph that starts and ends at the same vertex, with no other vertex or edge repeated, except
for the first and last vertices. A graph containing at least one cycle is called a cyclic graph. If a graph contains no
cycles, it is called an acyclic graph.

Fig. Cycle

Fig. Cyclic Graph

 Fig. Acyclic Graph

Loop
Loop in a graph is path starting from same vertex and ends to same vertex but uses at least one other vertex.
Example: Vertices w and z form a loop.

Loop

Fig. Loop in a Graph

Weight
A weight is a numerical value assigned to an edge, representing some attribute like distance, cost, or time
between connected nodes. An edge with a weight is called Weighted Edge.
Weight

Fig. Weighted Edge

Weighted Graph
A graph with weighted edges or a graph with some weighted assigned to it’s edges is called Weighted Graph.

Fig. Weighted Graph

Connected Graph

A connected graph is a graph where a path exists between any two vertices. The graph in which from one node
any other node can be visited in the graph is known as a connected graph. There are no isolated nodes in
connected graph.
 Fig. Connected Graph

Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

Sub Graph

A subgraph is a portion of a larger graph that includes a subset of the original graph's vertices and
edges. Essentially, it's a smaller graph derived from a bigger one, sharing some or all of its vertices and edges.
A graph G1 = (V1, E1) is called a subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a
subset of E(G) such that each edge of G1 has same end vertices as in G.

Spanning

Spanning refers to how data, memory, or operations cover or extend across parts of the structure—whether it’s
memory regions, index ranges, or connected nodes.
 Spanning Tree

A spanning tree is a subset of edges in a connected graph that spans all the vertices without forming any
cycles. A sub-graph T of a undirected graph G=(V,E) is a spanning tree of G if it is a tree and contains every vertex
of G.

Fig. Spanning Tree

Greedy Algorithm

The method of greedy algorithm starts with a top and goes down, creating greedy choices in a series and then
reduce each of the given problem to even smaller ones. At each step, the best possible choice is taken and
after that only the sub-problem is solved.

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a kind of a sub graph of an undirected graph in which, the sub graph
spans or includes all the nodes has a minimum total edge weight. Minimum Spanning Tree in an undirected
connected weighted graph is a spanning tree of minimum weight (among all spanning trees).
 Fig. Minimum Spanning Tree

Prim’s Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected
graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight
of all the edges in the tree is minimized.
▪ Start form any arbitrary vertex.
▪ Find the edge that has minimum weight form all known vertices.
▪ Stop when the tree covers all vertices.

Fig. Prim’s Algorithm

Example:

✓ The set mstSet is initially empty and keys assigned to vertices are {0, INF, INF, INF, INF, INF,
INF, INF} where INF indicates infinite.
✓ Pick the vertex with the minimum key value.
✓ The vertex 0 is picked, include it in mstSet. So mstSet becomes {0}.
✓ After including to mstSet, update key values of adjacent vertices.
✓ Adjacent vertices of 0 are 1 and 7.
✓ The key values of 1 and 7 are updated as 4 and 8.
✓ Following subgraph shows vertices and their key values, only the vertices with finite key values are
shown.
The vertices included in MST are shown in green color.

✓ Pick the vertex with minimum key value and not already included in MST (not in mstSET).

✓ The vertex 1 is picked and added to mstSet. So mstSet now becomes {0, 1}.

✓ Update the key values 3, 4 values of adjacent vertices.

✓ The key value of vertex 2 becomes 8.

✓ Pick the vertex with minimum key value and not already included in MST (not in mstSET).
✓ Either pick vertex 7 or vertex 2, let vertex 7 is picked. So mstSet now becomes {0, 1, 7}.
✓ Update the key values of adjacent vertices of 7. The key value of vertex 6 and 8 becomes finite (1 and 7
respectively).
 ✓ Pick the vertex with minimum key value and not already included in MST (not in mstSET). Vertex 6 is
picked. So mstSet now becomes {0, 1, 7, 6}.
✓ Update the key values of adjacent vertices of 6. The key value of vertex 5 and 8 are updated.

✓ Repeat the above steps until mstSet includes all vertices of given graph. Finally,
✓ Get the following graph.

Algorithm:

Algorithm for Minimum Spanning Tree using Prim’s Algorithm:

1. Begin with any vertex which you think would be suitable and add it to the tree.
2. Find an edge that connects any vertex in the tree to any vertex that is not in the
tree. Note that, don't have to form cycles.
3. Stop when n - 1 edges have been added to the tree.

Prim’s Algorithm:
MST= {0} // start with vertex 0
For (T=0; T contains fewer than n-1 edges; add(u,v) to T)
{
Let (u,v) be a least cost edge such that u є TV & v not belonging to TV;
Add V to TV
}
Flowchart:

Fig. Flowchart for Graph

Input: A Weighted Graph as a representation of phone lines between cities connecting all offices.
Output: Results based on the implemented phone lines between cities connecting all offices as a weighted
graph’s minimum spanning tree.

Conclusion: Concept of graph, types of graph and it’s Minimum Spanning Tree were studied, understood and
implemented on phone lines between cities connecting all offices successfully.