1. What is Data Structures?
/ Explain Elementary Data Structure
Data structure refers to the method of organizing, managing, and storing
data for efficient access and modification. It helps in processing data logically
and systematically.
Types of Data Structures:
1) **Linear Structures**:
- Arrays
- Linked Lists
- Stacks
- Queues
2) **Non-Linear Structures**:
- Trees
- Graphs
Elementary data structures: Arrays and Linked Lists are the basic structures
used to build complex structures.
2. Data Structure Operations
The common operations are:
1) **Traversing**: Visiting all elements
2) **Searching**: Finding an element
3) **Insertion**: Adding an element
4) **Deletion**: Removing an element
5) **Sorting**: Arranging in order
6) **Merging**: Combining data structures
3. Asymptotic Notations with Graph
Asymptotic notations describe the time complexity:
- **Big O (O)**: Worst case
- **Omega (Ω)**: Best case
- **Theta (θ)**: Average case
Graph: X-axis = Input size (n), Y-axis = Time. Different notations show growth
rate as n increases.
4. Arrays with its types
Array: Collection of similar data elements stored in contiguous memory.
**Types:**
1) One-Dimensional (1D)
2) Two-Dimensional (2D)
3) Multi-Dimensional
5. Traversing the Array
Traversing means accessing each element of the array exactly once, often
using loops (for, while).
6. Insertion and Deletion in Array
**Insertion:** Shift elements to create space, then insert.
**Deletion:** Remove element and shift remaining elements left.
7. Multi-Dimensional Array
An array with more than one index.
Eg: int a[3][4] – 3 rows, 4 columns.
Useful for matrix and table representation.
8. Sorting Techniques with Example
A) **Insertion Sort**:
Pick each element and insert in sorted part.
B) **Selection Sort**:
Select min and place at the start.
C) **Bubble Sort**:
Repeatedly swap adjacent elements if not in order.
9. Searching Algorithms with Example
A) **Linear Search**:
Check every element one by one.
B) **Binary Search**:
Efficient for sorted arrays. Divide and conquer method.
10. Representation of Singly Linked List in Memory
Each node contains:
1) Data
2) Pointer to next node
Nodes are stored non-contiguously in memory.
11. Traversing & Searching Singly Linked List
**Traverse:** Loop through nodes till NULL.
**Search:** Compare data of each node with key.
12. Garbage Collection & Insert/Delete in SLL
**Garbage Collection:** Automatic memory management (especially in high-
level languages).
**Insertion:** At head, tail, or position.
**Deletion:** Remove node and reconnect pointers.
13. Stack & Linked List Representation
**Stack:** LIFO (Last In First Out)
**Linked Stack:** Each node points to next; only top node is accessed.
14. Applications of Stack
1) Expression evaluation
2) Recursion handling
3) Undo operations
4) Balancing symbols
5) Function call stack
15. Recursion with Example
**Recursion:** Function calling itself.
**Example (Factorial):**
```c
int fact(int n) {
if(n<=1) return 1;
else return n*fact(n-1);
}
```
16. Queue & Types
**Queue:** FIFO structure.
Types:
1) Simple Queue
2) Circular Queue
3) Deque
4) Priority Queue
17. Queue Operations & Applications
**Operations:** Enqueue, Dequeue, Peek
**Applications:** OS scheduling, Printers, Buffers
18. Tree Terminologies
**Tree:** Hierarchical data structure.
Terms:
- Root
- Parent/Child
- Leaf
- Height
- Degree
19. Binary Tree with Example
**Binary Tree:** Max 2 children per node.
Example:
A
/\
B C
20. Tree Traversal Methods
1) **Inorder (LNR)**
2) **Preorder (NLR)**
3) **Postorder (LRN)**
Used to process tree data.
21. Graph with BFS and DFS
**Graph:** Collection of nodes and edges.
**BFS:** Level-wise (uses Queue)
**DFS:** Depth-wise (uses Stack/Recursion)