Page 1: Introduction to Data Structures
Definition:
A Data Structure is a method of organizing, managing, and storing data so that operations like
searching, insertion, deletion, and updates can be done efficiently.
Types of Data Structures:
1. Linear DS – Array, Linked List, Stack, Queue
2. Non-Linear DS – Tree, Graph
3. Hashing Structures
4. File Structures
Why Study DSA?
Efficient data management
Fast algorithm execution
Optimized real-world applications
Page 2: Arrays
Definition:
Array is a collection of similar data types stored in contiguous memory locations.
Operations:
Traversal
Insertion
Deletion
Searching
Sorting
Example (C Program):
#include<stdio.h>
int main() {
int a[5] = {10, 20, 30, 40, 50};
for(int i=0; i<5; i++)
printf("%d ", a[i]);
return 0;
}
Page 3: Linear Search & Binary Search
Linear Search
Time: O(n)
int linear(int a[], int n, int x) {
for(int i=0;i<n;i++)
if(a[i]==x) return i;
return -1;
}
Binary Search
Sorted array required
Time: O(log n)
int binary(int a[], int n, int x) {
int l=0, r=n-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==x) return m;
else if(x<a[m]) r=m-1;
else l=m+1;
}
return -1;
}
Page 4: Sorting Techniques
1. Bubble Sort
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)
if(a[j]>a[j+1]) swap(a[j], a[j+1]);
2. Selection Sort
for(int i=0;i<n;i++){
int min=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[min]) min=j;
swap(a[i], a[min]);
}
3. Insertion Sort
for(int i=1;i<n;i++){
int key=a[i], j=i-1;
while(j>=0 && a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
Page 5: Linked List (Singly Linked List)
Structure Definition
struct node {
int data;
struct node *next;
};
Insert at Beginning
void insertBeg(int x){
struct node *t = malloc(sizeof(struct node));
t->data = x;
t->next = head;
head = t;
}
Delete a Node
void delete(int x) {
struct node *t=head, *p=NULL;
while(t!=NULL && t->data!=x){
p=t;
t=t->next;
}
if(t==NULL) return;
if(p==NULL) head=head->next;
else p->next=t->next;
free(t);
}
Page 6: Doubly Linked List
Definition:
Each node has:
Previous pointer
Data
Next pointer
Node Structure
struct dnode {
int data;
struct dnode *prev, *next;
};
Used in: Browser history, undo–redo, multimedia playlists.
Page 7: Stack
Definition:
Stack follows LIFO (Last In First Out).
Operations: push(), pop(), peek()
Array Implementation
int stack[20], top = -1;
void push(int x){
stack[++top] = x;
}
int pop(){
return stack[top--];
}
Applications:
Expression evaluation
Function calls (recursion)
Undo operations
Page 8: Queue
Definition:
Queue follows FIFO (First In First Out).
Array Implementation
int q[20], f=0, r=-1;
void enqueue(int x){
q[++r] = x;
}
int dequeue(){
return q[f++];
}
Application:
CPU scheduling
Printer queues
Call center systems
Page 9: Circular Queue
Definition:
Improved queue that utilizes memory circularly.
Implementation
if((rear+1)%size == front) // Queue Full
Page 10: Trees
Definition:
Hierarchical non-linear data structure.
Binary Tree:
Each node has 0, 1 or 2 children.
Binary Search Tree (BST)
Left < Root < Right
Insert in BST
struct node* insert(struct node* root, int x){
if(root==NULL){
struct node* t = malloc(sizeof(struct node));
t->data=x; t->left=t->right=NULL;
return t;
}
if(x < root->data) root->left = insert(root->left, x);
else root->right = insert(root->right, x);
return root;
}
Page 11: Traversal of Tree
1. Inorder:
Left – Root – Right
2. Preorder:
Root – Left – Right
3. Postorder:
Left – Right – Root
void inorder(struct node *root){
if(root){
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
Page 12: Graphs
Definition:
A graph is a set of nodes (vertices) and edges.
Representation:
1. Adjacency Matrix
2. Adjacency List
Graph BFS
void bfs(int start){
[Link](start);
visited[start]=1;
}
Graph DFS
void dfs(int v){
visited[v]=1;
for(i=0;i<n;i++)
if(a[v][i]==1 && !visited[i])
dfs(i);
}
Page 13: Hashing
Definition:
Technique to map keys to index using a hash function.
Hash Function:
h(key) = key % size
Collision Handling:
1. Chaining
2. Linear Probing
3. Quadratic Probing
Page 14: Recursion
Definition:
Function calling itself.
Factorial Using Recursion
int fact(int n){
if(n==0) return 1;
return n * fact(n-1);
}
Fibonacci Using Recursion
int fib(int n){
if(n<=1) return n;
return fib(n-1)+fib(n-2);
}
Page 15: Conclusion & Viva Questions
Conclusion:
Data Structures and Algorithms help write optimized, efficient, and scalable programs.
Understanding DSA is essential for competitive exams, SEBI IT exams, placements, and
software development.
Important Viva Questions
1. What is the difference between array and linked list?
2. Why is stack called LIFO?
3. What is the time complexity of binary search?
4. Define recursion.
5. What are applications of trees?
6. What is hashing?