UNIT 1 – INTRODUCTION TO DATA STRUCTURES
1. Data
Definition:
Data is the raw material from which information is produced. It can be numbers, characters,
images, sounds, or any symbols that represent facts, observations, or measurements. By itself,
data has no meaning until it is processed and interpreted.
Key Points:
Can be structured (tables, records) or unstructured (images, videos).
Forms the input for any computer program.
Example:
85, blue, "Shivani", 5.9 — these are raw data values.
2. Data Objects
Definition:
A data object is a set of data elements that share common properties and are operated upon as
a single unit. It defines the domain of values for an abstract data type.
Key Points:
Logical representation of related data.
Example: Integer data object contains all integers {…, -2, -1, 0, 1, 2, …}.
Example in real life:
A Student object containing name, roll number, marks as its properties.
3. Abstract Data Type (ADT)
Definition:
An Abstract Data Type is a mathematical model that defines a data type in terms of its
behavior from the point of view of a user, specifically the set of possible values and the
allowed operations, without specifying the implementation details.
Key Points:
Focuses on what operations are possible, not how they are done.
Can be implemented using arrays, linked lists, etc., without changing the ADT
definition.
Example:
Stack ADT: Operations – push, pop, peek; Implementation – could be via array or
linked list.
4. Data Structure
Definition:
A data structure is a systematic way of organizing and storing data in a computer so it can
be accessed and modified efficiently. The choice of data structure affects memory usage and
execution speed.
Key Points:
Classified into linear (array, stack, queue) and non-linear (tree, graph).
Can be static (size fixed at compile time) or dynamic (size changes at runtime).
Real-life Example:
Books on a shelf (linear order).
Family tree chart (non-linear).
5. Algorithm
Definition:
An algorithm is a step-by-step set of instructions to solve a problem or perform a task. It
must be finite, well-defined, and effective.
Characteristics:
1. Input
2. Output
3. Definiteness (clear steps)
4. Finiteness (ends after a finite number of steps)
5. Effectiveness (simple enough to execute)
Example:
Algorithm to make tea:
1. Boil water
2. Add tea leaves
3. Add milk and sugar
4. Pour into cup
6. Space Complexity
Definition:
Space complexity is the total memory required by an algorithm to run to completion. It
includes memory for variables, constants, program instructions, and function calls.
Key Points:
Formula: S(P) = C + Sp (C = fixed part, Sp = variable part).
Dependent on problem size and algorithm.
Example:
If an algorithm uses 3 integer variables (12 bytes) + 1 array of size n (4n bytes), space
complexity = 12 + 4n bytes.
7. Time Complexity
Definition:
Time complexity is the total time taken by an algorithm to execute completely, measured as a
function of input size n.
Key Points:
Helps compare efficiency of algorithms.
Measured in terms of number of basic operations.
Example:
Linear search: O(n) (checks each element once).
8. Asymptotic Notations
a) Big-O (O) – Worst Case
Describes the upper bound of an algorithm’s running time.
Guarantees that the algorithm will not take longer than this bound.
Example: Binary search → O(log n).
b) Theta (Θ) – Average Case
Describes the tight bound of an algorithm.
Gives an exact growth rate for the average case.
Example: Insertion sort → Θ(n²) average case.
c) Omega (Ω) – Best Case
Describes the lower bound of an algorithm’s running time.
Best-case scenario performance.
Example: Insertion sort → Ω(n) when array is already sorted.
9. Sorting
Definition:
Sorting means arranging data in a specific order (ascending or descending) to make searching
and processing easier.
Example:
Ascending order of roll numbers: 12, 18, 20, 25.
Descending order of marks: 95, 88, 74, 60.
10. Types of Sorting
a) Internal Sorting:
Sorting performed entirely in the main memory.
Suitable for small datasets.
b) External Sorting:
Sorting performed when data is too large to fit in main memory, using external
storage.
Example: Merge sort with disk files.
11. Comparison-Based Sorting Methods
a) Bubble Sort
Definition:
Bubble Sort is a simple comparison-based algorithm where adjacent elements are compared,
and if they are in the wrong order, they are swapped. This process is repeated until the list is
sorted.
Characteristics:
Works by “bubbling” larger elements towards the end of the list.
Simple to implement but slow for large datasets.
Example:
List: [5, 3, 4]
Pass 1: [3, 4, 5] → sorted
Pseudocode:
procedure bubbleSort(A, n)
for i = 0 to n-1
for j = 0 to n-i-2
if A[j] > A[j+1]
swap A[j], A[j+1]
end procedure
Complexity:
Best case: O(n) (already sorted)
Worst/Average: O(n²)
b) Insertion Sort
Definition:
Insertion Sort works by taking one element from the unsorted portion and inserting it into its
correct position in the sorted portion of the list.
Characteristics:
Efficient for small datasets.
Stable sorting algorithm.
Example:
List: [4, 3, 5]
Pass 1: [3, 4, 5]
Pseudocode:
procedure insertionSort(A, n)
for i = 1 to n-1
key = A[i]
j=i-1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j=j-1
A[j+1] = key
end procedure
Complexity:
Best: O(n) (already sorted)
Worst/Average: O(n²)
c) Selection Sort
Definition:
Selection Sort repeatedly finds the minimum element from the unsorted part and swaps it
with the first unsorted element.
Characteristics:
Simple but not stable.
Works well for small lists.
Example:
List: [3, 1, 2]
Pass 1: [1, 3, 2]
Pass 2: [1, 2, 3]
Pseudocode:
procedure selectionSort(A, n)
for i = 0 to n-2
min = i
for j = i+1 to n-1
if A[j] < A[min]
min = j
swap A[i], A[min]
end procedure
Complexity:
Best/Worst/Average: O(n²)
d) Shell Sort
Definition:
Shell Sort is an improved version of Insertion Sort where elements far apart are compared
and swapped first. The gap between compared elements is gradually reduced until it becomes
1 (regular insertion sort).
Characteristics:
Faster than insertion sort for large datasets.
Not stable.
Example:
List: [8, 5, 3, 1] → Gap=2 → compare 8 & 3, 5 & 1 → then Gap=1 → regular insertion sort.
Pseudocode:
procedure shellSort(A, n)
gap = n / 2
while gap > 0
for i = gap to n-1
temp = A[i]
j=i
while j >= gap and A[j-gap] > temp
A[j] = A[j-gap]
j = j - gap
A[j] = temp
gap = gap / 2
end procedure
Complexity:
Average: O(n^1.5)
Worst: O(n²)
