Data Structure Notes
1. Introduction to Data Structures
- Definition: A data structure is a way of organizing, managing, and storing data so that it can be
accessed and modified efficiently.
- Types:
1. Primitive Data Structures – int, float, char, boolean.
2. Non-Primitive Data Structures – arrays, lists, stacks, queues, trees, graphs, hash tables.
2. Classification of Data Structures
1. Linear Data Structures – stored sequentially (Array, Linked List, Stack, Queue).
2. Non-Linear Data Structures – stored hierarchically (Tree, Graph).
3. Linear Data Structures
(a) Array
- Contiguous memory, fixed size, fast access.
- Complexity: Access O(1), Search O(n), Insert/Delete O(n).
(b) Linked List
- Nodes with data + pointer.
- Types: Singly, Doubly, Circular.
- Complexity: Search O(n), Insert/Delete O(1) if pointer known.
(c) Stack
- LIFO structure.
- Operations: Push, Pop, Peek.
- Complexity: Push/Pop O(1).
(d) Queue
- FIFO structure.
- Types: Simple, Circular, Priority, Deque.
- Complexity: Enqueue/Dequeue O(1).
4. Non-Linear Data Structures
(a) Tree
- Hierarchical structure with root.
- Types: Binary Tree, BST, AVL, Heap, B-Tree.
- Complexity (BST): O(log n) average, O(n) worst.
(b) Graph
- Vertices and Edges.
- Representations: Adjacency Matrix, Adjacency List.
- Traversals: DFS, BFS.
5. Hashing
- Hash Table stores key–value pairs.
- Collisions: Chaining, Open Addressing.
- Complexity: O(1) average.
6. Algorithms
- Searching: Linear O(n), Binary O(log n).
- Sorting: Bubble, Selection, Insertion O(n²); Merge, Quick, Heap O(n log n).
7. Complexity Analysis
- Big O → Worst case
- Big Ω → Best case
- Big Θ → Average case
