COURSE FILE

ARZU Page 1
 DATA
STRUCTURES
[Link], II-SEM
COMMON TO ALL
BRANCHES
MR23 REGULATION

ARZU Page 2
 SYLLABUS COPY
ARZU Page 3
 UNIT -I

Introduction to Linear Data Structures: Definition and importance of linear data structures,
Abstract data types (ADTs) and their implementation, Overview of time and space complexity
analysis for linear data structures. Searching Techniques: Linear & Binary Search, Sorting
Techniques: Bubble sort, Selection sort, Insertion Sort

UNIT -II

Linked Lists: Singly linked lists: representation and operations, doubly linked lists and circular linked
lists, Comparing arrays and linked lists, Applications of linked list.

UNIT-III
Stacks: Introduction to stacks: properties and operations, implementing stacks using arrays and linked
lists, Applications of stacks in expression evaluation, backtracking, reversing list etc.

UNIT-IV
Queues: Introduction to queues: properties and operations, implementing queues using arrays and
linked lists, Applications of queues in breadth-first search, scheduling, etc.
Deques: Introduction to deques (double-ended queues), Operations a deques and their applications.

UNIT-V
Trees: Introduction to Trees, Binary Search Tree–Insertion, Deletion &Traversal
Hashing: Brief introduction to hashing and hash functions, Collision resolution techniques: chaining
and open addressing, Hash tables: basic implementation and operations, Applications of hashing in
unique identifier generation, caching, etc.

Textbooks:
1. Data Structures and algorithm analysis in C, Mark Allen Weiss, Pearson, 2nd Edition.

ARZU Page 4
 2. Fundamentals of data structures in C, Ellis Horowitz, Sartaj Sahni, Susan Anderson- Freed, Silicon
Press, 2008

Reference Books:
1. Algorithms and Data Structures: The Basic Tool box by Kurt Mehlhorn and Peter Sanders
2. C Data Structures and Algorithms by Alfred V. Aho, Jeffrey D. Ullman, and John E. Hop croft
3. Problem Solving with Algorithms and DataStructures"byBradMillerandDavid Ranum
4. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford Stein
5. Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph
Algorithms" by Robert Sedgewick

LESSON PLAN

ARZU Page 5
 FACULTY NAME: REGULATION:MR23
CLASS&SEMESTER:[Link]&II SEM ACADEMIC YEAR:
COURSENAME:
BRANCH:

LESSONPLAN

UNITI: Introduction to Linear Data Structures

[Link] Lecture/Tutorial Topic Covered Teaching Aid Date

1 L-01 Definition and importance of GB, PC

linear data structures
2 L-02 Abstract data types(ADTs) and GB, PC
their implementation
3 L-03 Overview o f time and space GB, PC
complexity analysis
4 L-04 Linear Search- Introduction GB, PC

5 L-05 Linear Search-Algorithm& GB, PC

Implementation
6 L-06 Linear Search- Complexity GB, PC
Analysis
7 L-07 Binary Search-Introduction GB, PC

8 L-08 Binary Search-Algorithm& GB, PC

Implementation
9 L-09 Binary Search-Complexity GB, PC
Analysis
10 L-10 Bubble Sort -Introduction GB, PC

11 L-11 Bubble Sort-Algorithm& GB, PC

Implementation
12 L-12 Bubble Sort-Complexity Analysis GB, PC

13 L-13 Selection Sort- Introduction GB, PC

14 L-14 Selection Sort-Algorithm& GB, PC

Implementation
15 L-15 Selection Sort- Complexity GB, PC
Analysis

ARZU Page 6
 16 L-16 Insertion Sort-Introduction GB, PC

ARZU Page 7
 17 L-17 Insertion Sort-Algorithm& GB, PC
Implementation
18 L-18 Insertion Sort-Complexity GB, PC
Analysis
UNIT II: Linked Lists
19 L-19 Singly linked lists: Representation GB, PC

20 L-20 Singly linked lists: Insertion GB, PC

21 L-21 Singly linked lists: Deletion GB, PC

22 L-22 Doublylinkedlists:Representation GB, PC

23 L-23 Doublylinkedlists:Operations GB, PC

24 L-24 Circularlinked lists: GB, PC

Representation
25 L-25 Circularlinkedlists:Operations GB, PC

26 L-26 Comparingarraysandlinkedlists GB, PC

27 L-27 Applicationsoflinkedlists GB, PC

UNIT III:Stacks
28 L-28 Introductiontostacks:Properties GB, PC

29 L-29 Stacks:Basicoperations GB, PC

30 L-30 Implementingstacksusingarrays GB, PC

31 L-31 Implementingstacksusinglinked GB, PC

lists
32 L-32 Applications:Expression GB, PC
evaluation
33 L-33 Applications:Backtracking GB, PC

34 L-34 Applications:Reversingalist GB, PC

UNIT IV: Queues and Deques

35 L-35 Introductiontoqueues:Properties GB, PC

36 L-36 Queues:Basicoperations GB, PC

37 L-37 Implementingqueuesusingarrays GB, PC

38 L-38 Implementingqueuesusinglinked GB, PC

lists

ARZU Page 8
 39 L-39 Applications:Breadth-firstsearch GB, PC

40 L-40 Applications:Scheduling GB, PC

41 L-41 Introductiontodeques GB, PC

42 L-42 Deques:Basicoperations GB, PC

43 L-43 Deques:Applications GB, PC

UNITV:Treesand Hashing
44 L-44 Introductionto Trees GB, PC

45 L-45 BinarySearchTree–Insertion GB, PC

46 L-46 BinarySearchTree–Deletion GB, PC

47 L-47 BinarySearchTree–Traversal GB, PC

48 L-48 Briefintroductiontohashingand GB, PC

hashfunctions
49 L-49 Collisionresolutiontechniques: GB, PC
Chaining
50 L-50 Collisionresolutiontechniques: GB, PC
Openaddressing
51 L-51 Hashtables:Basicoperations GB, PC

52 L-52 Hashtables:Applications GB, PC

Textbooks:
1. DataStructuresandalgorithmanalysisinC,MarkAllenWeiss,Pearson,2nd Edition.
2. Fundamentals of data structures in C, Ellis Horowitz, Sartaj Sahni, Susan Anderson- Freed, Silicon
Press, 2008

ReferenceBooks:
1. AlgorithmsandData Structures:TheBasicToolboxbyKurtMehlhorn andPeter Sanders
2. [Link],[Link], [Link]
3. ProblemSolvingwithAlgorithmsandDataStructures"byBradMillerandDavid Ranum
4. [Link],[Link],[Link],and Clifford
Stein
5. Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph

ARZU Page 9
 Algorithms" by Robert Sedgewick

UNIT-I
INTRODUCTION TO LINEAR DATA STRUCTURES

Data Structure:
A data structure is a specialized format for organizing, storing, and managing data in a computer so that it
can be accessed and modified efficiently. It defines the way data is arranged and the operations that can be
performed on it.
Importance:
Data structures are essential because they:
• Help in organizing data efficiently.
• Allow quick access and modification of data.
• Improve the performance of algorithms.
• Play a crucial role in solving complex computational problems.
Classification of Data Structures
Data structures are broadly classified into two types:
1. Linear Data Structures – Elements are arranged sequentially (e.g., Arrays, Linked Lists, Stacks, Queues).
2. Non-Linear Data Structures – Elements are arranged in a hierarchical manner (e.g., Trees, Graphs).

ARZU Page 10
Linear Data Structures
A data structure is considered linear if its elements form a sequence. The elements of a linear data structure
can be stored in:
• Contiguous memory locations (using arrays)
• Non-contiguous memory locations (using linked lists, where each element contains a pointer to the next
element)
Importance of Linear Data Structures
1. Simplicity and Easy Access – Easier to understand and manipulate.
2. Efficient Traversal – Simple to iterate through elements.
3. Data Integrity – Maintains ordered relationships among elements.
4. Memory Efficiency – Optimized memory usage in certain implementations.
5. Real-World Applications – Used in software applications, databases, and operating systems.
6. Ease of Algorithm Implementation – Fundamental to algorithm design.
7. Flexibility – Can be implemented dynamically (e.g., linked lists).
Abstract Data Type (ADT)
An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and behaviors for a
data structure without specifying its implementation details. ADTs focus on what a data structure does,
rather than how it does it.
For example, a Stack ADT defines operations like push(), pop(), and peek() but does not specify whether
the stack is implemented using an array or a linked list.
Key Concepts of ADT
1. Abstraction

ARZU Page 11
 o ADTs hide implementation details and only expose necessary operations.

o Users can use ADTs without knowing how they are implemented.
2. Encapsulation

o ADTs bundle data and operations into a single unit.

o Internal details are hidden, and only the defined operations can be used.
3. Modularity

o ADTs help in designing reusable and maintainable code.

4. Data Structure Independence

o The same ADT can be implemented using different data structures, such as arrays or linked lists.
Examples of ADTs
1. List ADT

o A collection of elements in a sequence.

Operations: insert(), remove(), get(), size(), isEmpty(), etc.

2. Stack ADT (LIFO - Last In, First Out)

o Allows insertion and deletion only from the top.

Operations: push(), pop(), peek(), isEmpty(), etc.

3. Queue ADT (FIFO - First In, First Out)

o Elements are added at the rear and removed from the front.

Operations: enqueue(), dequeue(), peek(), isEmpty(), etc.

Advantages of ADTs
Encapsulation – Keeps data secure by hiding implementation details.
Abstraction – Users work with data without worrying about implementation.
Reusability – The same ADT can be used in multiple programs.
Modularity – Code becomes well-structured and easy to debug.
Disadvantages of ADTs
Overhead – Additional memory and processing may be required.
Complexity – Implementing ADTs can be tricky for large systems.
Limited Flexibility – Some ADTs may not fit all scenarios.

ARZU Page 12
Time and Space Complexity Analysis for Linear Data Structures
Linear data structures, such as arrays, linked lists, stacks, and queues, require analyzing their time
complexity (how execution time increases with input size) and space complexity (how memory usage
grows with input size).
Time Complexity Table for Linear Data Structures

Space Complexity Table for Linear Data Structures

ARZU Page 13
Searching Techniques: Linear and Binary Search
Linear Search
Linear search is a method of finding a particular value in a list by checking each element one by one
sequentially until the desired element is found or the list is exhausted.
Algorithm:
1. Start
2. Take the input list/array and the search element.
3. Iterate through each element in the list:
o Compare the current element with the search element.
o If they match, return the index (position) of the element.
o If not, continue to the next element.
4. If the element is not found after checking all elements, return "Element not found."
5. End

Example
Consider the following list of elements and the search element:
Search Element: 12

Steps of Linear Search

Step 1: Compare search element 12 with the first element (index 0).

ARZU Page 14
12 == 65 → Not Matched → Move to next element.

Step 2: Compare search element 12 with the second element (index 1).
12 == 20 → Not Matched → Move to next element.

Step 3: Compare search element 12 with the third element (index 2).
12 == 10 → Not Matched → Move to next element.

Step 4: Compare search element 12 with the fourth element (index 3).
12 == 55 → Not Matched → Move to next element.

Step 5: Compare search element 12 with the fifth element (index 4).
12 == 32 → Not Matched → Move to next element.

Step 6: Compare search element 12 with the sixth element (index 5).
12 == 12 → Matched! → Stop searching and display the result.

ARZU Page 15
Element 12 found at index 5.

Code:

Binary Search
Binary search is an efficient searching technique used to check whether an element is present in a sorted
list. It repeatedly divides the search interval in half to locate the element.
Algorithm:

ARZU Page 16
 1. Start
2. Take the input sorted list/array and the search element.
3. Set low = 0 and high = size of array - 1.
4. Repeat until low ≤ high:
o Find the mid index: mid=(low+high)/2
o Compare arr[mid] with the search element:
▪ If arr[mid] == search element, return mid (element found).
▪ If arr[mid] < search element, search the right half (low = mid + 1).
▪ If arr[mid] > search element, search the left half (high = mid - 1).
5. If the element is not found, return "Element not found."
6. End
Example
Consider the sorted list:

Search Element: 35
Steps of Binary Search
Step 1: Find the Midpoint
• Low index = 0
• High index = 8
• Mid index = (0 + 8) / 2 = 4
• Mid Value = 10

Comparison: 35 > 10 → Search in the right sublist {16, 21, 35, 36}.
Step 2: Find the New Midpoint
• Low index = 5
• High index = 8
• Mid index = (5 + 8) / 2 = 6

ARZU Page 17
• Mid Value = 21

Comparison: 35 > 21 → Search in the right sublist {35, 36}.

Step 3: Find the New Midpoint
• Low index = 7
• High index = 8
• Mid index = (7 + 8) / 2 = 7
• Mid Value = 35

Comparison: 35 == 35 → Match found at inded 7!

Code:
#include<stdio.h>
void binarySearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
printf("Element found at index %d\n", mid);
return;
} else if (arr[mid] < key) {
low = mid + 1;
} else {

ARZU Page 18
high = mid - 1;
}
}
printf("Element not found\n");
}
void main() {
int size, key;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter %d sorted elements: ", size);
for (int i = 0; i < size; i++) {
scanf(“%d”, &key);
}
Printf(“enter the element to search:”);
Scanf(“%d”, &key);
Binarysearch(arr,size,key);
}

Sorting Techniques
Sorting is the process of arranging elements in a specific order (ascending or descending). Below are three
fundamental sorting techniques:
Bubble Sort
• Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if
they are in the wrong order.
• It "bubbles" the largest element to the end in each pass.
• The process repeats until the array is completely sorted.
Algorithm:
1. Start from the first element.
2. Compare it with the next element.
3. Swap if the first element is greater than the second.

ARZU Page 19
4. Repeat this process for the entire array.
5. Reduce the range of comparison in each pass.
6. Stop when no swaps occur in a pass.
Time Complexity:
• Best Case: O(n)(already sorted)
• Worst/Average Case: O(n2)
Example: Sorting [8, 12, 2, 4, 11]
Initial Array:

Pass 1:
Compare 8 & 12 → No swap

Compare 12 & 2 → Swap

Compare 12 & 4 → Swap

Compare 12 & 11 → Swap

ARZU Page 20
Final Sorted Array:
Sorted Elements: [2, 4, 8, 11, 12]
Code:
#include “stdio.h”
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];

ARZU Page 21
arr[j + 1] = temp;
}
}
}
}
void main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("Sorted array using Bubble Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}

Selection Sort
Selection Sort is a simple sorting algorithm that repeatedly selects the smallest element from the unsorted
part and moves it to the correct position.
• Finds the minimum element and places it at the beginning.
• Repeats the process for the remaining unsorted part.

Algorithm:
1. Find the smallest element in the unsorted part.
2. Swap it with the first element of the unsorted part.
3. Repeat for the remaining elements until the array is sorted.
Time Complexity:

ARZU Page 22
• Best Case: O(n2)
• Worst Case: O(n2)
• Average Case: O(n2)

Example: Sorting [8, 12, 2, 4, 11]

Initial Array:
8 12 2 4 11

ARZU Page 23
Code:

#include “stdio.h”
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
int temp = arr[i]; arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
void main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
selectionSort(arr, n);
printf("Sorted array using Selection Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}

Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It works
similarly to how we sort playing cards in our hands:

ARZU Page 24
• Takes one element at a time and inserts it into its correct position.
• Moves larger elements one position to the right to make space for the new element.

Algorithm:
1. Start from the second element (index 1).
2. Compare it with previous elements.
3. Shift larger elements to the right.
4. Insert the current element at the correct position.
5. Repeat for all elements.
Time Complexity:
• Best Case: O(n) (if already sorted)
• Worst/Average Case: O(n2)
Example: Sorting [8, 12, 2, 4, 11]

ARZU Page 25
Code:

#include <stdio.h>

ARZU Page 26
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i – 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--;
}
arr[j + 1] = key;
}
}
void main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n); int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
insertionSort(arr, n);
printf("Sorted array using Insertion Sort: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}

ARZU Page 27
 UNIT-2
LINKED LIST: A linked list is a linear data structure that includes a series of connected nodes each node
stores the data and address of the next node, and it is also a dynamic structure.

Types of linked lists:

Single linked list
Double linked list
Circular linked list
Single linked list:
 It can be defined as the collection of ordered set of elements
 A linked list in which each node contains only one link field pointing to the next node in the list
 The first node in the list is pointing to the next node in the list
 The first node in the list is pointed to by a head pointer
 The last node in the list has a link field containing a NULL flag indicating “end of the list”
 A linked list in an ordered collection of elements called nodes each of which has two parts
Data part: it stores actual information that is to be represented by the node Link part: it stored the address
of its immediate successor.
Structure of single linked list:

ARZU Page 28
SYNTAX:
Struct node {
int data;
Struct node *next;
}
Operations on linked list:
 Create DATA POINTING TO THE NEXT NODE ADDRESS data next
 Insertion ➢ Insert at begin ➢ Insert at location ➢ Insert at end
 Deletion ➢ Delete at begin ➢ Delete at location ➢ Delete at end
 Search
 Traversal
 Updating
 Sorting
 Merging
 Display
Create: creation of single linked list is insertion of nodes into an empty list.
 If the contents of FIRST is equal to NULL, it implies that FIRST does not store the address of any node.
 This means that there are no nodes in the list.
 i.e., the list does not exists and hence has to be created.
 Creation of the list involves creation of the first node in the list. This can be done by
✓ Creating the new node
✓ Storing the address of the new node created in FIRST.

Operations on Singly Linked List: The main operations performed on a singly linked list are:
Insertion
(a) At the beginning
(b) At the end
(c) At a specific position
INSERTION: using this operation we can insert a value at different positions of the list

ARZU Page 29
(a) At the beginning :

• A new node is created.

• The next pointer of the new node is assigned to the current head.

• The head is updated to point to the new node.

Algorithm:
1. Create a new node.
2. Assign data to the new node.
3. Set the new node’s next to the current head.
4. Update the head to the new node.
Code:
void insertAtBeginning(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}

(b)At the end: if we insert new value at end of the list, the pointer of new node is NULL
• A new node is created.
• If the list is empty, the new node becomes the head.

ARZU Page 30
• Otherwise, traverse to the last node and update its next pointer to the new node.
Algorithm:
1. Create a new node.
2. Assign data to the new node.
3. If the list is empty, set head = new node.
4. Otherwise, traverse to the last node.
5. Set the last node’s next to the new node.
Code:
void insertAtEnd(struct Node** head, int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
newNode->data = value;
newNode->next = NULL

if (*head == NULL)
{
*head = newNode;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}

ARZU Page 31
(C) At a specific position:
• A new node is created.
• The list is traversed to the given position.
• The next pointer of the new node is updated to point to the next node of the current position.
• The next pointer of the previous node is updated to point to the new node.
Algorithm
1. Create a new node.
2. Assign data to the new node.
3. Traverse the list to the given position.
4. Set the new node’s next to the next node of the current position.
5. Set the previous node’s next to the new node.

Code:
void insertAtPosition(struct Node** head, int value, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (position == 1)
{
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++)

ARZU Page 32
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Invalid position\n");
return;
} newNode->next = temp->next;
temp->next = newNode;
}

DELETING A NODE:
• From the beginning
• From the end
• From a specific position
Deletion from the Beginning:
• The head node is deleted.
• The second node becomes the new head.
• If the list is empty after deletion, set head = NULL.

ARZU Page 33
Algorithm:
1. Check if the list is empty.
2. Store the head node in a temporary pointer.
3. Move the head pointer to the next node.
4. Free the memory of the removed node.

Code:
void deleteAtBeginning(struct Node** head)
{
if (*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
Example:

Deletion from the end

• The last node is deleted.
• The second-last node’s next is set to NULL.
• If there is only one node, the head becomes NULL.

ARZU Page 34
Algorithm
1. Check if the list is empty.
2. If there is only one node, delete it and set head = NULL.
3. Traverse to the second-last node.
4. Set the second-last node’s next to NULL.
5. Free the last node’s memory.

Code:
void deleteAtEnd(struct Node** head)
{
if (*head == NULL) return;
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp->next == NULL)
{
free(temp);
*head = NULL;
return;
}
while (temp->next != NULL)
{
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}

ARZU Page 35
Deletion from a Specific Position
• The node at a given position is deleted.
• The next pointer of the previous node is updated to skip the deleted node.
• If the position is 1, it behaves like deleting from the beginning.
Algorithm
1. Check if the list is empty.
2. If deleting the first node, update head = head->next and free the old head.
3. Traverse to the previous node of the target position.
4. Adjust pointers to bypass the deleted node.
5. Free the memory of the removed node.
Code:
void deleteAtPosition(struct Node** head, int position)
{
if (*head == NULL)
return;
struct Node* temp = *head;
if (position == 1)
{
*head = temp->next;
free(temp);
return;

ARZU Page 36
}
struct Node* prev = NULL;
for (int i = 1; i < position && temp != NULL; i++)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}

(b) Searching in a Singly Linked List

Searching is the process of finding a specific value in a Singly Linked List (SLL). Since there is no direct
indexing like arrays, we must traverse the list sequentially. Approach:

• Linear Search is used to traverse the list.

• The search starts from the head node and moves forward.

• If the target value is found, return its position (1-based index).

• If the value is not found, return -1.

Algorithm:

ARZU Page 37
 1. Initialize a pointer to the head node.

2. Initialize an index counter (pos = 1).

Travers the list:

o If the node’s data matches the key, return pos.

o Otherwise, move to the next node and increment pos. 4.

If the list ends without finding the key, return -1.

Code:

int search(struct Node* head, int key)

int pos = 1;

struct Node* temp = head;

while (temp != NULL)

if (temp->data == key)

return pos;

temp = temp->next;

pos++;

return -1; // Not found

}
(c) Traversal (Displaying the List) Traversal is the process of visiting each node and performing an
operation (e.g., printing values). It starts from the head node and follows the next pointers until
reaching NULL.

ARZU Page 38
Algorithm:
1. Start from the head node.
2. While the node is not NULL: o Print the node’s data. o Move to the next node.
3. Stop when NULL is reached.

Code:
void traverse(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
DOUBLY LINKED LIST:
Each node in a doubly linked list has two link fields. These are used to point to the successor node and
predecessor node.

Struct node
{
Int num;
Struct node *prev;
Struct node *next;
};
typedef struct node NODE;
Operations on double Linked List:
Insertion
• At the beginning

ARZU Page 39
• At the end
• At a specific position
Inserting at beginning:

DELETION

ARZU Page 40
• At the beginning
• At the end
• At a specific position
DELETING A NODE AT BEGINNING:

ARZU Page 41
CIRCULAR LINKED LIST:
In a list, once we traverse from one node to another it becomes difficult to get back as it links the entire
nodes in one direction.
To overcome this drawback, we can move on to circular linked list where the last node holds the address of

ARZU Page 42
the first node.
Operations on circular linked list:
 Create
 Insertion
➢ Insert at begin
➢ Insert at location
➢ Insert at end
 Deletion
➢ Delete at begin
➢ Delete at location
➢ Delete at end
 Search
 Traversal
 Updating
 Sorting
 Merging
 Display
Circular linked list using single linked list:
Creating a circular linked list using single linked list
Consider the items 10,20,30,40 to generate circular linked list using single linked list

Inserting a node into the list

Inserting at start:

ARZU Page 43
ARZU Page 44
ARZU Page 45
ARZU Page 46
Circular linked list using double linked list:

ARZU Page 47
Algorithm:

1. Allocate the memory to the node

2. Set its LEFT and RIGHT links to head

3. Set its data field to zero

4. Return the node

Code:

NODE*create_list()
{
NODE *head;
Head=allocate_node();
head->LEFT=head->RIGHT=head;
head->num=0;
return head;
}
CREATING A DOUBLE LINKED LIST USING CIRCULAR LINKED LIST

ARZU Page 48
ARZU Page 49
ARZU Page 50
ARZU Page 51
ARZU Page 52
ARZU Page 53
 UNIT-3
Stack is a linear data structure to which insertions and deletions are done from one end called top. It
follows Last In First Out(LIFO) technique. The technique operation for inserting an element into the stack
is referred as PUSH, and for deleting an element is referred as POP.
Inserting an element into the stack when it is full leads to stack overflow. Deleting an element from stack
when it is empty leads to stack underflow.
A stack may be referred as linear data structure or static data structure or homogeneous data structure.
Stack is used in many computer applications. It is used in system software like operating systems,
compilers. More over a stack may be implemented either using arrays or using linked list.
PROPERTIES OF STACK...
There are following important properties of stack-
(i)All insertions and deletions can occur only at the top of stack.
(ii) The elements that are removed from stack in reverse order in which they were inserted.
(iii) Only one element can be pushed or popped from the stack at a time.
(iv) It works in last-in-first-out or LIFO manner
Standard Stack Operations:
The following are some common operations implemented on the stack:
push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then
the overflow condition occurs.
pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty
means that no element exists in the stack, this state is known as an underflow state.
Peek (or Top):
The peek operation, also known as top, allows you to view the element at the top of the stack without
removing it. This is useful for inspecting the current top element.
Peeking doesn't alter the stack's structure; it only provides information about the top element.

ARZU Page 54
isEmpty():
It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.'
peek(): It returns the element at the given position.
count(): It returns the total number of elements available in a stack.
change(): It changes the element at the given position.
display(): It prints all the elements available in the stack.
Algorithms for Stack ADT (Abstract Data Type)
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Below are the
algorithms for fundamental stack operations.
1. Initialize Stack

This algorithm initializes an empty stack.

Algorithm:
Algorithm initializeStack
1. Define an array `stack[MAX]`
2. Set `top = -1` (indicating an empty stack)
2. Push Operation (Insertion)
This algorithm inserts an element into the stack.
Algorithm:
Algorithm push(stack, top, MAX, element)
1. If `top == MAX - 1`, then

Print "Stack Overflow"

Return
2. Else

Increment `top = top + 1`

`stack[top] = element`

Print "Element pushed successfully"

[Link] Operation (Deletion)
This algorithm removes and returns the top element from the stack.

ARZU Page 55
Algorithm:
Algorithm pop(stack, top)
1. If `top == -1`, then

Print "Stack Underflow"

Return NULL
2. Else

`element = stack[top]

` Decrement `top = top - 1`

Return `element`
[Link] Operation (View Top Element)

This algorithm returns the top element without removing it.

Algorithm:

Algorithm peek(stack, top)

1. If `top == -1`, then

Print "Stack is empty"

Return NULL
2. Else

Return `stack[top]`

5. isEmpty Operation

This algorithm checks whether the stack is empty.

Algorithm:

Algorithm isEmpty(top)
1. If `top == -1`, then

Return True

ARZU Page 56
 2. Else

Return False
5. isFull Operation

This algorithm checks whether the stack is full.

Algorithm:

Algorithm isFull(top, MAX)

1. If `top == MAX - 1`, then

Return True
2. Else

Return False

ARZU Page 57
ARZU Page 58
ARZU Page 59
Representation of STACK using LINKED LIST
To implement a stack using a singly linked list, we follow the LIFO (Last In, First Out) principle. In this
approach, data is stored in the form of nodes, and we manipulate the stack using a top pointer.
• The top pointer is used to insert (push) and delete (pop) elements in the stack.
• Each new element is added as the top node.
• When removing an element, we simply remove the node pointed to by top and update top to its next
node.
• The next field of the last node in the stack is always NULL.
Example:
Consider a stack with three elements: 10, 20, 30
• Top value = 30 (it was inserted last).
• Indexing starts from 0, so top = 2.
• The linked list representation is as follows:

ARZU Page 60
ARZU Page 61
Expression Evaluation and Its Types
Expression evaluation is the process of computing the result of a mathematical or logical expression by
following specific rules of operator precedence, associativity, and operand order. Expressions can contain
operands (values, variables) and *operators
(+, -, , /, etc.) and are commonly used in programming, mathematics, and compilers.
There are three primary types of expressions based on the position of operators:

ARZU Page 62
 1. Infix Expression

2. Prefix Expression (Polish Notation)

3. Postfix Expression (Reverse Polish Notation - RPN)

Types of Expressions with Detailed Explanation

1. Infix Expression

Definition:

• In Infix Notation, the operator is placed between the operands.

• It is the most natural and commonly used notation in arithmetic and programming languages.

• However, infix expressions require operator precedence rules and parentheses to define the order of
operations clearly.

Example Infix Expression:

(5 + (3 * 4)) – 9

Operator Precedence (BODMAS Rule in Math):

• Parentheses () – Highest priority

• Multiplication *, Division / – Higher priority

• Addition +, Subtraction - – Lower priority

ARZU Page 63
Advantages of Infix Notation:
Easy to read and understand.
Used in most programming languages (C, Java, Python, etc.).

Disadvantages of Infix Notation:

Difficult for machines to evaluate directly (requires parsing and precedence rules).
Needs parentheses to remove ambiguity.
2. Prefix Expression (Polish Notation)

Definition:

• In Prefix Notation, the operator appears before its operands.

• It is also known as Polish Notation (named after Polish mathematician Jan Łukasiewicz).

• No parentheses are required, as the order of evaluation is always clear. Example Prefix Expression:

-+5*349

ARZU Page 64
 .Equivalent Infix Expression: (5 + (3 * 4)) - 9

Advantages of Prefix Notation:

No need for parentheses.
Simple to parse and evaluate.
Used in some programming languages (Lisp, functional programming).
Disadvantages of Prefix Notation:
Not intuitive for humans.
Requires a stack for evaluation in compilers.

3. Postfix Expression (Reverse Polish Notation - RPN)

Definition:

• In Postfix Notation, the operator appears after its operands.

• It is also known as Reverse Polish Notation (RPN).

• No parentheses or precedence rules are needed, making it easy to evaluate using stacks.
Example Postfix Expression:
534*+9–
Equivalent Infix Expression: (5 + (3 * 4)) – 9

ARZU Page 65
Advantages of Postfix Notation:
No parentheses or precedence rules needed.
Easier to evaluate using a stack.
Used in calculators and compilers (e.g., Java Virtual Machine).
Disadvantages of Postfix Notation:
Not human-friendly.
Requires a stack-based approach for evaluation.

ARZU Page 66
Infix to Postfix Conversion
1. Introduction

Infix notation is the standard way of writing mathematical expressions where operators are placed

ARZU Page 67
 between operands, e.g.,

A+B

However, computers find it difficult to evaluate infix expressions directly because they require operator
precedence and associativity rules to determine the order of operations.

Postfix notation (Reverse Polish Notation, RPN) is an alternative in which operators follow operands,
making it easier for computers to evaluate expressions without parentheses or precedence rules.

A B + (equivalent to A + B in infix)

2. Need for Conversion

• Infix expressions require complex parsing due to operator precedence and associativity.

• Postfix expressions are easier to evaluate because they follow a strict order and don't need parentheses.

Example:

• Infix: (5 + 3) * 4

• Postfix: 5 3 + 4 *
3. Operator Precedence & Associativity

Before converting an infix expression to postfix, we need to consider operator precedence and
associativity.

• Associativity decides whether an operator is evaluated from left-to-right or right-to-left.

• Higher precedence operators are evaluated before lower precedence operators.

ARZU Page 68
4. Conversion Rules

To convert an infix expression to postfix using a stack, follow these rules:

1. Operands (A-Z, 0-9): Directly add them to the output.

2. *Operators (+, -, , /, ^):

o If the stack is empty, push the operator.

o If the stack is not empty:

▪ Pop operators from the stack to the output until the stack is empty or an operator with lower precedence
is found.

▪ Push the new operator onto the stack.

3. Left Parenthesis (: Always push onto the stack.

4. Right Parenthesis ):

o Pop and add operators to the output until a left parenthesis ( is encountered.

o Discard the left parenthesis.

5. Example Conversion

Convert Infix Expression

(5 + (3 * 4)) - 9

Step-by-Step Process

ARZU Page 69
6. Advantages of Postfix Notation

No need for parentheses – The order of operations is determined by the notation itself.

Easier for machines to evaluate – It avoids precedence and associativity complications.

Efficient for stack-based evaluation – Postfix expressions can be evaluated using a simple stack.
Backtracking Using Stacks
Backtracking is a problem-solving approach that systematically explores all possible solutions to a
problem and backtracks when an invalid solution is encountered. It is often used for solving problems that
involve multiple solutions or constraints. When implemented using stacks, we replace recursion with an
explicit stack structure, which allows iterative backtracking.
Use of Backtracking
The backtracking algorithm is useful when:
A problem has multiple possible solutions, and we need to find one or all valid solutions.
The problem can be broken down into smaller subproblems with similar properties. There are constraints
that must be satisfied to obtain a valid solution.

ARZU Page 70
Backtracking Algorithm
Backtracking explores all possible paths toward a solution and establishes checkpoints from where it can
backtrack if necessary. The algorithm follows these steps:
1. Start from an initial state and push it onto a stack.
2. Repeat until the stack is empty:
o Pop the top state from the stack.
o If it is a valid solution, return success.
o If it is an invalid state (dead-end), discard it and backtrack.
o Otherwise, generate possible moves from this state and push them onto the stack
[Link] all possibilities are explored and no solution is found, return failure.

ARZU Page 71
 • Grey → Final solution.
Backtracking Algorithm (Using Stack Representation)
1. Start
2. If the current position is the goal, return success.
3. Else, check if the current position is a dead-end:
o If yes, discard and backtrack.
o If no, explore possible moves and repeat the process.
[Link] when all possibilities are exhausted.
Types of Backtracking Problems
Backtracking is mainly applied in three types of problems:
1. Decision Problems – Finding at least one valid solution (e.g., Rat in a Maze).
2. Optimization Problems – Finding the best possible solution (e.g., Minimum Cost Path).

ARZU Page 72
3. Enumeration Problems – Finding all possible valid solutions (e.g., Subset Sum).
Examples of Backtracking Problems
Here are some well-known problems where backtracking is applied:
N-Queens Problem – Placing N queens on an N×N chessboard without conflicts.
Rat in a Maze – Finding a path through a maze with obstacles.
Sudoku Solver – Filling a Sudoku grid with valid numbers.
Knight’s Tour Problem – Moving a knight on a chessboard to visit all squares exactly once.
Hamiltonian Cycle – Finding a cycle in a graph that visits every vertex exactly once.
Subset Sum Problem – Finding subsets that sum to a given value.
Word Break Problem – Breaking a word into valid dictionary words.
M-Coloring Problem – Coloring a graph with M colors without adjacent conflicts.
Cryptarithmetic Puzzle – Solving puzzles involving letter-based arithmetic.
Advantages of Using Stacks for Backtracking
Avoids recursion depth limits – Eliminates recursion overhead.
Improved debugging and control – We explicitly track backtracking steps.
Efficient memory usage in some cases – Useful for large search spaces.
Disadvantages
Requires manual stack management – Push/pop operations must be handled explicitly.
Can be complex to implement – Compared to recursive solutions.
Reversing a Linked List Using a Stack
A singly linked list consists of nodes where each node contains data and a pointer to the next node. The
goal is to reverse the order of nodes using a stack.
Understanding the Concept:
A stack follows the LIFO (Last In, First Out) principle. This means:
• The last element inserted into the stack is the first one to be removed.
• If we push elements of a linked list into a stack, they will be stored in reverse order.
• When we pop elements from the stack, we retrieve them in reverse order, which allows us to reconstruct
the reversed linked list.
Algorithm
1. Check for Edge Cases:

o If the linked list is empty or has only one node, return without reversing.

ARZU Page 73
2. Initialize an Empty Stack:
o Create a stack to store pointers to the nodes of the linked list.
3. Push All Nodes into the Stack:
o Traverse the linked list from the head to the end.
o Push each node into the stack.
o Once traversal is complete, the stack stores nodes in reverse order.
4. Reconstruct the Linked List:
o Pop the top element of the stack and make it the new head of the linked list.
o Keep popping elements from the stack and linking them in sequence.
5. Update the Last Node:
o Set the next pointer of the last node to NULL to mark the end of the reversed list.
7. Return the New Head of the Reversed Linked List.

Example:

Original Linked List:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Step 1: Push nodes into a stack

Stack (top to bottom): [5, 4, 3, 2, 1]

Step 2: Pop nodes from the stack and modify the linked list
• Pop 5, set it as the new head.
• Pop 4, set it as 5 -> 4.
• Pop 3, set it as 5 -> 4 -> 3.
• Pop 2, set it as 5 -> 4 -> 3 -> 2.
• Pop 1, set it as 5 -> 4 -> 3 -> 2 -> 1.
• Set 1’s next pointer to NULL.
Reversed Linked List:
5 -> 4 -> 3 -> 2 -> 1 -> NULL
Time & Space Complexity:
• Time Complexity: O(N) (traversal + reconstruction)
• Space Complexity: O(N) (due to stack storage)

ARZU Page 74
 UNIT-4
Queue
A queue is a linear data structure where insertions and deletions take place from two distinct ends known as the rear
and the front, respectively. Elements are inserted from the rear and removed from the front, following the First In,
First Out (FIFO) principle, meaning that the first element added is the first one to be removed. The operation of
inserting an element into the queue is termed 'Enqueue', while the removal of an element is called 'Dequeue'.
Real-World Examples of Queues:
• A single-lane one-way road, where vehicles enter first and exit in the same order.

ARZU Page 75
 4. Priority Queue
A priority queue is a specialized type of queue where elements are assigned a priority. Elements with
higher priority are dequeued before those with lower priority. If multiple elements have the same priority,
they follow the FIFO principle.

ARZU Page 76
 5. Deque (Double-Ended Queue)

A deque (double-ended queue) is a flexible queue structure where elements can be inserted and removed
from both the front and rear. This allows greater versatility in data management compared to standard
queues.

Properties of Queues
1. FIFO Principle – The element added first is removed first.
2. Two Pointers – Uses two pointers: front (for deletion) and rear (for insertion).
3. Dynamic Size – The queue can expand or contract as elements are added orremoved.
4. Efficient Operations – Insertions and deletions occur in constant time O(1).
5. Ordered Storage – Maintains the sequence of elements.
Queue Operations
1. Enqueue (Insertion) – Adds an element to the rear of the queue
2. Dequeue (Deletion) – Removes an element from the front of the queue.
3. Front (Peek) – Returns the element at the front without removing it.
4. Rear (Peek Last) – Returns the element at the rear without removing it.
5. isEmpty() – Checks if the queue is empty.
6. isFull() – Checks if the queue is full (relevant in static implementations).
Algorithms:
1. Initialize Queue

ARZU Page 77
 This algorithm initializes an empty queue.

Algorithm:
Algorithm initializeQueue
1. Define an array `queue[MAX]`
2. Set `front = -1` and `rear = -1`
• Initially, both front and rear are set to -1, indicating an empty queue.
2. Enqueue Operation (Insertion)

This algorithm inserts an element at the rear of the queue.

Algorithm:
Algorithm enqueue(queue, front, rear, MAX, element)
1. If `rear == MAX - 1`, then

Print "Queue Overflow"

Return
2. If `front == -1` (Queue is initially empty), then

Set `front = 0`
3. Increment `rear = rear + 1`
4. `queue[rear] = element`
5. Print "Element inserted successfully"
3. Dequeue Operation (Deletion)
This algorithm removes and returns the front element.
Algorithm:
Algorithm dequeue(queue, front, rear)
1. If `front == -1` OR `front > rear`, then

Print "Queue Underflow"

Return NULL
2. `element = queue[front]`
3. If `front == rear` (Only one element left), then
Set `front = -1` and `rear = -1`
4. Else

ARZU Page 78
Increment `front = front + 1`
5. Return `element`
4. Peek Operation (View Front Element)
This algorithm returns the front element without removing it.
Algorithm:
Algorithm peek(queue, front, rear)
1. If `front == -1` OR `front > rear`, then

Print "Queue is empty"

Return NULL
2. Else

Return `queue[front]`
5. isEmpty Operation
This algorithm checks whether the queue is empty.
Algorithm:
Algorithm isEmpty(front, rear)
1. If `front == -1` OR `front > rear`, then

Return True
2. Else
Return False
6. isFull Operation
This algorithm checks whether the queue is full.
Algorithm:
Algorithm isFull(rear, MAX)
1. If `rear == MAX - 1`, then
Return True
2. Else
Return False

Queue & its Operations

A queue is a linear data structure where insertions and deletions are performed from two different ends
called front and rear.

ARZU Page 79
• Insertions are done from the rear end.
• Deletions are done from the front end.
• It follows the First In First Out (FIFO) principle, meaning the first inserted element is the first to be
accessed.
Terminology:
• Enqueue: Inserting an element into the queue.
• Dequeue: Removing an element from the queue.
Real-World Examples:
• A single-lane one-way road where the vehicle that enters first exits first.
• Queues at ticket counters and bus stops.

A queue consists of:

1. Front: Points to the first element of the queue.
2. Rear: Points to the last element of the queue.
3. Array or Linked List: Used to store the queue elements.
Operations of a Queue
1. Enqueue: Inserts an element at the rear end of the queue.
2. Dequeue: Deletes an element from the front end of the queue.
3. Peek: Returns the front element without removing it.
4. Queue Overflow (isFull): When the queue is full, further insertions are not possible.
5. Queue Underflow (isEmpty): When the queue is empty, deletions cannot be performed.

ARZU Page 80
ARZU Page 81
Queue Implementation Using Linked List
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. When implemented
using a linked list, the queue can dynamically grow and shrink as elements are added or removed, avoiding
the fixed size limitation of arrays.
Uses:

ARZU Page 82
• Dynamic Memory Allocation: No need to specify a fixed size like arrays.
• Efficient Insertions and Deletions: Insertions occur at the rear, and deletions occur at the front, both in
constant time O(1).
• Avoids Memory Wastage: Unlike arrays, linked lists do not have unused space.
Structure of Queue Using Linked List
A queue implemented with a linked list consists of nodes, where each node contains: 1. Data (value stored
in the node)
2. Pointer to the next node (link to the next element in the queue)

The queue maintains two pointers:

• Front: Points to the first element (used for deletions).
• Rear: Points to the last element (used for insertions).
Operations on Queue Using Linked List
1) Enqueue (Insertion)

• Adds an element at the rear of the queue.

• If the queue is empty, the new node becomes both front and rear.

• Otherwise, the new node is linked to the existing rear, and rear is updated.
2) Dequeue (Deletion)

• Removes an element from the front of the queue.

• If the queue is empty, underflow occurs.

• Otherwise, front moves to the next node.

• If the queue becomes empty after deletion, both front and rear are set to NULL.
3) Display Queue Elements

• Prints all elements from front to rear.

Step-by-Step Execution
Initial State (Empty Queue):
Enqueue Operations:

ARZU Page 83
ARZU Page 84
Breadth-First Search (BFS) Algorithm
Breadth-First Search (BFS) is a traversal technique used in graph theory, where all nodes at the current
level are visited before moving to the next level. It follows the FIFO (First In, First Out) principle and
utilizes a queue to ensure each node is processed in the correct order.

ARZU Page 85
Steps of the BFS Algorithm:
1. Initialization:

o Set the status of each node to 1 (ready state).

2. Enqueue the Start Node:
o Insert the starting node A into the queue and update its status to 2 (waiting state).
3. Processing Nodes Until the Queue is Empty:

o Repeat the following steps until the queue becomes empty:

▪ Dequeue a node, process it, and set its status to 3 (processed state).

▪ Enqueue all its adjacent (unvisited) nodes and set their status to 2 (waiting state).
4. Exit Once All Nodes Are Processed.

Example of BFS Traversal

Graph Representation:

A── B

C──D

Starting BFS from Vertex A:

Step 1: Enqueue the Start Node

• Enqueue A, mark it as visited.

• Queue: [A]

• Visited: {A}

Step 2: Process Node A

• Dequeue A, process it.

• Enqueue its unvisited neighbors B and C.

• Queue: [B, C]

• Visited: {A, B, C}

ARZU Page 86
 Step3: Process Node B

• Dequeue B, process it.

• Enqueue its unvisited neighbor D.

• Queue: [C, D]

• Visited: {A, B, C, D}

Step4: Process Node C

• Dequeue C, process it.

• No unvisited neighbors remain.

• Queue: [D]

• Visited: {A, B, C, D}

Step5: Process Node D

• Dequeue D, process it.

• No unvisited neighbors remain.

• Queue: [] (Empty)

• Visited: {A, B, C, D}

Final Order of BFS Traversal:

A→B→C→D

This completes the breadth-first search traversal of the graph.

Queue in Scheduling
A queue is a fundamental data structure used in scheduling to manage processes and tasks efficiently. In a
scheduling system, multiple tasks or processes request CPU time or resources, and a queue helps organize
them based on a specific scheduling strategy.
1. Types of Scheduling Using Queues
1.1 Job Scheduling (Long-Term Scheduling)
• Determines which jobs (processes) should be admitted into the system for execution. • Maintains a job
queue, where new jobs wait until they are assigned CPU time.

ARZU Page 87
• Example: Batch processing systems use job scheduling to select processes for execution.
1.2 Ready Queue (Short-Term Scheduling)

• Contains all processes that are ready to execute but waiting for CPU allocation.

• The CPU scheduler selects processes based on scheduling algorithms like:

o First Come, First Serve (FCFS)

o Round Robin (RR)

o Shortest Job Next (SJN)

o Priority Scheduling

o Multilevel Queue Scheduling

1.3 Device Queue (I/O Scheduling or Medium-Term Scheduling)

• Processes waiting for I/O operations are placed in an I/O queue.

• Helps in managing devices like printers, hard drives, and network connections.
2. Scheduling Algorithms Using Queues
2.1 First Come, First Serve (FCFS) Scheduling
• Processes are executed in the order they arrive (FIFO).
• Simple but suffers from convoy effect (long processes delay short ones).
2.2 Round Robin (RR) Scheduling

• Each process gets a fixed time slice (quantum) in a cyclic manner.

• Uses a circular queue to manage processes.

• Fair for time-sharing systems.

2.3 Priority Scheduling

• Each process is assigned a priority value.

• The process with the highest priority is executed first.

• Can be preemptive (interrupts lower-priority processes) or non-preemptive.

2.4 Multilevel Queue Scheduling

• Divides processes into multiple priority-based queues.

ARZU Page 88
 • Each queue has its own scheduling algorithm (e.g., FCFS for low-priority, RR for high priority).
3. Real-World Applications of Queue in Scheduling

CPU Scheduling

• Queues manage multiple processes competing for CPU time.

• Ensures fairness and efficient resource allocation.

Print Job Scheduling

• Printers process jobs in the order they are received (FIFO queue).

Network Packet Scheduling

• Data packets are queued before being sent over a network (e.g., routers use priority queues).
Traffic Flow Management

• Traffic signals use queue-based scheduling to control vehicle movement efficiently.

Double Ended Queue (Deque)

A Double Ended Queue (Deque) is a type of queue data structure where insertion and deletion can be
performed at both the front and rear. Unlike a standard queue (FIFO), which allows operations at only one
end, a deque provides greater flexibility.

Operations on Deque
1. Initialize → Create an empty deque with a fixed size.
2. Insertion at Rear → Add elements to the rear (similar to a normal queue).
3. Deletion from Front → Remove elements from the front (FIFO behavior).

ARZU Page 89
4. Insertion at Front → Add elements to the front (not possible in a normal queue).
5. Deletion from Rear → Remove elements from the rear.
6. Full Status Check → Verify if the deque is full before inserting elements.
7. Empty Status Check → Verify if the deque is empty before deleting elements.

ARZU Page 90
ARZU Page 91
ARZU Page 92
Real-World Applications of Queues
[Link] Service Systems

o Used in call centers, banks, hospitals, and ticket booking platforms to ensure First-In First-Out (FIFO)
order.

o Example: Customers are served in the order they arrive.

2. CPU Scheduling

o Operating systems use queues to manage processes waiting for execution.

o Example: Round-robin scheduling uses a queue to manage task execution.

3. Printer Spooling

o Print jobs are stored in a queue before being processed one by one.

o Example: Multiple documents sent to a shared printer are printed sequentially.

4. Data Streaming & Buffers

o Streaming applications use queues to manage data packets in real-time.

o Example: Video buffering in YouTube loads and plays video frames sequentially.
5. Network Packet Scheduling

o Routers use queues to manage incoming and outgoing data packets.

o Example: Prioritization of network packets in Quality of Service (QoS) applications.

6. Breadth-First Search (BFS) in Graph Traversal

o BFS algorithm uses queues to explore graph levels.

o Example: Finding the shortest path in Google Maps.

7. Task Scheduling in Operating Systems

o Job queues handle background processes efficiently.

Example: Task execution in multi-threading environments.

ARZU Page 93
 UNIT-5
Tree in Data Structures
A Tree is a hierarchical data structure that is widely used in computer science. It consists of nodes
connected by edges, forming a structure that resembles a tree in nature. Unlike linear data structures
(arrays, linked lists, stacks, and queues), a tree organizes data in a non-linear way, making it efficient for
searching, sorting, and hierarchical representations.

ARZU Page 94
Basic Concepts of Trees
1. Node
A node is the fundamental unit of a tree. Each node contains:
• Data (Value)
• pointers(like) to its child node is any node
2. Root Node
The topmost node in a tree is called the root. It serves as the starting point of the tree, and every other node
is a descendant of the root.
3. Parent and Child Nodes
• A parent node has links to its child nodes.
• A child node is any bode that has a parent above it.
4. Sibling Nodes
Nodes that share the same parent are called siblings.
5. Leaf Node
A leaf node is a node with no children. It is the endpoint of a tree path.
6. Edge

ARZU Page 95
An edge is a link between two nodes (parent and child).
7. Height of a Tree
The height of a tree is the longest path from the root node to a leaf node.
8. Depth of a Node
The depth of a node is the number of edges from the root to that node.
9. Degree of a Node
The degree of a node is the number of direct children it has.

Types of Trees in Data Structures

1. Binary Tree: Each node has at most two children (left and right).
2. Binary Search Tree (BST): A special binary tree where the left subtree has smaller values and the right
subtree has larger values.
3. Balanced Tree: A tree where the height difference between left and right subtrees is minimal.
4. Heap Tree: A complete binary tree used for heap operations (Min Heap & Max Heap). 5. AVL Tree: A
self-balancing BST where the height difference of left and right subtrees is at most 1.
6. B-Tree: A self-balancing tree used in databases and file systems.

Importance of Trees in Data Structures

1. Efficient Searching and Sorting

o BSTs allow fast searching with O(log n) complexity.

o Trees like Heaps help in sorting algorithms (Heap Sort).

2. Hierarchical Representation

o Used to represent hierarchical data, such as file systems, databases, and XML/HTML documents.
3. Fast Insertions and Deletions

o Unlike arrays, trees allow quick modifications without shifting elements.

4. Memory Optimization

ARZU Page 96
 o Trees provide an efficient way to store and retrieve data dynamically.
5. Used in Graphs and Networks

o Trees are the foundation of graph algorithms, network routing, and AI decision trees.
6. Expression Trees
o Used in parsing mathematical expressions and compilers.

BINARY SEARCH TREE

Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted
manner. Binary search tree follows all properties of binary tree and its left child contains values less than
the parent node and the right child contains values greater than the parent node. This hierarchical structure
allows for efficient Searching, Insertion, and Deletion operations on the data stored in the tree.

Binary Search Tree (BST) is a special type of binary tree in which the left child of a node has a value less
than the node’s value and the right child has a value greater than the node’s value. This property is called
the BST property and it makes it possible efficiently search, insert, and delete elements in the tree.

Properties of Binary Search Tree:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key. • This means
everything to the left of the root is less than the value of the root and everything to the right of the root is
greater than the value of the root. Due to this performing, a binary search is very easy.
• The left and right subtree each must also be a binary search tree.

ARZU Page 97
• There must be no duplicate nodes (BST may have duplicate values with different handling approaches)
Insert a node into a BST:
A new key is always inserted at the leaf. Start searching a key from the root till a leaf node. Once a leaf
node is found, the new node is added as a child of the leaf node.

ARZU Page 98
ARZU Page 99
ARZU Page 100
Binary Tree program in C
#include<stido.h>
struct node
{
int data;
struct node *left, *right;
}
void main()
{
struct node *root;
root = create();
}
struct node *create()
{
struct node *temp;
int data;
temp = (struct node *)malloc(sizeof(struct node));
printf("Press 0 to exit");
printf("\nPress 1 for new node");
printf("Enter your choice : ");
scanf("%d", &choice);
if(choice==0)
{
return 0;
}
else
{
printf("Enter the data:");
scanf("%d", &data);
temp->data = data;
printf("Enter the left child of %d", data);
temp->left = create();

ARZU Page 101

printf("Enter the right child of %d", data);
temp->right = create(); return temp;
}
}

Properties of Binary Search Tree:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key. • This means
everything to the left of the root is less than the value of the root and everything to the right of the root is
greater than the value of the root. Due to this performing, a binary search is very easy.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes(BST may have duplicate values with different handling approaches)
Handling duplicate values in the Binary Search Tree:
• We must follow a consistent process throughout i.e. either store duplicate value at the left or store the
duplicate value at the right of the root, but be consistent with your approach.
Basic Operations on Binary Search Tree:
1. Searching a node in BST:

Searching in BST means to locate a specific node in the data structure. In Binary search tree, searching a
node is easy because of its a specific order. The steps of searching a node in Binary Search tree are
listed as follows
1. First, compare the element to be searched with the root element of the tree.

o If root is matched with the target element, then return the node’s location.

o If it is not matched, then check whether the item is less than the root element, if it is smaller than
the root element, then move to the left subtree.

o If it is larger than the root element, then move to the right subtree.
2. Repeat the above procedure recursively until the match is found.
3. If the element is not found or not present in the tree, then return NULL.
Now, let’s understand the searching in binary tree using an example:
Below is given a BST and we have to search for element

ARZU Page 102

 S

ARZU Page 103

2. Insert a node into a BST:
A new key is always inserted at the leaf. Start searching a key from the root till a leaf node. Once a leaf
node is found, the new node is added as a child of the leaf node.

ARZU Page 104

3. Delete a Node of BST:
It is used to delete a node with specific key from the BST and return the new BST.
Different scenarios for deleting the node:

ARZU Page 105

ARZU Page 106
ARZU Page 107
ARZU Page 108
HASHING
Hashing in Data Structures refers to the process of transforming a given key to another value. It involves
mapping data to a specific index in a hash table using a hash function that enables fast retrieval of
information based on its key. The transformation of a key to the corresponding value is done using a Hash
Function and the value obtained from the hash function is called Hash Code .
Components of Hashing
There are majorly three components of hashing:
1. Key: A Key can be anything string or integer which is fed as input in the hash function the technique that
determines an index or location for storage of an item in a data structure.
2. Hash Function: The hash function receives the input key and returns the index of an element in an array
called a hash table. The index is known as the hash index .
3. Hash Table: Hash table is a data structure that maps keys to values using a special function called a hash
function. Hash stores the data in an associative manner in an array where each data value has its own
unique index.
Hash Table
A Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly. It
operates on the hashing concept, where each key is translated by a hash function into a distinct index in an
array. The index functions as a storage location for the matching value. In simple words, it maps the keys
with the value.
Hash function
The hash function creates a mapping between key and value, this is done through the use of mathematical
formulas known as hash functions. The result of the hash function is referred to as a hash value or hash.
The hash value is a representation of the original string of characters but usually smaller than the original.
Types of Hash Functions
There are many hash functions that use numeric or alphanumeric keys. This article focuses on discussing
different hash functions:
1. Division Method.
2. Multiplication Method
3. Mid-Square Method
4. Folding Method
5. Cryptographic Hash Functions
6. Universal Hashing

ARZU Page 109

7. Perfect Hashing

1. Division Method
The division method involves dividing the key by a prime number and using the remainder as the hash
value.
h(k)=k mod m
Where k is the key and 𝑚m is a prime number.
Advantages:
• Simple to implement.
• Works well when 𝑚m is a prime number.
Disadvantages:
• Poor distribution if 𝑚m is not chosen wisely.
2. Multiplication Method
In the multiplication method, a constant 𝐴A (0 < A < 1) is used to multiply the key. The fractional part of
the product is then multiplied by 𝑚m to get the hash value. h(k)=⌊m(kAmod1)⌋
Where ⌊⌋ denotes the floor function.
Advantages:
• Less sensitive to the choice of 𝑚m.
Disadvantages:
• More complex than the division method.
3. Mid-Square Method
In the mid-square method, the key is squared, and the middle digits of the result are taken as the hash
value.
Steps:
1. Square the key.
2. Extract the middle digits of the squared value.
Advantages:
• Produces a good distribution of hash values.

ARZU Page 110

Disadvantages:
• May require more computational effort.
4. Folding Method
The folding method involves dividing the key into equal parts, summing the parts, and then taking the
modulo with respect to 𝑚m.
Steps:
1. Divide the key into parts.
2. Sum the parts.
3. Take the modulo 𝑚m of the sum.
Advantages:
• Simple and easy to implement.
Disadvantages:
• Depends on the choice of partitioning scheme.
5. Cryptographic Hash Functions
Cryptographic hash functions are designed to be secure and are used in cryptography.
Examples include MD5, SHA-1, and SHA-256.
Characteristics:
• Pre-image resistance.
• Second pre-image resistance.
• collision resistance.
Advantages:
• High security.
Disadvantages:
• Computationally intensive.
6. Universal Hashing
Universal hashing uses a family of hash functions to minimize the chance of collision for any given set of
inputs.
h(k)=((a⋅k+b)modp)modm
Where a and b are randomly chosen constants, p is a prime number greater than m, and k is the key.
Advantages:
• Reduces the probability of collisions.
Disadvantages:

ARZU Page 111

• Requires more computation and storage.
7. Perfect Hashing
Perfect hashing aims to create a collision-free hash function for a static set of keys. It guarantees that no
two keys will hash to the same value.
Types:
• Minimal Perfect Hashing: Ensures that the range of the hash function is equal to the number of keys.
• Non-minimal Perfect Hashing: The range may be larger than the number of keys.
Advantages:
• No collisions.
Disadvantages:
• Complex to construct.
Hashing
Hashing is a technique used in data structures to efficiently store and retrieve data using a hash function. It
transforms an input (key) into a fixed-size value called a hash code or hash value. This value serves as an
index to store the data in a hash table, making data retrieval much faster compared to linear searches.
Role of Hash Functions in Data Storage and Retrieval
A hash function plays a critical role in hashing by mapping a given key to a specific location in a hash
table. The efficiency of hashing depends on how well the hash function distributes data across the table.
Key Functions of a Hash Function:
1. Efficient Indexing:
o Converts keys into hash values that determine their position in the table.
o Reduces search time from O(n) (linear search) to O(1) (constant time) in ideal cases.

2. Minimizing Collisions:
o Collisions occur when multiple keys map to the same index.
o A good hash function distributes data evenly across the hash table to reduce collisions.
3. Fast Data Retrieval:
o The hash function ensures that looking up a key in a hash table is quick by providing a direct index.
4. Security (in some cases):
o In cryptographic hashing, hash functions are designed to be irreversible to secure data (e.g., password
storage).
Collision Handling Techniques

ARZU Page 112

Since multiple keys may generate the same hash index, collision handling techniques include:
1. Chaining: Uses linked lists at each index to store multiple values.
2. Open Addressing: Finds an alternative empty slot within the table (e.g., linear probing).
Example of a Hash Function
A simple hash function for storing student roll numbers could be:
H(x)=x mod 10
This function divides a number by 10 and uses the remainder as the index.

When we need to find student 202, we go directly to index 2, making retrieval O(1) in the best case.

Collision Handling in Hashing

Sometimes, different keys can generate the same hash index. This situation is called a collision. To handle
collisions, we use these two main techniques:
1. Chaining (Separate Chaining)
• Instead of storing just one value at an index, a linked list is used to store multiple values at the same
location.
• If a collision occurs, the new value is added to the linked list at that index.

ARZU Page 113

When searching for 121, we go to index 1 and traverse the linked list.
2. Open Addressing
Instead of using a linked list, open addressing finds another available slot within the hash table.
Types of Open Addressing
• Linear Probing: If a collision occurs, check the next available slot (index + 1).
• Quadratic Probing: Use a quadratic function to find a new slot.
• Double Hashing: Apply a secondary hash function to determine the next available slot.

Applications of Hashing
Hashing is a powerful technique used in various domains for efficient data storage, retrieval, and security.
It allows quick access to information by mapping keys to unique index values, making searches faster and
more reliable.
Some important applications of hashing include:

ARZU Page 114

 1. Database Indexing – Hashing speeds up searching in databases by quickly locating records using
hash indexes instead of scanning entire tables. This improves query performance significantly.
2. Password Storage & Security – Hash functions like SHA-256 and bcrypt convert passwords into
irreversible hash values, protecting user credentials from cyberattacks.
3. Data Deduplication – Hashing helps identify duplicate files by generating unique hash values for
file contents, saving storage space in cloud storage systems.
4. Digital Signatures & Blockchain – Cryptographic hash functions ensure data integrity in digital
signatures and blockchain transactions, preventing unauthorized alterations.
5. Compiler Symbol Tables – Programming languages use hash tables to store variable names,
function names, and keywords efficiently, enabling fast lookups during compilation.
6. File Systems & Searching – Hashing enhances file search operations in file systems (e.g., NTFS,
ext4) by mapping file names to storage locations, making retrieval faster.

Use of Hashing in Unique Identifier Generation

Unique identifiers (UIDs) play a critical role in various applications, ensuring that every entity (such as a
user, transaction, or resource) has a distinct and non-repetitive identity.
Hashing helps generate such identifiers efficiently in different scenarios:
1. UUIDs (Universally Unique Identifiers) –

o Hash functions such as MD5 and SHA-1 create unique IDs based on timestamps, random values, or
device addresses.

o These identifiers are widely used in distributed databases, blockchain, and authentication systems to
prevent duplication.
2. Shortened URLs –

o URL shortening services like Bitly and TinyURL use hashing to convert long URLs into short, fixed-
length unique identifiers.

o This helps in efficient URL redirection while preventing duplicate entries.

3. Checksum & Data Integrity Verification –

o Hash functions create unique signatures (checksums) for files, ensuring that they remain unchanged
during transmission.

o This is crucial for software downloads, ensuring that files have not been corrupted or tampered with.

ARZU Page 115

Use of Hashing in Caching
Caching improves system performance and response time by storing frequently accessed data in temporary
storage. Hashing optimizes caching by mapping frequently requested data to specific memory locations,
reducing the need for expensive database or network calls.
1. Web Caching (CDNs & Browsers) –

o Content Delivery Networks (CDNs) use hashing to distribute cached web content across multiple
servers, speeding up page loading times.

o Browsers also use hash-based caching to store frequently visited web pages locally, reducing repeated
data downloads.
2. Database Caching (Redis, Memcached) –

o Database caching stores frequently queried results in memory using hash tables, reducing database
access time.

o Technologies like Redis and Memcached rely on hashing to efficiently store and retrieve cached
objects.
3. CPU & Memory Caching –

o Processors use hashing to map frequently accessed memory addresses to cache memory, minimizing the
time taken to fetch data from the main memory.

o This improves the performance of applications by reducing memory access latency.

4. DNS Caching –

o DNS resolvers use hash-based caching to store recently resolved domain names and IP addresses,
reducing the need for repeated DNS queries.

o This speeds up internet browsing and minimizes network congestion.

ARZU Page 116

 Data Structures Important Questions
ESSAY QUESTIONS
Unit-1
1. What is data structure? Explain its role in problem solving? Explain the different types of data
structure with suitable examples
2. What is Linear Search? Explain its working with an example and analyze its time complexity.
3. What is Binary Search? Explain how it works with an example and write a program to implement it.
4. Explain the Bubble Sort algorithm with an example and analyze its time complexity.
5. Describe the Selection Sort algorithm with an example and discuss its efficiency.
6. What is Insertion Sort? Explain its working with an example and compare its performance with other
sorting techniques.

Unit-2
1. What is a Singly Linked List? Explain its representation and basic operations with examples.
2. Explain the structure of a doubly linked list and describe its key operations with examples.
3. Explain the types of circular linked lists with examples and diagrams.
4. What are the advantages and disadvantages of single linked list and double linked list.
5. Write a program to implement a Singly Linked List with insert and delete operations.
Unit-3
1. What is a stack? Explain its properties and basic operations with examples.
2. Write algorithms for stack ADT. Implement stack using arrays?
3. How is a stack used in expression evaluation? Explain with an example of infix to postfix conversion?
4. What is backtracking? How does a stack help in solving back tracking problems?
5. Explain how a stack can be used to reverse a linked list with an example.

Unit-4
1. What is a Queue? Explain its properties and basic operations with examples.
2. Write algorithms for queue ADT. Implement Queue using linkedlist?
3. Explain the Queues in Breadth-First Search (BFS) and Scheduling.
4. What is a Deque (Double-Ended Queue)? Explain its types and operations with examples.
5. Discuss real-world applications of queues and how they differ from regular deques.

Unit-5
1. What is a Tree? Explain its basic concepts and importance in data structures.
2. What is a Binary Search Tree (BST)? Explain insertion, deletion operations with examples.
3. What is Hashing? Explain the role of hash functions in data storage and retrieval.

ARZU Page 117

4. What is meant by tree traversal? Explain different types of tree traversal with an example.
5. Define Collision. Explain various collision resolving techniques.

Short Answer Questions:

Unit – I

1. Define sorting.
2. List any two differences between linear and binary search.
3. Define ADT and list various ADT’s with an example.
4. Write the time complexity of bubble sort and insertion sort.
5. Differentiate stable and unstable sorting.

Unit – II

1. Write the structure syntax to create a node in doubly linked list.

2. Write the major difference between single linked list and circular linked list.
3. List various operations that are supported by the linked list.

Unit – III

1. Define stack and write its working principle.

2. Write the procedure to evaluate the postfix expression evaluation.
3. List various expression evaluation strategies.
4. Write the major difference between prefix and postfix expression evaluations.

Unit – IV

1. Define queue and write its working principle.

2. Write a short note on round robin scheduling algorithm.
3. List various applications of queues.
4. Write the procedure for Breadth First Search.

Unit – V

1. Write the properties of a Binary Search Tree.

2. Define hash table and hash function.
3. Write the hash function used in double hashing collision resolving technique.
4. Write the applications of hashing.
5. Differentiate in order, Preorder and Post order traversals briefly.

ARZU Page 118

ARZU Page 119
ARZU Page 120