DAY 4
CHAPTER 2: DATA STRUCTURE
Introduction to Data Structure
A Data Structure is a way of organizing, storing, and
managing data in memory so that it can be accessed
and modified efficiently.
Why Data Structures are needed
Efficient data access
Better memory utilization
Faster processing
Easy data management
Types of Data Structures
Primitive: int, char, float
Non-Primitive:
Linear: Array, Stack, Queue, Linked List
Non-Linear: Tree, Graph
Shruti Dandekar
Data Structure Operations
Common operations performed on data structures:
Traversal – Accessing elements
Insertion – Adding an element
Deletion – Removing an element
Searching – Finding an element
Sorting – Arranging elements
Merging – Combining structures
Shruti Dandekar
Algorithm Notation
An algorithm is a finite set of steps to solve a
problem.
an algorithm is a step by step instructions to
perform a particular operation
Characteristics
Input
Output
Definiteness
Finiteness
Effectiveness
Algorithm Representation
Natural language
Flowchart
Pseudocode
Shruti Dandekar
Control Structures
Control structures decide the flow of execution:
Sequential
Conditional
Repetitive
Shruti Dandekar
Sequential Control Structure
Statements execute one after another
No condition or repetition
Example: Input → Process → Output
Shruti Dandekar
Conditional Control Structure
Execution depends on condition
Uses:
if
if-else
switch case
Shruti Dandekar
Repetitive Control Structure
Repeats statements
Uses loops:
for
while
do-while
Shruti Dandekar
Array
Array is a collection of same type elements
Stored in contiguous memory locations
Elements accessed using index
Shruti Dandekar
Representation of Array in Memory
Continuous memory allocation
Address calculation:
Address = Base Address + (Index × Size)
Shruti Dandekar
Reversing a Linear Array
Reverse means changing order of elements
First element swapped with last
Continue till middle of array
Shruti Dandekar
Insertion in Linear Array
Insert element at specified position
Shift elements to right
Increase array size by one
Shruti Dandekar
Algorithm:
1. Start
2. Set J = N
3. Set N = N + 1
4. Repeat steps 5 and 6 while J >= K:
5. Set LA[J+1] = LA[J] // Shift element to the right
6. Set J = J - 1 // Decrease counter
7. Set LA[K] = ITEM // Insert the new element
8. Stop
Shruti Dandekar
Deletion from Linear Array
Remove element from given position
Shift elements to left
Reduce array size
Shruti Dandekar
Algorithm: Deletion in an Array
1. Start
2. Input array A, size n, and position pos to delete
3. Check if pos is valid (1 ≤ pos ≤ n)
If not valid, Stop
4. Shift elements from index pos to n-1 one position
to the left
A[i] = A[i+1]
5. Reduce size: n = n − 1
6. Stop
Shruti Dandekar
Sorting
Sorting arranges elements in order
Types:
Ascending
Descending
Shruti Dandekar
Bubble Sort
Simple sorting technique
Compares adjacent elements
Swaps if they are in wrong order
Shruti Dandekar
BUBBLE_SORT(A, n)
BEGIN
FOR i ← 0 TO n-2 DO
FOR j ← 0 TO n-2-i DO
IF A[j] > A[j+1] THEN
temp ← A[j]
A[j] ← A[j+1]
A[j+1] ← temp
END IF
END FOR
END FOR
END
Shruti Dandekar
Searching
Process of finding an element in data
Types:
Linear Search
Binary Search
Shruti Dandekar
Linear Search
Searches element one by one
Works on sorted and unsorted arrays
Time complexity: O(n)
Shruti Dandekar
Linear Search Algorithm
1. Start
2. Input array A, size n, and element key to search
3. For i = 0 to n − 1
If A[i] == key, display “Element found at
position i+1” and Stop
4. If end of array is reached, display “Element not
found”
5. Stop
Shruti Dandekar
Binary Search
Works only on sorted array
Divides array into halves
Faster than linear search
Shruti Dandekar
Binary Search Algorithm
(Array must be sorted)
1. Start
2. Input sorted array A, size n, element key
3. Set low = 0, high = n − 1
4. While low ≤ high
mid = (low + high) / 2
If A[mid] == key, display “Element found” and
Stop
If A[mid] < key, set low = mid + 1
Else set high = mid − 1
5. If not found, display “Element not found”
6. Stop
Shruti Dandekar
Pointer Array
Definition
A pointer array is an array where each element
stores the address of a variable or another array.
Used to store addresses instead of actual data.
Example
int a = 10, b = 20, c = 30;
int *ptr[3] = {&a, &b, &c};
Advantages
Efficient memory usage
Useful for dynamic data structures
Shruti Dandekar
Records
Definition
A record is a collection of related data items of
different data types.
In C++, records are implemented using structure
(struct) and Class.
Example
struct Student {
int roll;
char name[20];
float marks;
};
Class Student{
//code
}
Shruti Dandekar
Linked List
Definition
A linked list is a dynamic data structure
Elements are stored as nodes
Each node contains:
Data
Address of next node
Types of Linked List
Singly Linked List
Doubly Linked List
Circular Linked List
Shruti Dandekar
Tree
Definition
A tree is a non-linear hierarchical data structure
Consists of nodes connected by edges
Top node is called root
Types of Tree
Binary Tree
Binary Search Tree (BST)
AVL Tree
Heap
B-Tree
Shruti Dandekar
Binary Tree
Each node has at most two children
Left child and Right child
Applications
Expression evaluation
Searching and sorting
Shruti Dandekar
Stack
Definition
Stack is a linear data structure
Follows LIFO (Last In First Out) principle
Operations
Push
Pop
Peek
Can be implemented using:
Array
Linked List
Applications
Function calls
Expression evaluation
Undo/Redo operations
Shruti Dandekar
Queue
Definition
Queue is a linear data structure
Follows FIFO (First In First Out) principle
Operations
Enqueue
Dequeue
Front
Types of Queue
Simple Queue
Circular Queue
Priority Queue
Deque (Double Ended Queue)
Applications of Queue
CPU scheduling
Printer queue
Breadth First Search (BFS)
Traffic management systems
Shruti Dandekar