What is Data Structure ?

• Data Structure is the logical or the mathematical model of a particular organization of

data.
• It is a way in which the data is efficiently stored, processed & retrieved from computer
memory.
• Data Structure helps us to understand the relationship of one element with another and
how they are stored in memory

1
 Terms to remember

• Note : Data structure which are not directly understand by the machine but
can be implemented through primitive data structure are known as Non-
primitive
• Linear data structures
• Linear DS are those which can be expendable in 1D
• eg: array, link list
• Non-Linear data structure
• Non-linear DS are those which can be expendable in more than 1D
• eg: Trees, graph

2
 Various operations on Data Structure
1. Creation: Creating a new data structure
2. Traversing: visiting each and every element exactly ones
3. Searching
4. Insertion: inserting a new element in existing structure
5. Deletion: deleting an existing element
6. Merging : combining two data structure to form a single DS
7. Replacing:
8. Swapping: interchanging of position
9. Dropping : deletion of complete data structure
10. Hashing : use different function for searching

3
 Algorithm
•Algorithm: It is a collection of well-defined steps for solving a particular
problems.
• Time and space used by an algorithm are the two measures of the
efficiency of an algorithm.
• The complexity of an algorithm is the function which gives the running
time and space in terms of input size.

• Three cases of algorithm

• Best : minimum number of comparisons or min value of the function.
• Worst : maximum number of comparisons or max value of the function
• Average : expected value of the function

4
 Algorithm

• Approaches or methods for designing algorithm

• Top down
• Bottom up
• Divide and conquer
• Dynamic programming problem
• Greedy approach
• Randomization
• And many more ……..

5
 Array

• It is collection of homogeneous type of data elements, stored at

consecutive memory location.
• It is a linear data structure.
• The elements of an array are referred by their index.
• Length of array : UB- LB +1
• Syntax : // declaration of array
• data type array_name[size_of_array];
• int a[10];
• // the above statement is a request to compiler to allocate a
memory of size 20 bytes

6
 Array

Types of array

Multidimension
Linear Array array
(2-D i.e Matrix)

Length of Array : UB-LB +1

Location of element in array when base

address is given i.e Address of Kth element
= base address + w (k-LB)
Where w is width of DS

7
 Numerical on address calculation – 1 D array
• Base address : address of the first element of array.
• Address of Kth element = base address + w (k-LB)
• Elements Ist II IIIrd 4th 5th 6th 7th 8th
element element element

201,202, 203,204 205,206 207,2 209,2 211, 213,2 215,

08 10 212 14 216
• Base address
• Question : Find the address of 6th element
• Solution :
• Base address = 201
• Elements are integer type, so w=2
• Address of 6th element is =base + w (k-LB)
• = 201 + 2 (6-1)
• = 201 + 2 (5)
• = 211
8
 Numerical on address calculation- 1 D Array
• Base address : address of the first element of array.
• Address of K = base address + w (k-LB)
Ist element (1932) II element IIIrd element 1935 1936
• Elements (1933) 1934
2 2 2 203 204,205, 208 to 211 So on -------
0 0 0 206,207
• Address 0 1 2

• Question : Find the address of 1965

• Solution :
• Base address = 200
• Elements are floating type, so w=4
• Address of 1965 is =base + w (k-LB)
• = 200 + 4 (1965 – 1932)
• = 200 + 4 (33)
• = 332

9
 Creation & Traversing of array

• int a[10]; // is a request to the compiler to allocate a memory of 20

bytes
• // by using the above instruction we can create an array
• for(i = 1; i<=5; i++) // out of 10 places we are using on 5
• {
• scanf(“%d”, &a[i]); // providing values in array
• }
• // above process is known as creation of array.

• for(i=1;i<=5;i++)
• {
• printf(“%d”,a[i]); // visiting/ Reading/ printing of array , also known as
traversing operation.
• }
10
 Array

Searching in array

Linear Search Binary Search

11
 Linear Search

• Consider an unsorted array : 50 20 40 60 30

• a[5] => 1 2 3 4 5

• Let we want to search 60 in the above array

step Iteration no 1 Compare 60 with the first 60 50 Move to next element New i =2
1 i=1 element that is a[1] , i.e 50 i changes to i +1

step Iteration no 2 Compare 60 with the 60 20 Move to next element New i =3

2 i=2 second element i.e a[2], i.e i changes to i +1
20

step Iteration no 3 Compare 60 with the third 60 40 Move to next element New i =4
3 i=3 element i.e a[3], i.e 40 i changes to i +1

step Iteration no 4 Compare 60 with the fourth 60 = Element found at 4th Return i
4 i=4 element i.e a[4], i.e 60 60 position =4

The above example returns a positive value as the element is present in array
12
 Linear Search

• Consider an unsorted array : 50 20 40 60 30

• a[5] => 1 2 3 4 5

• Let we want to search 50 in the above array

step Iteration no 1 Compare 50 with the first 50 50 Element found at first Return
1 i=1 element that is a[1] , i.e 50 position i=1

The above example returns a positive value as the element is present in array

13
 Linear Search

• Consider an unsorted array : 50 20 40 60 30

• a[5] => 1 2 3 4 5
• Let we want to search 70 in the above array

step Iteration no 1 Compare 70 with the first 70 50 Move to next element New i =2
1 i=1 element that is a[1] , i.e 50 i changes to i +1

step Iteration no 2 Compare 70 with the 2nd 70 20 Move to next element New i =3
2 i=2 element i.e a[2], i.e 20 i changes to i +1

step Iteration no 3 Compare 70 with the third 70 40 Move to next element New i =4
3 i=3 element i.e a[3], i.e 40 i changes to i +1
step Iteration no 4 Compare 70 with the fourth 70 60 Move to next element New i =5
4 i=4 element i.e a[4], i.e 60 i changes to i +1

step Iteration no 4 Compare 70 with the fourth 70 30 Move to next element New i =6
5 i=5 element i.e a[5], i.e 30 i changes to i +1
Now i = 6 and total elements in array was 5, so above example will return
negative value
14
 Algorithm : Linear Search
Given : We are provided with an array, number of
• Algorithm LS (a, n, item) elements, and item
item is an element which we want to search in
• { // item is the element which we array
want to search in array a[], with n elements
• LOC = Null ; So lets assume a variable which contain the
position of item if it present in array , i.e. LOC
• for ( i =LB to UB) Initially the value of LOC is assumed as NULL => if
• { item found than we update LOC to some positive
value.
• if (item == a[i])
• { Now we check all elements, started from first
position to last
• LOC= i;
• Element found at location I; Compare item with all the elements of array
• Break; If element is found, than we update the value of
• } LOC
} And stop the procedure for searching, as we are
• If ( LOC = NULL) interested in only finding the very first element
which is equal to item
• {
• Element not in array If all the elements get exhausted => if LOC not
updated to any positive value
• } 50 20 40 60 30
• } 1 2 3 4 5

15
 Complexity :
Analysis of Linear Search
Is the number of comparison to found the item.
Case 1: Best Case
50 20 40 60 30
The element you want to search is at the first position
1 2 3 4 5
Hence number of comparison will ne 1
=> f(n) = 1
Implies complexity is (1)
Case 2 : Worst Case
The element you want to search is at the last position or not in the array.
In both the cases number of comparison will ne n
=> f(n) = n
Implies complexity is (n ) or O (n)
Case 3: Average Case
The probability to get an element is 1/n
f(n) = (number of comparison) * Probability of that number
f(n) = (1 * 1/n) + (2 * 1/n) + (3 * 1/n) + ----------- + (n * 1/n)
f(n) = 1/n {1 + 2 + 3 +--------+ n) = 1/n { n(n+1)/2} = (n+1)/2 so f(n) =???
f(n) = (n/2)

16
 • Animation for Linear Search

• http://cs.armstrong.edu/liang/animation/web/LinearSearchNew.html

17