MCS-021: Short Notes (Topic-wise)
1. Introduction to Data Structures
A data structure is a way of organizing and storing data such that it can be accessed and modified efficiently.
Types:
- Primitive: Integer, Float, Character, Pointer
- Non-Primitive: Linear (Array, Linked List, Stack, Queue), Non-Linear (Tree, Graph)
Operations: Traversal, Insertion, Deletion, Searching, Sorting, Merging
Abstract Data Type (ADT): Defines behavior of data structure independent of implementation.
2. Arrays and Strings
Array: A collection of homogeneous elements in contiguous memory.
Types: 1D, 2D, Multidimensional
Operations: Traversal, Insertion, Deletion, Searching, Sorting
Strings in C: Sequence of characters terminated by '\0'
Functions: strcpy, strlen, strcmp, strcat
3. Linked Lists
Linear structure of nodes where each node contains data and a pointer.
Types: Singly, Doubly, Circular
MCS-021: Short Notes (Topic-wise)
Advantages: Dynamic size, Efficient insertion/deletion
Operations: Creation, Insertion, Deletion, Traversal, Search
4. Stacks and Queues
Stack: LIFO structure. Operations - push, pop, peek
Queue: FIFO structure. Operations - enqueue, dequeue
Types of Queue: Simple, Circular, Deque, Priority
Implementation: Array and Linked List
Applications: Expression eval, CPU scheduling, BFS, Undo operation
5. Trees
Non-linear hierarchical data structure.
Terms: Root, Parent, Child, Leaf, Degree, Height, Subtree
Types: Binary, Full, Complete, BST, AVL, B-Trees
Traversal: Inorder, Preorder, Postorder, Level Order
Applications: Filesystem, Expression Tree, DB Indexing
6. Graphs
MCS-021: Short Notes (Topic-wise)
Set of vertices and edges.
Types: Directed, Undirected, Weighted, Unweighted, Cyclic, Acyclic, Connected
Representation: Adjacency Matrix, Adjacency List
Traversal: DFS (Stack), BFS (Queue)
Algorithms: Dijkstra, Prim, Kruskal, Topological Sort
Applications: Routing, Maps, Networks
7. Searching and Sorting
Searching: Linear (O(n)), Binary (O(log n))
Sorting:
- Bubble: O(n^2)
- Selection: O(n^2)
- Insertion: O(n^2)
- Merge: O(n log n)
- Quick: O(n log n) avg
- Heap: O(n log n)
Stable Sorts: Bubble, Insertion, Merge
8. File Handling and File Structures
File: Collection of related data on secondary storage.
MCS-021: Short Notes (Topic-wise)
C File Functions: fopen, fclose, fread, fwrite, fprintf, fscanf, fseek, ftell
Structures:
- Sequential
- Direct (Random Access)
- Indexed Sequential
Applications: Storage, Reporting, Data Management
9. Memory Management and Garbage Collection
Memory Types: Static (Stack), Dynamic (Heap)
C Functions: malloc, calloc, realloc, free
Fragmentation: Internal, External
Garbage Collection: Not in C. Used in Java, etc. Techniques include Mark & Sweep, Reference Counting
Importance: Prevent memory leaks, Ensure efficiency
