Scribd
Upload
2 views4 pages

Data Structures & Algorithms Overview

Data Structures are organized ways to manage data efficiently, classified into linear (e.g., arrays, linked lists) and non-linear (e.g., trees, graphs) types. Key operations include traversing, inserting, deleting, searching, and sorting, with algorithms evaluated on time and space complexity. Arrays, including one-dimensional and multi-dimensional types, have specific memory representations and operations, with searching methods like linear and binary search demonstrating different efficiencies.

Uploaded by

bhupendrasenapati23
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
2 views4 pages

Data Structures & Algorithms Overview

Data Structures are organized ways to manage data efficiently, classified into linear (e.g., arrays, linked lists) and non-linear (e.g., trees, graphs) types. Key operations include traversing, inserting, deleting, searching, and sorting, with algorithms evaluated on time and space complexity. Arrays, including one-dimensional and multi-dimensional types, have specific memory representations and operations, with searching methods like linear and binary search demonstrating different efficiencies.

Uploaded by

bhupendrasenapati23
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 & Algorithms - Unit I Notes

Introduction and Overview

Definition of Data Structures:

- A data structure is a way of organizing data so that it can be used efficiently.

Classification:

- Linear: Arrays, Linked Lists, Stacks, Queues

- Non-linear: Trees, Graphs

- Static: Fixed size (Array)

- Dynamic: Variable size (Linked List)

Operations:

- Traversing, Inserting, Deleting, Searching, Sorting, Merging

Algorithms

Complexity:

- Time Complexity: Time taken based on input size (O notation)

- Space Complexity: Memory used

Time-Space Tradeoff:

- Balance between faster execution and higher memory use.

Arrays
Data Structures & Algorithms - Unit I Notes

Definition:

- Collection of elements stored in contiguous memory.

Classification:

- 1D, 2D, Multi-Dimensional

Memory Representation:

- 1D: Base_Address + (Index × Size)

- 2D (Row-major): A[i][j] = Base + ((i × columns) + j) × Size

Operations on Linear Arrays

1. Traversal: Visit all elements one by one.

2. Insertion: Add new element, shifting as needed.

3. Deletion: Remove element and shift.

4. Searching:

- Linear Search: O(n)

- Binary Search: O(log n)

5. Sorting:

- Bubble Sort: Repeated swaps (O(n²))

- Selection Sort: Select min and swap (O(n²))

- Insertion Sort: Insert in sorted part (O(n²), best O(n))

6. Merging: Combine two sorted arrays.


Data Structures & Algorithms - Unit I Notes

Searching Algorithms

Linear Search:

- Check each element until found.

- Time: O(n)

Binary Search:

- Only for sorted arrays, divide and search.

- Time: O(log n)

Comparison:

| Method | Time | Condition |

|---------------|------------|----------------|

| Linear Search | O(n) | Any array |

| Binary Search | O(log n) | Sorted array |

Two-Dimensional Arrays

Definition:

- Matrix with rows and columns

Memory Representation:

- Row-major: Row by row

- Column-major: Column by column


Data Structures & Algorithms - Unit I Notes

Matrices and Sparse Matrices

Matrix:

- Regular 2D array

Sparse Matrix:

- Mostly zero elements

- Efficient format: Row | Column | Value

Multi-Dimensional Arrays

- Arrays with >2 dimensions, e.g., int arr[3][3][3]

You might also like