Scribd
Upload
11 views3 pages

Data Structures Unit1 Unit2 Notes

This document provides an overview of data structures, including definitions, classifications, and operations, as well as specific types such as arrays and matrices. It also covers sorting algorithms like insertion sort, selection sort, and merge sort, along with searching techniques including linear and binary search, and introduces hashing for efficient data access. The content is structured into two units: Introduction to Data Structures and Sorting and Searching.

Uploaded by

Yash Krishna ,lX - C, 57
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views3 pages

Data Structures Unit1 Unit2 Notes

This document provides an overview of data structures, including definitions, classifications, and operations, as well as specific types such as arrays and matrices. It also covers sorting algorithms like insertion sort, selection sort, and merge sort, along with searching techniques including linear and binary search, and introduces hashing for efficient data access. The content is structured into two units: Introduction to Data Structures and Sorting and Searching.

Uploaded by

Yash Krishna ,lX - C, 57
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures – Unit I & Unit II (Exam Notes)

UNIT I – INTRODUCTION TO DATA STRUCTURES

1. Data Structure
A data structure is a way of organizing and storing data in a computer so that it can be accessed and
modified efficiently. It helps in managing large amounts of data and performing operations like searching,
sorting, insertion, and deletion.

Examples: Array, Linked List, Stack, Queue, Tree, Graph

2. Basic Terminology
Term Meaning
Data Raw facts and figures
Data Item Single unit of data
Entity Real-world object represented in a system
Attribute Property of an entity
Record Collection of related fields
File Collection of related records

3. Classification of Data Structures


Data structures are classified into two main types: Primitive and Non■Primitive.
Primitive Data Structures
- Integer
- Float
- Character
- Boolean

Non■Primitive Data Structures


1. Linear Data Structures
- Array
- Stack
- Queue
- Linked List

2. Non■Linear Data Structures


- Tree
- Graph

4. Operations on Data Structures


Traversal – Visiting each element
Insertion – Adding new element
Deletion – Removing element
Searching – Finding element
Sorting – Arranging data
Merging – Combining two data structures

5. Array
An array is a linear data structure that stores a fixed number of elements of the same type in contiguous
memory locations.
Example:
A = [10, 20, 30, 40, 50]
Index representation:
A[0] = 10
A[1] = 20
A[2] = 30

6. Multidimensional Arrays
Example of 2D Array (Matrix)

1 2 3
4 5 6

Declaration example:
int A[2][3]

7. Sparse Matrix
A sparse matrix is a matrix in which most elements are zero. Instead of storing all values, only non■zero
elements and their positions are stored to save memory.

8. Triangular Matrices
Lower Triangular Matrix
1 0 0
2 3 0
4 5 6

Upper Triangular Matrix


1 2 3
0 4 5
0 0 6

Tri■Diagonal Matrix
1 2 0
3 4 5
0 6 7

UNIT II – SORTING AND SEARCHING


1. Insertion Sort
Insertion sort builds the final sorted array one element at a time by inserting elements into their correct
position.
Example:

Original: 8 3 5 2
Step1: 3 8 5 2
Step2: 3 5 8 2
Step3: 2 3 5 8

Time Complexity: O(n²)

2. Selection Sort
Selection sort repeatedly selects the smallest element from the unsorted part and places it at the
beginning.
Example:

Original: 7 4 5 2
Sorted: 2 4 5 7

Time Complexity: O(n²)

3. Merge Sort
Merge sort is a divide and conquer algorithm that divides the array into smaller parts, sorts them, and
merges them back together.
Example:

8 3 6 2
Split → (8 3) (6 2)
Sort → (3 8) (2 6)
Merge → 2 3 6 8

Time Complexity: O(n log n)

4. Linear Search
Linear search checks each element sequentially until the desired element is found.
Example:
Array: [10,20,30,40]
Search: 30

10 → 20 → 30 ✓

Time Complexity: O(n)

5. Binary Search
Binary search works on sorted arrays and repeatedly divides the search interval in half.
Example:
Array: 1 3 5 7 9
Search: 7

Middle → 5
Right side → 7 ✓

Time Complexity: O(log n)

6. Hashing
Hashing uses a hash function to convert a key into an index in a hash table for fast data access.
Example:
Key = 25
Hash function = key % 10
Index = 5

Time Complexity: O(1)

You might also like