Data Structures and

Algorithms

Pre requisite : Programming fundamentals, OOP

Designed by: Murku

Designed by: Murku
Data Structures

• Data Structures : A particular way of arranging data in computer

memory in such a way that it can be used effectively
• Eg : Array, Linked list, Queues etc.

Designed by: Murku

 Types of Data Structures
Data Structure

Primitive Non Primitive

Int Char Float Boolean Non

Linear
Linear

Linked
Array Queue Stack Trees Graphs
List
Designed by: Murku
Algorithms

• Algorithms : A well-defined and finite sequence of steps to solve a

specific class of problems.

• Benefits
• Language free
• Helps in Analysis
• Formulates formula to solve a particular type of problem

Designed by: Murku

Relation Between Data Structure
and Algorithms

• A Data structures needs set of algorithms to structure the data into memory.
• There are multiple operations that are needed to be performed on our data
structure i.e.

• Adding new Data Element

• Deleting a data Element
• Accessing data elements
• Searching a particular data element
• Sorting data elements

• Different algorithms are formed for above

Designed by: Murku Operations
Algorithm Analysis

Designed by: Murku

Algorithm Analysis
• Algorithm analysis helps analyzing time and resources required by an
algorithm.

• We always need a optimized method So it also helps compare two or

more algorithm of same class of problems.

• Algorithm Analysis is based on two criteria

• Time Analysis
• Memory Analysis

Designed by: Murku

Example 1 (space & time Analysis)
int a=5; int a=5;
int b=10; int b=10;

int temp=a; a=a+b;

a=b; b=b-a;
b=temp a=a-b;

Designed by: Murku

Example 2 (time Analysis)

for(i=0; i<n; i++) for(i=0; i<n; i++)

{ {
Statement 1 for(j=0;j<n;j++)
Statement 2 {
Statement 3 Statements
} }
}

Designed by: Murku

Asymptotic Notations
• Asymptotic notations are mathematical notations used to describe
time complexity of an algorithm
• There are three Asymptotic notations
• Big Oh (Upper bound)
• Omega (Lower bound)
• Theta (Average bound)

Designed by: Murku

Big Oh (Upper Bound)
• Big oh or upper bound of function f(n) is
Cg(n)
defined as f(n) = O(g(n)) f(n)

Given that 0 ≤ f(n) ≤ cg(n) and c,n>0

Designed by: Murku

Omega (Lower Bound)
• Omega or Lower bound of function f(n) is
f(n)
defined as f(n) = Ὡ(g(n)) Cg(n)

Given that 0 ≤ Cg(n) ≤ f(n) and c,n>0

Designed by: Murku

Theta (Average bound)
• Theta or Average bound of function f(n) is
C1g(n)
defined as f(n) = Ѳ(g(n)) f(n)
C2g(n)

Given that C1g(n) ≤ f(n) ≤ C2g(n) and

C1,C2,n>0

Designed by: Murku

Example

Designed by: Murku

Arrays

Designed by: Murku

Array
• It is a data structures that stores data elements in contiguous memory
locations
0 1 2 3 4 5 6

A B C D E F G

Designed by: Murku

Array Operations
• Accessing an Element
• Traversing whole Array
• Inserting new element
• Deleting Element
• Searching Element
• Sorting Array

Designed by: Murku

Accessing An Array Element
• Arr[4] gives us E

0 1 2 3 4 5 6

Arr A B C D E F G

Designed by: Murku

Traversing Array Elements

• Arr[i]

0 1 2 3 4 5 6

Arr A B C D E F G

Designed by: Murku

Traversing Array
Algorithm Program

Traverse(arr[], n)
1. Begin for( int i=0; i<n; i++)
2. Set i 0 {
3. if i = n then go to step 6 System.out.println(arr[i]);
4. Print array element on index i }
5. i=i+1 go to step 3
6. End
Designed by: Murku
Searching an element from array

• Two Methods
• Linear Search
• Binary Search

Designed by: Murku

Searching an array element(Linear
Search)
• Linear Search: suppose we want to search element ‘E’

0 1 2 3 4 5 6

Arr A B C D E F G

Arr[0]=‘E’ ? Arr[1]=‘E’ ? Arr[2]=‘E’ ? Arr[3]=‘E’ ? Arr[4]=‘E’ ?

Designed by: Murku
Searching an array element(Linear
Search)
Program
Algorithm
Linear_Search(int arr[],int n,int elem)
Linear_Search(arr[], n, elem) {
1. Begin int i=0;
for(i=0;i<n;i++)
2. Set i 0 {
3. If i = n go to step 7 If(arr[i]==elem)
4. If element in arr on index i is equal to break;
elem go to step 6 }
5. i=i+1 go to step 3 If(i=n)
System.out.println(“Array element not found”);
6. Print elem found on index i go to step 8
else
7. Print element not found System.out.println(“Element found on index”+i);
8. end }

Designed by: Murku

Searching an array element(Linear
Search)
• Analysis

Best Case : O(1)

Worst Case: O(n)

Average Case: O(n)

Designed by: Murku

 Searching an Array (Binary Search)
• Binary Search: Suppose we want to search Element ‘E’ S=0
E=6
Mid=(S+E)/2  3

0 1 2 3 4 5 6
S=Mid+1  4
E=6
Arr A B C D E F G Mid=(S+E)/2  5

S= 4
Arr[Mid]=‘E’ ? Arr[Mid]=‘E’ ? Arr[Mid]=‘E’ ? E=Mid-1  4
Mid=(S+E)/2  4
Arr[Mid]>‘E’? NO Arr[Mid]>‘E’? YES
Arr[Mid]<‘E’? YES Arr[Mid]<‘E’? NO

Designed by: Murku

Searching an Array (Binary Search)
• Algorithm • Program

Binary_Search(arr[],n,elem) Binary_Search(int arr[],int n,int elem)

1. Begin {
2. Set s  0 int s=0;
3. Set e  n int e=n;
4. Set mid (s+e)/2 int mid=(s+e)/2;
5. If mid < s go to step 11 while(!(mid<s)) {
6. If element at mid index is equal to elem go to step 10 if(arr[mid]==elem){
7. If element at mid > elem, set e  mid-1 System.out.println(“Element found on index”+mid);
8. If element at mid < elem, set s  mid+1 return; }
9. mid= (s+e)/2, go to step 5
else if(arr[mid]>elem)
10. Print element found on index mid go to step 12
s=mid+1;
11. Print element not found
else if(arr[mid]<elem)
12. End
e=mid-1;
mid=(s+e)/2; }
Designed by: Murku
System.out.println(“Element not found”);
Searching an Array (Binary Search)
• Analysis: Best Case : O(1)

Worst Case: O(log n)

Designed by: Murku

Inserting Array Element
• Three ways
• Maybe we want to always add element at end
• maybe we want to always add element to start
• maybe we want to always add element at user given location

Designed by: Murku

Inserting Array Element
• Adding element at the end
• Algorithm
Insert_End(arr[],n,max,elem)
1. Begin
2. if n=max then go to step 3 else go to step 4 Time Complexity: O(1)

3. Print Array is full, go to step 6

4. set n  n+1
5. set arr[n]  elem
6. end
Designed by: Murku
Inserting Array Element
• Adding element at the Start
• Algorithm
Insert_Start(arr[],n,max,elem)
1. Begin
2. if n=max then go to step 3 else go to step 4
3. Print Array is full, go to step 10
4. set n  n+1 Time Complexity: O(n)
5. set i  n
6. if i = 0 then go to step 9
7. set array at index i to array at index i-1
8. i=i-1 go to step 6
9. set array at index 0 to elem
10. end
Designed by: Murku
Inserting Array Element
• Adding element at the User given index
• Algorithm
Insert_UGI(arr[],n,max,elem,loc)
1. Begin
2. if n=max then go to step 3 else go to step 4
3. Print Array is full, go to step 10
4. set n  n+1 Time Complexity: O(n)
5. set i  n
6. if i = loc then go to step 9
7. set array at index i to array at index i-1
8. i=i-1 go to step 6
9. set array at index loc to elem
10. end
Designed by: Murku
Deleting Array Elements
• Three ways
• Maybe we want to always delete element at end
• maybe we want to always delete element to start
• maybe we want to always delete element at user given location

Designed by: Murku

Deleting Array Elements
• Deleting element at the end
• Algorithm
Delete_End(arr[],n,elem)
1. Begin
Time Complexity: O(1)
2. if n=0 then go to step 3 else go to step 4
3. Print Array is Empty , go to step 5
4. set n  n-1
5. end

Designed by: Murku

Deleting Array Elements
• Deleting element at the Start
• Algorithm
Delete_Start(arr[],n,elem)
1. Begin
2. if n=0 then go to step 3 else go to step 4
3. Print Array is Empty , go to step 9
Time Complexity: O(n)
4. Set i  0
5. If i = n go to step 9
6. Set element at index i to element at index i+1
7. i=i+1 go to step 5
8. set n  n-1
9. end
Designed by: Murku
Deleting Array Elements
• Deleting element at the user given location
• Algorithm
Delete_UGL(arr[],n,elem,loc)
1. Begin
2. if n=0 then go to step 3 else go to step 4
3. Print Array is Empty , go to step 9
Time Complexity: O(n)
4. Set i  loc
5. If i = n go to step 9
6. Set element at index i to element at index i+1
7. i=i+1 go to step 5
8. set n  n-1
9. end
Designed by: Murku
Sorting

Designed by: Murku

Sorting Array Element
• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort

Designed by: Murku

Selection Sort
• Demo on board • Algorithm
Selection_Sort(arr[],n)
1. Begin
2. Set i  0
3. If i = n then go to step 11
4. Set minloc  i
5. Set j  i+1
6. If j = n go to step 9
Time Complexity 7. If element in at index j is smaller then element at index minloc set minloc to j
Worst Case: O(N2) 8. j=j+1 go to step 6
9. Swap element at index i with element at index minloc
Average Case: O(N2) 10. i=i+1 go to step 3
Best Case: O(N2) 11. end

Designed by: Murku

Bubble Sort
• Demo on board
• Algorithm

Bubble_Sort(arr[],n)
1. Begin
2. Set i  0
3. If i = n then go to step 11
4. Set flag  0
5. Set j  0
6. If j < n-i go to step 9
Time Complexity 7. If element in at index j is greater then element at index j+1, then swap elements and set flag
Worst Case: O(N2) 1
8. J=j+1 go to step 6
Average Case: O(N2) 9. If flag = 0 go to step 11
Best Case: O(N) 10. i=i+1 go to step 3
11. end

Designed by: Murku

Insertion Sort
• Demo on Board • Algorithm

Insertion_Sort(arr[],n)
1. Begin
2. Set i  1
3. If i = n then go to step 11
4. Set temp  array element at ith index
5. Set j  i-1
Time Complexity 6. While j>=0 and array element at index j > temp repeat steps 7 and 8
Worst Case: O(N2) 7. Set array at index j+1to array element at index j
Average Case: O(N2) 8. j=j-1 go to step 6
9. Set array element at j+1 to temp
Best Case: O(N) 10. i=i+1 go to step 3
11. end

Designed by: Murku

 • Algorithm

Merge(arr[], s, mid, e)

Merge Sort 1.
2.
Begin
Set n1  mid-s+1
3. Set n2  e – mid
4. Set LA[] size to n1
5. Set RA[] size to n2
• Algorithm 6. Set i  0, set j  0
7. If i = n1 go to step 10
8. Set LA[i] to arr[s+i]
9. i=i+1 go to step 7
Merge_Sort(arr[],s,e) 10. If j=n2 go to step 13
1. Begin 11.
12.
Set RA[j] to arr[mid+1+j]
J=j+1 go to step 10
2. If s > e go to step 7 13. Set i,j  0 and k s
14. While i<n1 and j<n2 repeat steps 15 and 16
3. Set mid  (s+e)/2 15. If LA[i] < RA[j] then set arr[k] to LA[i] and increment i by 1,.. ELSE
set arr[k] to RA[j] and increment j by 1
4. Merge_Sort(arr[], s, mid) 16. k=k+1
17. While i < n1 repeat step 18
5. Merge_Sort(arr[], mid+1, e) 18. Set arr[k] to LA[i] and increment i and k by 1
6. Merge(arr[], s, mid, e) 19. While j < n2 repeat step 20
20. Set arr[k] to RA[j] and increment j and k by 1
7. end 21. end
Designed by: Murku
 • Algorithm
Quick sort
Partition(arr[], s, e)
• Algorithm 1. Begin
2. Set p  arr[s], set i s and j e
Quick_Sort(arr[], s, e) 3. While i < j repeat steps 4 to 8
1. Begin 4. Set i i+1
2. If s > e go to step 6 5. If arr[i] < p then go to step 4
3. Set j  Partition(arr[], s,e) 6. Set j j-1
4. Quick_Sort(s, j) 7. if arr[j] > p then go to step 6
5. Quick_Sort(j+1, e) 8. If i < j swap a[i] and a[j]
6. end 9. Swap arr[s] to arr[j]
10. Return j
Designed by: Murku
Count Sort
• Algorithm
Count_Sort(arr[],r,n)
1. Set i  0
2. Set count[] size to r+1
3. If i = n go to step 6
4. Count[arr[i]]++
Time Complexity 5. i = i+1 go to step 3
Worst Case: O(N+k) 6. Set i = 1
Average Case: O(N+K) 7. If j = r, go to step 10
Best Case: O(N+K) 8. Count[j]=count[j]+count[j-1]
9. j=j+1, go to step 7
10. Set k  0
11. If k = n go to step 15
12. Out[count[arr[k]]-1]=arr[k]
13. count[arr[k]]—
14. K++ go to step 11
15. end
Designed by: Murku
Radix Sort
• Algorithm
• Algorithm Count_Sort(arr[],d,n,r)
1. Set i  0
Radix_Sort(Arr[], n) 2. Set count[] size to r+1

1. Begin 3. If i = n go to step 6
4. Count[(arr[i]/d)%10]++
2. Find max element and assign to 5. i = i+1 go to step 3
max 6. Set i = 1
7. If j = r, go to step 10
3. Set d  1 8. Count[j]=count[j]+count[j-1]
9. j=j+1, go to step 7
4. If max/d > 0 go to step 7
10. Set k  0
5. Count_Sort(Arr[], d, n,r) 11. If k = n go to step 15
12. Out[count[(arr[k]/d)%10]-1]=arr[k]
6. d = d*10 go to step 4 13. count[(arr[k]/d)%10] - -
7. end 14. K++ go to step 11
15. end
Designed by: Murku
Queues

Designed by: Murku

Queue Operations
• Enqueue
• Dequeue
• Overflow
• Underflow
• Peek

Designed by: Murku

Queue

0 1 2 3 4 5 6

Arr A B C D E F G

Rear
Front

Designed by: Murku

Queue

0 1 2 3 4 5 6

Arr A B C D E F G

Front
Rear

Designed by: Murku

Stack

Designed by: Murku

Stack Operations
• Push
• Pop
• Overflow
• Underflow
• Peek

Designed by: Murku

Stack

0 1 2 3 4 5 6

Arr A B C D E F G

Top

Designed by: Murku

Stack

0 1 2 3 4 5 6

Arr A B C D E F G

Top

Designed by: Murku

Linked Lists

Designed by: Murku

Linked Lists

Head

Data Next Data Next Data Next Data Null

Designed by: Murku

Array V/s Linked Lists

Array Linked Lists

• Acquire contagious memory • Could work with non contagious
• Elements are not connected memory
• We can randomly access any • Elements are connected using
element pointers
• Insertion and deletion is hard • Random access is not possible
• Size must be specified • Insertion and deletion is easy
• Size can be increased and
decreased according to the need
Designed by: Murku
Types of Linked List
• Singly Linked List
• Doubly Linked List
• Circular Linked List
• Circular doubly Linked List

Designed by: Murku

Singly Linked List
• Operations
• Insertion
• Deletion
• Searching
• Updating

Head

Data Next Data Next Data Next Data Null

Designed by: Murku

Insertion
• At start
• At end
• At user given location

Designed by: Murku

Insertion
Inserting to the Linked List at start Algorithm
1. Insert_Start(data, next, head)
2. Set new-> data = data
3. Set new->next = null
Time Complexity: O(1)
4. If head == null then set head 
new and go to step 7
5. Set new->next = head
6. Head  new
7. end
Designed by: Murku
Insertion
Inserting to the Linked List at end Algorithm
1. Insert_end(data, next, head)
2. Set new-> data = data
3. Set new->next = null
4. If head == null then set head  new and
Time Complexity: O(n) go to step 9
5. Set point  head
6. While point-> next != null repeat step 7
7. Point  point->next
8. Point->next  new
9. end
Designed by: Murku
Insertion
Inserting to the Linked List at loc Algorithm
1. Insert_loc(data, next, head, loc)
2. Set new-> data = data
3. Set new->next = null
4. If head == null then set head  new and print “List
is empty adding element at start” go to step 7
5. Set point  head
Time Complexity: O(loc) 6. Set i 1
7. While i< loc-1 repeat step 8 and 9
8. Point  point->next
9. i  i+1
10. new->next  point.next
11. Point->next  new
12. end

Designed by: Murku

Deletion
Algorithm
• Deletion at start 1. Del_Start(data, next, head)
2. If head == null then Print list is
empty and go to step 4
3. Set head  head->next
4. end

Designed by: Murku

Deletion
Algorithm
Del_End(data, next, head)
• Deletion at end
1. If head == null then Print list is empty and
go to step 7
2. If head.next == null then set head  null
and go to step 7
3. Set SL  head and L  head.next
4. Repeat step 6 while L.next !=null
5. L  L.next and SL  SL.next
6. SL.next  null
7. end

Designed by: Murku

Deletion
Algorithm
Del_End(data, next, head, loc)
• Deletion at Given Loc
1. If head == null then Print list is empty and go to
step 9
2. If head.next == null then set head  null and go to
step 9
3. Set SL  head and L  head.next
4. Set i  1
5. Repeat step 6 and 7 while i < loc-1
6. L  L.next and SL  SL.next
7. I  i+1
8. SL.next  L.next
9. end

Designed by: Murku

Doubly Linked List

Head

null D1 N1 Head D2 N2 N1 D3 N3 N2 D4 null

Designed by: Murku

Insertion
Inserting to the Linked List at start Algorithm
1. Insert_Start(data, next,prev,head)
2. Set new-> data = data
3. Set new->next = null
Time Complexity: O(1) 4. Set new->prev=null
5. If head == null then set head 
new and go to step 7
6. Set new->next = head
7. end

Designed by: Murku

Insertion
Inserting to the Linked List at end Algorithm
1. Insert_end(data, next,prev,head)
2. Set new-> data = data
3. Set new->next = null
4. Set new -> prev=null
5. If head == null then set head  new and go to
Time Complexity: O(n) step 11
6. Set point  head
7. While point-> next != null repeat step 8
8. Point  point->next
9. Point->next  new
10. new.prev  point
11. end
Designed by: Murku
Insertion
Inserting to the Linked List at loc Algorithm
1. Insert_loc(data, next,prev, head, loc)
2. Set new-> data = data
3. Set new->next = null
4. If head == null then set head  new and print “List
is empty adding element at start” go to step 7
5. Set point  head
Time Complexity: O(loc) 6. Set i 1
7. While i< loc-1 repeat step 8 and 9
8. Point  point->next
9. i  i+1
10. new->next  point.next
11. Point->next  new
12. end

Designed by: Murku

Doubly Linked Listed
Deletion discussed in Lab, so is circular and doubly circular

Designed by: Murku

 Trees
Non Linear Data Structures

Designed by: Murku

Trees
5
Trees are non linear Data
structures which shows
hierarchical representations of 4 8
Data.

3 2 1 9

Designed by: Murku

Types of Trees
• General
• Binary

Designed by: Murku

Binary Tree
• Tree where each node is having at most 2 child
• Types
• Full Binary Tree
• Complete Binary Tree
• Perfect Binary Tree
• Balanced Binary Tree
• Degenerate Binary Tree

Designed by: Murku

Some Formulas
• Max number of Nodes = 2l-1

•Min Number of nodes = l+1

•At a level l Max num of nodes = 2l

Designed by: Murku

 Traversal
8
• In Order Traversal
• Pre Order Traversal
• Post Order Traversal 9 24

In Oder : 56,9,3,8,2,24,1

Pre Oder : 8,9,56,3,24,2,1 56 3 1

2
Post Oder : 56,3,9,2,1,24,8

Designed by: Murku

Binary Tree In Memory
5

9 24

56 3 2 1

Designed by: Murku

 Algorithms
• In Order Traversal • Pre Order Traversal • Post Order Traversal
1. In_Order(Root) 1. Pre_Order(Root) 1. Post_Order(Root)
2. Begin 2. Begin 2. Begin
3. In_Order(Root.Left) 3. Print “Root” 3. Pre_Order(Root.Left)
4. Pre_Order(Root.Left) 4. Pre_Order(Root.Right)
4. Print “Root”
5. Pre_Order(Root.Right) 5. Print “Root”
5. In_Order(Root.Right)
6. End 6. End
6. End

Designed by: Murku

Binary Search Trees
8

9 24

56

3
Designed by: Murku
Converting Simple Binary Tree To
Binary Search Tree
8
1. Perform In order traversal
store result in an array 9
24
In Oder : 56,9,3,8,2,24,1

2. Sort The output Array 56 3 2 1

In Oder : 1,2,3,8,9,24,56
8
3. Traverse The Tree again in In
order and replace elements
2
with output arrays 24

1 3 9 56
Designed by: Murku
Searching in BST
• Search(root,elem)
1. Begin
2. if root = null print element not found and go to step 6
3. if root.data = elem then print “Element Found” and go to step 6
4. if root.data < elem then call Search(root.left, elem)
5. If root.data > elem then call Search(root.right, elem)
6. end

Designed by: Murku

Insertion in BST
• Insert(Root,elem)
1. Begin
2. Set n.data = elem, n.left and n.right = null
3. If root = null set root  n and go to step 8
4. if elem < = root.data and root.left = null then set root.left  n and go to step 8
5. If elem > root.data and root.right = null then set root.right  n and go to step 8
6. If elem <= root.data then call Insert(root.left,elem)
7. If elem > root.data then call insert(root.right,elem)
8. end

Designed by: Murku

 • SearchLoc(elem,root)
1. Begin
2. Set Loc  root

Deletion in BST 3. While Loc.data != elem repeat step 4 and 5

4. If elem < Loc.data then prev  Loc and Loc 

• Delete(elem,root) Loc.left
1. Begin
2. searchLoc(elem,root) 5. If elem > Loc.data then Prev  Loc and Loc 
Loc.right

3. If Loc = null go to step 8 6. end

• SearchMin(Loc)
4. if Loc.left = null and Loc.right = null then if loc = prev.left set 1. Begin
prev.left  null and if loc = prev.right set prev.right  null
2. Set ptr  loc

5. If Loc.left = null and Loc.right != null then set prev.right  loc.right

3. While ptr.left != null repeat step 4

6. If Loc.right = null and Loc.left != null then set prev.left  loc.left

4. prev  ptr ,ptr  ptr.left

7. If Loc.left!= null and Loc.right != null then min

searchMin(Loc.right) and set loc.data = min 5. prev.left  null
8. end
6. Return ptr.data
Designed by: Murku
AVL Tree

Designed by: Murku