UNIT I: INTRODUCTION TO DATA
STRUCTURES
Data Structure Operations
Every data structure allows certain basic operations to manipulate the data effectively. The
commonly supported operations are:
1. Traversal
2. Insertion
3. Deletion
4. Searching
5. Sorting
6. Merging
Let’s discuss each with examples and illustrative diagrams.
1. Traversal
Definition: Visiting each element of a data structure exactly once to process it.
Example (Array Traversal):
Array: [10, 20, 30, 40, 50]
Diagram:
Index: 0 1 2 3 4
Value: 10 20 30 40 50
Traversal visits: 10 → 20 → 30 → 40 → 50
2. Insertion
Definition: Adding a new element at a specific position.
Example (Array Insertion): Insert 25 at position 2 in the array [10, 20, 30, 40].
Diagram (Before):
Index: 0 1 2 3
Value: 10 20 30 40
Diagram (After Insertion):
Index: 0 1 2 3 4
Value: 10 20 25 30 40
In Linked List, insertion is simpler: just adjust node pointers.
Linked List Insert at Middle:
Before: 10 → 20 → 30 → 40
After: 10 → 20 → 25 → 30 → 40
3. Deletion
Definition: Removing an element from the data structure.
Example (Array Deletion): Delete 30 from [10, 20, 30, 40, 50].
Diagram (Before):
Index: 0 1 2 3 4
Value: 10 20 30 40 50
Diagram (After Deletion):
Index: 0 1 2 3
Value: 10 20 40 50
Linked List Deletion:
Before: 10 → 20 → 30 → 40
After: 10 → 20 → 40
4. Searching
Definition: Finding the position of an element in the data structure.
Example (Linear Search in Array): Search for 40 in [10, 20, 30, 40, 50].
Diagram:
Check: 10 → 20 → 30 → 40 ✅ Found at index 3
Binary Search (if sorted): Divide array into halves repeatedly.
Example: Search 40 in Sorted Array [10, 20, 30, 40, 50].
Step 1: Middle = 30 → 40 > 30 → Search right
Step 2: Middle = 40 → ✅ Found
5. Sorting
Definition: Arranging elements in ascending or descending order.
Example (Bubble Sort on [40, 10, 30, 20]):
Pass 1: [40, 10, 30, 20] → [10, 40, 30, 20] → [10, 30, 40, 20] → [10, 30, 20, 40]
Pass 2: [10, 30, 20, 40] → [10, 20, 30, 40]
Final Sorted Array: [10, 20, 30, 40]
6. Merging
Definition: Combining two sorted data structures into one sorted structure.
Example (Merging Two Arrays):
Array A: [10, 30, 50]
Array B: [20, 40, 60]
Merging Process:
Step 1: Compare 10 & 20 → Pick 10
Step 2: Compare 30 & 20 → Pick 20
Step 3: Compare 30 & 40 → Pick 30
Step 4: Compare 50 & 40 → Pick 40
Step 5: Compare 50 & 60 → Pick 50
Step 6: Pick 60
Merged Array: [10, 20, 30, 40, 50, 60]
