Data structures are fundamental concepts in computer science that allow us to store and organize data efficiently. They are essential for designing efficient algorithms and play a crucial role in software development. In this study note, we will explore various data structures as per the CBSE syllabus, breaking down each concept into digestible sections.
Data structures can be broadly categorized into two types: Linear and Non-Linear.
In linear data structures, elements are arranged sequentially. Each element is connected to its previous and next element. Examples include Arrays, Linked Lists, Stacks, and Queues.
An array is a collection of elements identified by index or key. It is a fixed-size data structure that stores elements of the same type.
int arr[5] = {1, 2, 3, 4, 5};
int x = arr[2]; // x = 3
Example
Suppose we need to store the marks of 5 students. An array can be used as follows:
int marks[5] = {85, 90, 78, 92, 88};
Common Mistake
A common mistake is trying to access an array index that is out of bounds, which can lead to undefined behavior.
A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (or link) to the next node in the sequence.
struct Node {
int data;
Node* next;
};
Tip
Use a dummy head node to simplify edge cases in linked list operations.
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can be added or removed only from one end, called the top.
std::stack
s; s.push(10); s.push(20); int x = s.top(); // x = 20 s.pop();
#### 1.4 Queues
A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front.
- **Basic Operations:**
- Enqueue: Add an element to the rear.
- Dequeue: Remove an element from the front.
- Front: Get the front element without removing it.
- **Example (C++):**
```cpp
std::queue
<int>
q;
q.push(10);
q.push(20);
int x = q.front(); // x = 10
q.pop();
Non-linear data structures do not store elements sequentially. Examples include Trees and Graphs.
A tree is a hierarchical data structure consisting of nodes, with a single node as the root and sub-nodes forming branches.
struct Node {
int data;
Node* left;
Node* right;
};
Example
Consider a binary tree with the following structure:
1
/ \
2 3
/ \
4 5
In-order traversal: 4, 2, 5, 1, 3
A graph is a collection of nodes (vertices) and edges connecting pairs of nodes. Graphs can be directed or undirected.
std::vector
adj[5]; // 5 vertices adj[0].push_back(1); adj[1].push_back(2); adj[2].push_back(3); adj[3].push_back(4);
<note>
Graphs are widely used in network routing, social networks, and more.
</note>
## Conclusion
Understanding data structures is crucial for efficient algorithm design and problem-solving in computer science. This study note covered the basics of linear and non-linear data structures, providing examples and tips to help you grasp the concepts better. Practice implementing these data structures to gain a deeper understanding and improve your coding skills.