Data Structures - BSCS Notes

Data Structures — Complete BSCS Notes

Introduction to Data Structures

Definition: A data structure is a way of organizing and storing data so it can be accessed and modified efficiently.
Examples: Arrays, stacks, queues, linked lists, trees, graphs.
Purpose: Improve storage, retrieval speed, and algorithm efficiency.

Linear Data Structures

Array: Fixed-size collection of same-type elements stored in contiguous memory.
Example: marks[5]
Stack: LIFO (Last In First Out).
Operations: push, pop, peek
Queue: FIFO (First In First Out).
Operations: enqueue, dequeue
Priority Queue: Elements removed based on priority.
Linked List: Nodes connected through pointers.
Types: singly, doubly, circular

Non-Linear Data Structures

Trees: Hierarchical structure with root, parent, child, leaf nodes.
Types: Binary Tree, BST, AVL, Heap
Graphs: Set of vertices and edges.
Types: Directed, Undirected, Weighted
Traversals: DFS, BFS, inorder, preorder, postorder

Recursion, Sorting & Searching

Recursion: Function calling itself.
Example: factorial(n)
Sorting: Bubble, Selection, Insertion, Merge, Quick sort
Searching: Linear Search, Binary Search
Storage & Retrieval: Techniques depend on chosen structure and access pattern.

Hashing

Definition: Technique to map keys to indexes using hash functions.
Example: hash(key) % size
Collision Handling: Chaining, Linear Probing, Quadratic Probing

Algorithm Complexity

Time Complexity: Amount of time algorithm takes.
Notation: O(1), O(n), O(log n), O(n²)
Space Complexity: Memory used by algorithm.
Polynomial Algorithms: Efficient algorithms like O(n²)
Intractable Algorithms: Very slow algorithms such as exponential O(2ⁿ)
Efficient Classes: Best, average, worst-case analysis

Algorithm Design Techniques

Divide and Conquer: Break problem into smaller parts.
Example: Merge Sort
Dynamic Programming: Store subproblem results.
Example: Fibonacci, Knapsack
Greedy Method: Choose locally optimal solution.
Example: Activity Selection, Dijkstra