📘 Data Structures
2.1 Introduction to Data Structures
A Data Structure is a way of organizing, managing, and storing data so that it can be
used efficiently.
Different problems require different data organizations → choosing the right structure
improves performance.
👉 Data structures affect:
Speed of operations (insertion, deletion, searching).
Memory usage.
Scalability of algorithms.
Examples in real life:
Contact list on your phone (stored alphabetically = array).
Browser history (works like a stack).
Call queue in a call center (works like a queue).
Family tree (works like a tree).
Facebook friend network (works like a graph).
2.2 Arrays
Definition
An array is a collection of similar type elements, stored at contiguous memory
locations.
Each element is accessed using an index (starting from 0 in most languages).
Example
int Marks[5] = {85, 90, 72, 66, 95};
Marks[0] = 85
Marks[4] = 95
Solution:-
Index: 0 1 2 3 4
Value: 85 90 72 66 95
Advantages
1. Fast access using index (O(1)).
2. Simple to use.
3. Best for storing fixed-size data.
Disadvantages
1. Fixed size (cannot grow or shrink dynamically).
2. Insertion/deletion in middle is costly (shifting required).
3. Cannot store mixed data types.
Types
1. One-Dimensional Array (1-D)
o Linear list of data.
o Example: Student roll numbers [101, 102, 103, 104].
2. Two-Dimensional Array (2-D)
o Data stored in rows and columns (like a table/matrix).
o Example (Marks of 3 students in 3 subjects):
o [85 72 90]
o [60 75 80]
o [95 88 92]
👉 Real Life Example: Seating arrangement in a cinema hall = 2-D Array (rows × columns).
2.3 Linked Lists
Definition
A Linked List is a sequence of nodes, where each node contains:
o Data (value to store).
o Pointer/Reference (address of next node).
Eample Singly Linked List
Head → [10 | Next] → [20 | Next] → [30 | NULL]
Types
1. Singly Linked List
o Each node points only to the next node.
o Last node points to NULL.
2. Doubly Linked List
o Each node has two pointers: previous and next.
o Allows traversal in both directions.
o Example:
o NULL ← [10 | Prev | Next] ↔ [20 | Prev | Next] ↔ [30 | Prev |
Next] → NULL
3. Circular Linked List
o Last node points back to first node (forms a loop).
o Can be singly or doubly circular.
Advantages
Dynamic size (no need to predefine length).
Efficient insertion and deletion at any position.
Can store mixed types of data.
Disadvantages
Extra memory for pointers.
Accessing an element is slower (must traverse nodes).
👉 Real Life Example: Music playlist (songs connected one after another, looping back to first
song in case of repeat mode).
2.4 Stacks
Definition
Stack is a linear data structure that works on LIFO (Last In, First Out) principle.
The last element inserted is the first one removed.
Operations
1. Push(x) → Add element at the top.
2. Pop() → Remove element from the top.
3. Peek() → Show top element without removing.
4. IsEmpty() → Check if stack is empty.
5. IsFull() → Check if stack is full.
Stack example:-
Stack (Top → Bottom)
Top → [C]
[B]
[A]
Example
Push(A) → Push(B) → Push(C) → Stack = [A, B, C]
Pop() → removes C → Stack = [A, B]
Advantages
Simple and efficient for LIFO operations.
Used in recursive function calls.
Disadvantages
Cannot access middle elements directly.
Limited size if implemented using arrays.
👉 Real Life Example: Undo/Redo in MS Word, Browser Back Button.
2.5 Queues
Definition
Queue is a linear data structure that works on FIFO (First In, First Out) principle.
First element inserted is the first to be removed.
Operations
1. Enqueue(x) → Add at rear (back).
2. Dequeue() → Remove from front.
3. Front() → Get first element.
4. IsEmpty() → Check if queue is empty.
5. IsFull() → Check if queue is full.
Queue example:-
Front → [10] → [20] → [30] ← Rear
Advantages
Maintains order of processing.
Useful for scheduling and resource management.
Disadvantages
Slower random access (must dequeue to reach elements).
👉 Real Life Example: Print Queue, Customer Queue in a bank.
2.6 Graphs
Definition
Graph is a collection of nodes (vertices) connected by edges.
Types
1. Undirected Graph → Edges have no direction.
2. Directed Graph (Digraph) → Edges have direction.
3. Connected Graph → At least one path exists between every pair of nodes.
Graph:-
(1) —— (2)
| / |
| / |
(3) —— (4)
Advantages
Represents complex relationships.
Useful for shortest path, networking, and resource allocation.
Disadvantages
Can be memory-heavy (if graph is dense).
👉 Real Life Example:
Facebook (Users = nodes, Friendships = edges).
Google Maps (Cities = nodes, Roads = edges).
2.7 Trees
Definition
Tree is a hierarchical structure made of nodes connected by edges.
Top node = Root.
Connected nodes = Parent and Child.
Node without children = Leaf.
Example (Binary Tree)
[A] ← Root
/ \
[B] [C]
/ \
[D] [E]
Traversal Methods
1. In-order (Left → Root → Right).
2. Pre-order (Root → Left → Right).
3. Post-order (Left → Right → Root).
Advantages
Useful for hierarchical data (like directories).
Efficient searching (Binary Search Tree).
Disadvantages
Complex implementation compared to arrays.
Balancing required for efficiency.
👉 Real Life Example: File directory in operating systems, Family tree.
