Data Structures: Basic to Advanced Notes
1. Introduction
A data structure is a way to organize and store data so it can be accessed and modified efficiently.
2. Types
Primitive: int, float, char, bool. Non-primitive: arrays, linked lists, stacks, queues, trees, graphs,
hash tables.
3. Arrays
Contiguous memory, O(1) access, fixed size.
4. Linked Lists
Nodes connected by pointers. Types: singly, doubly, circular.
5. Stack
LIFO. Operations: push, pop, peek.
6. Queue
FIFO. Types: simple, circular, priority, deque.
7. Trees
Root, parent, child, leaf. Binary tree, BST, AVL, Heap, Trie.
8. Graphs
Vertices and edges. BFS, DFS, directed/undirected, weighted.
9. Hash Tables
Key-value mapping using hash functions. Average O(1) search.
10. Heaps
Complete binary tree used for priority queues.
11. Time Complexity
Big-O: O(1), O(log n), O(n), O(n log n), O(n²).
12. Sorting
Bubble, Selection, Insertion, Merge, Quick, Heap sort.
13. Searching
Linear search O(n), Binary search O(log n) on sorted arrays.
14. Advanced
AVL Trees, Red-Black Trees, B-Trees, Segment Trees, Fenwick Trees, Tries, Disjoint Set Union,
Dynamic Programming data structures.
15. Tips
Choose the data structure based on operation needs: access, insertion, deletion, memory.