Introduction
A data structure is a specialized way of organizing and storing data so it can be used efficiently. In C programming, data structures are critical for building algorithms, managing memory, and solving real‑world problems like search engines, operating systems, and databases.
🔹 Categories of Data Structures
1. Primitive Data Structures
int → integers
float/double → decimal numbers
char → characters
Pointers → memory addresses
2. Non‑Primitive Data Structures
Linear → Arrays, Linked Lists, Stacks, Queues
Non‑Linear → Trees, Graphs
🔹 Arrays
An array is a fixed‑size collection of elements of the same type stored in contiguous memory.
Pros
Fast access using index.
Easy to implement.
Cons
Fixed size.
Insertion/deletion is costly.
Example: Sorting an Array
int main() {
int arr[5] = {5, 2, 9, 1, 3};
int i, j, temp;
for(i=0; i<5; i++) {
for(j=i+1; j<5; j++) {
if(arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for(i=0; i<5; i++) printf("%d ", arr[i]);
return 0;
}
🔹 Structures
A structure groups different data types under one name.
Example: Employee Record
int id;
char name[50];
float salary;
};
Use Cases
Student records
Employee databases
Product catalogs
🔹 Linked Lists
A linked list is a dynamic data structure where each node contains data and a pointer to the next node.
Types
Singly Linked List → one pointer (next).
Doubly Linked List → two pointers (next, prev).
Circular Linked List → last node points to first.
Pros
Dynamic size.
Efficient insertion/deletion.
Cons
Extra memory for pointers.
Slower access (must traverse).
🔹 Stack (LIFO)
A stack follows Last In, First Out.
Operations
Push → insert element
Pop → remove element
Peek → view top element
Applications
Undo/Redo in text editors
Expression evaluation
Function call management
🔹 Queue (FIFO)
A queue follows First In, First Out.
Types
Simple Queue
Circular Queue
Priority Queue
Double‑Ended Queue (Deque)
Applications
Printer job scheduling
Process management in OS
Customer service systems
🔹 Trees
A tree is a hierarchical structure with nodes.
Binary Search Tree (BST)
Left child < parent
Right child > parent
Advanced Trees
AVL Tree → self‑balancing BST
Heap → used in priority queues
Trie → used in dictionaries/search engines
🔹 Graphs
A graph is a set of vertices connected by edges.
Representations
Adjacency Matrix → 2D array
Adjacency List → linked list
Applications
Social networks (friends, followers)
Maps and GPS navigation
Network routing
🔹 Common Operations
Operation Example Traversal Visiting each element/node Insertion Adding new data Deletion Removing data Searching Finding data Sorting Bubble, Quick, Merge sort
🔹 Real‑World Applications
Arrays: Store marks of students.
Structures: Employee records.
Linked Lists: Dynamic memory allocation.
Stacks: Undo/Redo in editors.
Queues: Task scheduling in OS.
Trees: Database indexing, file systems.
Graphs: Social networks, maps, AI pathfinding.
🔹 Best Practices
Always free memory (
free()) to avoid leaks.Use the right data structure for the problem.
Keep code modular and well‑commented.
Test all operations thoroughly.
Conclusion
Data structures are the foundation of efficient programming. They help organize data, optimize performance, and solve complex problems.
By mastering arrays, structures, linked lists, stacks, queues, trees, and graphs, you’ll gain the skills to design scalable and high‑performance applications.
❓ Practice Questions with Answers
Q1: What are the differences between arrays and linked lists?
Answer:
Arrays have fixed size and contiguous memory; linked lists are dynamic and use pointers.
Arrays allow direct access using indices; linked lists require traversal.
Arrays waste memory if not fully used; linked lists use extra memory for pointers.
Q2: Explain stack and queue with real‑world examples.
Answer:
Stack (LIFO): Last In, First Out. Example → Undo/Redo in text editors, function call management.
Queue (FIFO): First In, First Out. Example → Printer job scheduling, customer service systems.
Q3: What is a binary search tree (BST)?
Answer: A BST is a tree where:
Left child < parent node.
Right child > parent node. It allows efficient searching, insertion, and deletion compared to linear structures.
Q4: What is the difference between linear and non‑linear data structures?
Answer:
Linear: Elements arranged sequentially (arrays, linked lists, stacks, queues).
Non‑linear: Hierarchical or networked arrangement (trees, graphs).
Q5: What is the difference between static and dynamic memory allocation in C?
Answer:
Static: Memory allocated at compile time (e.g., arrays).
Dynamic: Memory allocated at runtime using
malloc(),calloc(), and freed withfree().
Q6: What are the applications of graphs?
Answer:
Social networks (connections between users).
Maps and GPS navigation.
Network routing.
AI pathfinding in games.
Q7: How do you detect a cycle in a linked list?
Answer: Use Floyd’s Cycle Detection Algorithm (Tortoise and Hare):
Move one pointer one step, another two steps.
If they meet, a cycle exists.
Q8: What is hashing and why is it important?
Answer: Hashing maps data to a fixed‑size table using a hash function.
Used in searching, password storage, indexing.
Provides constant time complexity for search operations in ideal cases.
Q9: What is the difference between BFS and DFS in graphs?
Answer:
BFS (Breadth First Search): Explores level by level using a queue.
DFS (Depth First Search): Explores depth using a stack or recursion.
Q10: What is the difference between shallow copy and deep copy in structures?
Answer:
Shallow copy: Copies values but not dynamically allocated memory (pointers still reference the same memory).
Deep copy: Copies values and allocates new memory for pointers, ensuring independent copies.
