Complete Data Structures Notes (Basic to Advanced) - in C
1. Introduction to Data Structures
Data Structures (DS) are specialized formats for organizing, processing, retrieving, and storing data.
They are broadly categorized as:
- Primitive: int, char, float, etc.
- Non-Primitive: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs.
Data structures are divided into:
- Linear (Array, Linked List, Stack, Queue)
- Non-linear (Tree, Graph)
2. Arrays
Arrays store elements in contiguous memory locations.
Syntax in C: int arr[5];
Advantages: Fast access via index.
Limitations: Fixed size.
Operations:
- Traversal
- Insertion
- Deletion
- Searching
3. Strings
Strings are arrays of characters ending with a null character '\0'.
String operations in C:
- strlen()
- strcpy()
- strcat()
- strcmp()
Example:
Complete Data Structures Notes (Basic to Advanced) - in C
char str[20] = "Hello";
4. Linked Lists
A Linked List is a linear data structure with nodes containing data and a pointer to the next node.
Types:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Common operations include insertion, deletion, traversal, and searching.
Example Node in C:
struct Node {
int data;
struct Node* next;
};
5. Stacks
Stack is a LIFO (Last In First Out) structure.
Operations:
- push()
- pop()
- peek()
- isEmpty()
Implemented using arrays or linked lists.
Applications: Undo feature, Expression evaluation.
6. Queues
Queue is a FIFO (First In First Out) structure.
Operations:
Complete Data Structures Notes (Basic to Advanced) - in C
- enqueue()
- dequeue()
- isEmpty()
- isFull()
Types:
- Circular Queue
- Deque
- Priority Queue
7. Trees
Tree is a hierarchical structure.
Types:
- Binary Tree
- Binary Search Tree (BST)
Traversals:
- Inorder
- Preorder
- Postorder
Applications: Expression trees, Routing algorithms.
8. Heaps
A Heap is a complete binary tree.
Types:
- Min Heap
- Max Heap
Applications: Priority queues, Heap Sort
9. Graphs
Graph is a collection of nodes (vertices) connected by edges.
Representations:
Complete Data Structures Notes (Basic to Advanced) - in C
- Adjacency Matrix
- Adjacency List
Algorithms:
- BFS
- DFS
- Dijkstra's Algorithm
- Topological Sort
10. Hashing
Hashing is used for efficient data retrieval.
Techniques:
- Chaining
- Open Addressing
Applications: Hash Tables, Symbol Tables.
11. Tries
Trie is a tree-based data structure used for searching strings.
Applications:
- Auto-completion
- Dictionary management
12. Segment Trees / Fenwick Trees
Used for range queries and updates.
Applications: Range Sum, Range Minimum queries
13. Disjoint Set (Union-Find)
Used for grouping items into disjoint sets.
Operations:
- Find
- Union
Complete Data Structures Notes (Basic to Advanced) - in C
Applications: Kruskal's algorithm, Cycle detection
14. Time & Space Complexity
Important for analyzing algorithms.
- Time Complexity: Measures time (e.g., O(n), O(log n))
- Space Complexity: Measures memory usage.
Always aim for optimal complexity based on constraints.
