Notes - Data Structure - Algorithm

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 65

Analysis of Algorithm

Define Algorithms

Algorithm is a stepwise set of instructions written to perform a specific task.

Describe/list/explain different approaches for designing an algorithm

Sr. Approach Explanation


No
.
1 Top-Down approach  A top-down design approach starts by dividing the complex
algorithm into one or more modules.
 These modules can further be decomposed into one or more sub-
modules, and this process of decomposition is iterated until the
desired level of module complexity is achieved.
 Top-down design method is a form of stepwise refinement where
we begin with the topmost module and incrementally add modules
that it calls
 Top-down approach is highly appreciated for ease in documenting
the modules, generation of test cases, implementation of code, and
debugging
 Criticized because sub-modules are analysed in isolation without
concentrating on their communication with other modules or on
reusability of components and little attention is paid to data,
thereby ignoring the concept of information hiding
2 Bottom-up approach  A bottom-up approach is just the reverse of top-down approach
 we start with designing the most basic or concrete modules and
then proceed towards designing higher level modules
 Sub-modules are grouped together to form a higher level module
 All the higher-level modules are clubbed together to form even
higher-level modules.
 This process is repeated until the design of the complete algorithm
is obtained.
 Allows information hiding as it first identifies what has to be
encapsulated within a module and then provides an abstract
interface to define the module’s boundaries as seen from the
clients
Algorithm analysis
How algorithm is analyzed?

 There are different ways of solving problem & there are different algorithms which can be designed
to solve a problem. Some algorithms may be more efficient than others.
 Analyzing an algorithm means determining the amount of resources (such as time and memory)
needed to execute it.

Define complexity & classify it


What is complexity of an algorithm? Describe time complexity and space complexity.

The complexity of an algorithm is a measure that describes its efficiency in terms of amount of time and
space required for an algorithm to process.

Classification (Define time complexity and space complexity):


Time complexity of algorithm: Consider three algorithms given below:-
is running time of a program as Algorithm A:- a=a+1
a function of input size. Algorithm B:- for x=1 to n step 1
a=a+1
loop
Algorithm C:- for x=1 to n step 1
for y=1 to n step 2
a=a+1
loop

For algorithm A: a=a+1 statement will execute only once.


For algorithm B: a=a+1 statement will be executed n times
For algorithm C: a=a+1 statement will be execute n 2 times

So time complexity of algorithm A is 1, B is n and C is n 2

Time complexity divided in to –


 Worst-case running time: This denotes the behavior of
an algorithm with respect to the worst possible case of the
input instance. For example, in sorting case, all input data
items given are in reverse order. It is is an upper bound on the
running time for any input.
 Best-case running time: The term ‘best-case
performance’ is used to analyze an algorithm under optimal
conditions. For example, the best case for a simple linear
search on an array occurs when the desired element is the first
in the list
 Average-case running time: The average-case running
time of an algorithm is an estimate of the running time for an
‘average’ input size.
Space complexity of algorithm: The space needed by the program is the sum of –
is amount of computer memory  Fixed space requirement - for storing instruction, variables,
required during program constants, structures etc.
execution as a function of input  Variable space requirement – it varies from program to
size program. It include dynamically allocated space during run
time, additional space required when function uses
recursion(stack) etc.

Time–Space Trade-off
Describe time and space trade off

The best algorithm is that one which require less memory space and take less time to complete its
execution. However, practically designing such algorithm might not be so easy.

There can be more than one algorithm to solve a particular problem. One may require less memory
space, while the other may require less CPU time to execute.

Therefore, if space is a big constraint, then one might choose a program that takes less space at the cost
of more CPU time. On the contrary, if time is a major constraint, then one might choose a program that
takes minimum time to execute at the cost of more space. This phenomenon is known as time – space
trade off.

Expressing time and space complexity


Expressed using a function f(n) where n is the input size for a given instance of the problem being
solved.
Complexity is required when –
 We want to predict complexity as input size grows
 Find more efficient algorithm

The most widely used notation to express this function f(n) is the Big O notation

Big O notation
Big O is a mathematical notation that represents complexity (time or space) of an algorithm. O stands
for order of term.

Big O specifically describes the worst-case scenario, and can be used to describe the execution time
required or the space used (e.g. in memory or on disk) by an algorithm

For example, if a sorting algorithm performs n 2 operations to sort just n elements, then complexity of
that algorithm would be O(n2)

Limitations of the Big ‘O’ notation


 Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it
is, as it does not consider the programming effort.
 It ignores important constants. For example, if one algorithm takes O(n 2) time to execute and the
other takes O(100000n2) time to execute, then as per Big O, both algorithm have equal time
complexity. In real-time systems, this may be a serious consideration
 There may not be sufficient information to calculate the behaviour of the algorithm in the average
case.
 Many algorithms are simply too hard to analyze mathematically

Searching
Define searching and give/enlist its type

It is the process of finding a data element in the given data structure.

Types:

1) Linear search (also called sequential search)


2) Binary search

Advantages of searching:
1) To check if data element exists
2) If data element exists, find position
3) Find no. of occurrences of data element to be searched
4) To locate data element in given data structure for further operations(update/delete etc)

Describe working of linear search with example


 In linear search, search element is compared with each element from the list in a sequence.
 Comparison starts with first element from the list and continues till element is found or comparison
reaches to the last element of the list.
 As each element is checked with search element, the process of searching requires more time.
 Time complexity of linear search is O (n) where n indicates number of elements in list.
 Linear search is mostly used to search an unordered list of elements

Example:
Linear search using array: On sorted array search takes place till element is found or comparison reaches
to last element of the list i.e. element not found.

Input list i.e. Array A[]= {10, 20, 30, 40, 50} and Search element 30, Index =0

We are searching for element 30. To search 30 the element 30 is compared with element at A[0] then
A[1] and so on until we find the target value or reach to the end of array. When item is found it displays
the location of an item else displays data element not found.

Iteration 1:
10 40 30 50 20
Index= 0 Index =1 Index =2 Index =3 Index =4

10!=30
index = index + 1

Iteration 2:
10 40 30 50 20
Index= 0 Index =1 Index =2 Index =3 Index =4
40!=30
index = index + 1

Iteration 3:
10 40 30 50 20
Index= 0 Index =1 Index =2 Index =3 Index =4
30=30 (Number found)
Position of 30 = Index + 1 = 3

Explain the linear search algorithm.


A = Array which stores the List of data
elements
N= Total Number of elements in list
VAL = Value to be searched in list

POS = position of element to be searched in


list

I = counter which will start with 1 and will


continue till I =N

 Step 1 & 2: Initialize POS=-1 and I =1


 Step 3: While loop is executed until I <=N
 Step 4: Check if match is found between
current array element and VAL
 If match found, position of array element
(POS=I) is printed and exit else value of I is
incremented
 If all elements of array are compared with
N and no match found i.e. POS=-1 then
this means that VAL is not present in array

Limitations:
Highly inefficient for large data

Complexity of Linear Search Algorithm

 (n) where n=no. of elements in array/linked list


 Time complexity: best case when element to be searched is first element
 Time complexity: worst case when element to be searched is last element of list or
not present in list
 The performance of the linear search algorithm can be improved by using a sorted array.
Linear search Program
Write a program to implement linear search for #include <stdio.h>
10 elements in an array. OR Write a program to #define size 10
search an element in an array. Display position of int main()
element. OR Write a program for linear search {
int arr[size],n, num,i,found=0;
printf("Enter number of elements in array\n");
scanf("%d",&n);
printf("Enter number to be searched in
array\n");
scanf("%d",&num);
printf("Enter the elements in array\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

for(i=1;i<n;i++) // or we can use while(i<=n)


and i++ in while loop
{
if(arr[i] == num)
{
printf("Element is present in array at
position %d",i+1);
found=1;
break;
}

}
if (found==0)
printf("Element does not exist in an
array\n");
return 0;
}

Consider the following array: 55 65 25 75 45 85 10. Write step wise procedure to find 45 using linear
search.

Step/Iteration 1 Compare element 45 with a [0].

Since, 45 is not equal to a[0],


compare next element
Step/Iteration 2 Compare element 45 with a[1].
Since, 45 is not equal to a[1],
compare next element

Step/Iteration 3 Compare element 45 with a[2].


Since, 45 is not equal to a[2],
compare next element

Step/Iteration 4 Compare element 45 with a[3].


Since, 45 is not equal to a[3],
compare next element

Step/Iteration 5 Compare element 45 with a[4].


Since, 45 is equal to a[4], we
can conclude that element 45 is
found and its position in list is 5
[4 + 1]

Binary search
Explain the working of Binary search with an example

 Binary search is performed only on sorted


array.
 Search method starts with calculating mid
position from an array and compare the
mid position element with the search
element.
 If a match is found then the search process
ends otherwise divide the input list into 2
parts. First part contains all the numbers
less than mid position element and second
part contains all the numbers greater than
mid position element.
 Then select one of the part depending on
search element is less or greater than mid
position element and calculate mid
position for selected part. Again compare
mid position element with search element.
 This process continues till either the input
value is found or the search condition
become false
 Example: give any one example like
mentioned below.

Find the position of element 29 using binary search method in an array ‘A’ given below : A = {11, 5, 21,
3, 29, 17, 2, 43}

 Binary search need array to be sorted first. Given array A is not sorted. So we need to sort the array
A first say in ascending order.
Sorted array A= { 2,3,5,11,17,21,29,43}
 Value to be searched VAL = 29

Binary search algorithm will proceed in following manner:


2 3 5 11 17 21 29 43
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

Iteration BEG END MID=BEG+END/ A[MID] Remark


2
1 0 7 3 11 VAL>A[MID] so search in second
half of the array now.
Change value of BEG now i.e.
BEG=MID+1 = 4
2 3 5 11 17 21 29 43
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
2 4 7 5 21 VAL>A[MID] so search in second
half of segment now. Change
value of BEG now i.e.
BEG=MID+1=6
17 21 29 43
A[4] A[5] A[6] A[7]
3 6 7 6 29 VAL=A[MID] so search successful
Element 29 found at index
position 6 means i.e. at position
= 6+1 =7 in a list
29 43
A[6] A[7]

Give stepwise procedure to search 65 in the following list: 23, 12, 5, 29, 10, 65, 55, 70
 Binary search need array to be sorted first. Given array A is not sorted. So we need to sort the array
A first say in ascending order.
Sorted array A= { 5,10,12,23,29,55,65,70}
 Value to be searched VAL = 65

Binary search algorithm will proceed in following manner:


5 10 12 23 29 55 65 70
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

Iteration BEG END MID=BEG+END/ A[MID] Remark


2
1 0 7 3 23 VAL>A[MID] so search in second
half of the array now.
Change value of BEG now i.e.
BEG=MID+1 = 4
5 10 12 23 29 55 65 70
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
2 4 7 5 55 VAL>A[MID] so search in second
half of segment now. Change
value of BEG now i.e.
BEG=MID+1=6
29 55 65 70
A[4] A[5] A[6] A[7]
3 6 7 6 65 VAL=A[MID] so search successful
Element 29 found at index
position 6 means i.e. at position
= 6+1 =7 in a list
65 70
A[6] A[7]

Find location of element ‘H’ by using binary search algorithm in the given list.
B F D A C E I G H J

 Binary search need array to be sorted first. Given array X is not sorted. So we need to sort the array
A first say in ascending order.
Sorted array X= { A,B,C,D,E,F,G,H,I,J}
 Value to be searched VAL = ‘H’

Binary search algorithm will proceed in following manner:


A B C D E F G H I J
X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] X[8] X[9]

Iteration BEG END MID=BEG+END/ X[MID] Remark


2
1 0 9 4 E ASCII VAL of char>A[MID] so
search in second half of the array
now.
Change value of BEG now i.e.
BEG=MID+1 = 5
A B C D E F G H I J
X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] X[8] X[9]
2 5 9 7 H VAL=A[MID] so search successful
Element ‘H’ is found at index
position 7 or at position 8th in a
list
F G H I J
X[5] X[6] X[7] X[8] X[9]

Differentiate/Distinguish between linear search (or sequential search) and binary search
Linear search Binary search
Element to be searched is compared with each Element to be searched is compared with mid
element of list element of list only
Given list can be sorted/Unsorted Given list must be in sorted order
Complexity is O(n) Complexity is O(log2n)
Easy to implement Comparatively difficult to implement
Requires sequential Access only. Requires random access to data elements in list
Efficient when search is required on less number Efficient when search is required on large number
of input elements of input elements
Slow when used to sort large list Faster when used to sort large list

Write a program for binary search

#include <stdio.h>

#define size 10

int main()

int arr[size],n, num,i,begin,end,mid,found=0;

printf("Enter number of elements in array\n");

scanf("%d",&n);

printf("Enter number to be searched in array\n");

scanf("%d",&num);

printf("Enter the elements in array\n");

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

scanf("%d",&arr[i]);

begin=0;

end=n-1;

while(begin<=end)

{
mid=(begin+end)/2;

if(arr[mid] == num)

printf("Element is present in array at position %d",mid+1);

found=1;

break;

else if(arr[mid]>num)

end = mid - 1;

else

begin = mid+1;

if (found==0 && begin>end)

printf("Element does not exist in an array\n");

return 0;

Hashing
Explain the concept of hashing and hash function
Definition

The process of mapping the key(data) to appropriate location(or index) in a hash table is called Hashing.

Hash table is a data structure in which keys are mapped to array positions(index) and array
position/index is calculated by a hash function.

In hash table element with key(k) is stored in hast table at index h(k). h() is hash function which take key
as input and generate index value at which key will be stored in hash table.

Hash function

 A hash function is a mathematical formula which, when applied to a key, produces an integer which
can be used as an index for the key in the hash table
 The main aim of a hash function is that elements should be relatively, randomly, and uniformly
distributed
 It produces a unique set of integers within some suitable range in order to reduce the number of
collisions
 In practice, there is no hash function that eliminates collisions completely. A good hash function can
only minimize the number of collisions by spreading the elements uniformly throughout the array
 Hash functions accelerate. table or database lookup

Methods of Hashing

 Division method
h(x) = x mod M i.e. x %M where M can be any prime number

int const M = 97; // a prime number


int h (int x) // Hash function
{
return (x % M);
}
 Multiplication method
Step 1: Choose a constant A such that 0 < A < 1.
Step 2: Multiply the key k by A.
Step 3: Extract the fractional part of kA.
Step 4: Multiply the result of Step 3 by the size of hash table (m). Hence, the hash function can
be given as: h(k) = [ m (kA mod 1)]

 Mid-square method
Step 1: Square the value of the key. That is, find k 2.
Step 2: Extract the middle r digits of the result obtained in Step 1.
e.g. k = 1234, k2 = 1522756, h (1234) = 27

 Folding method

Hash Table

Hash table is a data structure in which keys are mapped to array positions by a hash function. A value
stored in hash table can be searched using in O(1) [i.e. constant time irrespective of no. of data elements
in list] by using hash function which generate address from key (by producing index of array where the
key value is stored)

Collision

Collisions occur when the hash function maps two different keys to the same location. Obviously, two
records cannot be stored in the same location. Therefore different Collision Resolution Techniques used
for resolving or handling the collision.

Collision Resolution Techniques:

 Open Addressing
o Linear probing
o Quadratic probing
o Double hashing
 Chaining – store keys having same hash value as linked list as shown below.

Advantage or significance of Hashing

 With hashing, no extra space is required to store the index as in the case of other data
structures like database.
 Hash table provides fast data access(or search) hence fast data retrieval or fats data updates.
Applications of Hashing

 Quickly search and retrieve information in database . Some database systems store separate index
file and data file. When data is to be searched, first it is searched in index file which give exact
location of data in data file.
 Hashing is used in Internet search engines like google

Sorting
Define sorting & give its types

Definition Categories/Classification of sorting


Sorting means arranging the elements of any  Internal sorting: deals with sorting the data
collection/list in either ascending or descending stored in the computer’s memory
order  External sorting: deals with sorting the data
stored in files. External sorting is applied
when there is large data which can not be
stored in the memory.
Sorting types/Techniques
 Bubble sort
 Selection sort
 Insertion sort
 Quick sort
 Merge sort
 Radix sort
 Shell sort

Internal sorting

The list of records can be either stored in a contiguous and randomly accessible data structure (array) or
may be stored in a dispersed and only sequentially accessible data structure like a linked list. But the
logic to sort the records will be same and only the implementation details will differ.

External sorting

Let us consider we need to sort 700 MB of data using only 100 MB of RAM

 Step 1: Read 100 MB of the data in RAM


and sort this data using any conventional
sorting algorithm like quick sort.
 Step 2: Write the sorted data back to the
magnetic disk.
 Step 3: Repeat Steps 1 and 2 until all the
data (in 100 MB chunks) is sorted.
 All these seven chunks that are sorted
need to be merged into one single output
file.
Sorting algorithm performance is analyzed on following:

 Number of data comparisons performed


 Number of time data is moved
 Best case performance
 Worst case performance
 Average case performance
 Stability – same result on different data set

Bubble sort
Principal of bubble sort

This method sorts the elements by repetitively moving largest element to highest index position of
array/linked list segment(in case sorting elements in ascending order)

Consecutive adjacent pairs of data element are compared. If element of lower index is greater than
element of higher index , two elements are interchanged (in case of sorting in ascending order) so that
largest element is pushed to higher index position. This process continues till entire list is sorted.

This procedure of sorting is called bubble sorting because elements ‘bubble’ to the top of the list.

Note: If elements need to sorted in descending order then smallest number need to be moved to
highest index position in list segment.

Complexity of Bubble sort: O(n2)

Algorithm

 The outer loop is for the total number of


passes which is N–1 where N=Number of
element in list
 The inner loop will be executed for every
Iteration/pass. However, the frequency of
the inner loop will decrease with every pass
because after every pass, one element will be
in its correct position
 Therefore, for every pass, the inner loop will
be executed N–I times, where I is iteration
count

Describe working of bubble sort with example

Example

Perform bubble sort on following data to sort all elements in ascending order.

15, 10, 02, 35, 08 (show all steps)


Pass 1: Pass 3
a) Compare 15 & 10. Since 15>10 do a) Compare 2 & 10. Since 2<10 no swapping
swapping done
10, 15,02,35,08 02, 10, 08, 15, 35
b) Compare 15 & 02. Since 15>2 do b) Compare 10 & 8. Since 10>08 do
swapping swapping
10, 02,15, 35,08 02, 08, 10, 15, 35
c) Compare 15 & 35. Since 15<35 no Pass 4
swapping done a) Compare 2 & 08. Since 2<08 no swapping
10, 02,15, 35,08 done
d) Compare 35 & 08. Since 35>8 do 02, 08, 10, 15, 35
swapping
10, 02,15, 08, 35 Final sorted list in ascending order is:
Pass 2 02, 08, 10, 15, 35
a) Compare 10 & 02. Since 10>2 do
swapping
02, 10, 15, 08, 35
b) Compare 10 & 15. Since 10<15 no
swapping done
02, 10, 15, 08, 35
c) Compare 15 & 8. Since 15>8 do
swapping
02, 10, 08, 15, 35

Program

Write a program for sorting the array of #include <stdio.h>


10/N elements using the Bubble sort #define size 10
method int main()
{
int arr[size],n, num,i,j,temp,flag=0;
printf("Enter number of elements in array\n");
scanf("%d",&n);
printf("Enter the elements in array\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

for(i=0;i<n;i++)
{
printf("Pass %d\n",i);
for (j=0;j<n-1-i;j++)
{
if (arr[j]>arr[j+1])
{
flag=1;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if (flag==0)
{
printf("Array is already sorted\n");
break;
}
}

Selection sort
Describe working of selection sort method with suitable example

Working principal

First find the smallest value in the list and place it in the first position. Then, find the second smallest
value in the array and place it in the second position. Repeat this procedure until the entire list is sorted.

If list is stored in an array –

 In pass 1, find position POS of smallest value in array and then swap ARR[POS] with ARR[0]. To find
smallest value in array, ARR[0] is compared with all remaining elements of array.
 In pass 2, find position POS of smallest value in sub-array of N-1 elements now[excluding first
element which is already sorted in pass1]. To find smallest value in sub-array, ARR[1] is compared
with all remaining elements of array.
 The above process is repeated (till pass N-1) till entire list is sorted

Algorithm
SELECTION SORT(ARR, N) During the Ith pass, we need to find the position
Step 1: Repeat Steps 2 and 3 for I = 1
to N-1 POS of the smallest elements from ARR[I],
Step 2: CALL SMALLEST(ARR, I, N, POS) ARR[I+1], ..., ARR[N].
Step 3: SWAP A[I] with ARR[POS]
[END OF LOOP]
Step 4: EXIT To find the smallest element, we use a variable
SMALLEST (ARR, K, N, POS)
SMALL to hold the smallest value in the sub-array
Step 1: [INITIALIZE] SET SMALL = ARR[I] ranging from ARR[I] to ARR[N]. Then, swap ARR[I]
Step 2: [INITIALIZE] SET POS = I
Step 3: Repeat for J = I+1 to N
with ARR[POS].
IF SMALL > ARR[J]
SET SMALL = ARR[J] This procedure is repeated until all the
SET POS = J
[END OF IF] elements in the array are sorted.
[END OF LOOP]
Step 4: RETURN POS

Describe working of selection sort method with suitable example.


Sort given input list in ascending order using selection sort input list: 55, 25, 5, 15, 35

Complexity of Selection sort: O(n2)


Advantages of selection sort:

 It is 60% more efficient than bubble sort


 Simple and easy to implement.
 Can be used for small data set sorting

Insertion sort
Working principal

Describe working of inserting sort. Demonstrate working of insertion sort algorithm to sort 6
elements.

One element is sorted at a time to its final position. We usually use it for ordering a deck of cards while
playing bridge.

Assume list is stored in array –


 The array of values to be sorted is divided into two sets. One that stores sorted values and another
that contains unsorted values.
 The sorting algorithm will proceed until there are elements in the unsorted set.
 Suppose there are n elements in the array. Initially, the element with index 0 (assuming LB =0) is in
the sorted set. Rest of the elements are in the unsorted set.
 The first element of the unsorted partition has array index 1 (if LB = 0).
 During each iteration of the algorithm, the first element in the unsorted set is picked up and
inserted into the correct position in the sorted set.

Example
Write an algorithm for insertion sort and arrange given numbers in ascending order using insertion sort:
– Summer 2019 Also find total number of comparison made
9, 15, 5, 20, 10
Total no. of comparisons = 10 [calculate above steps and write down)

Arrange given numbers in ascending order using insertion algorithm.

39 9 45 63 18 81 108 54 72 36
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

Pass 1: Pass6:
9 39 45 63 18 81 108 54 72 36 9 18 39 45 63 81 108 54 72 36
A[1] is compared with A[0]. As A[1]<A[0] they are A[6] is compared with all previous elements from
interchanged A[0] to A[5] and no interchange is required as it is
greater than all of them.
Pass2: Pass7:
9 39 45 63 18 81 108 54 72 36 9 18 39 45 54 63 81 10 72 36
A[2] is compared with both A[0] & A[1] and as it 8
is greater than both its position is as it is and no A[7] is compared with all previous elements from
interchange required A[0] to A[6]. A[7] is less than A[4] so it is inserted
before A[4]
Pass3: Pass8:
9 39 45 63 18 81 108 54 72 36 9 18 39 45 54 63 72 81 10 36
A[3] is compared with A[0], A[1] & A[2] and as it 8
is greater than all, no interchange required A[8] is compared with all previous elements from
A[0] to A[7]. A[8] is less than A[6] so it is inserted
before A[6]
Pass4: Pass9: (Sorted)
9 18 39 45 63 81 108 54 72 36 9 18 36 39 45 54 63 72 81 108
A[4] is compared with all previous elements from A[9] is compared with all previous elements from
A[0] to A[3]. As A[4]<A[1] so A[4] is inserted A[0] to A[8]. A[9] is less than A[2] so it is inserted
before A[1] before A[2]
Pass5:
9 18 39 45 63 81 108 54 72 36
A[5] is compared with all previous elements from
A[0] to A[4] and no interchange is required as it is
greater than all of them.
Note: Data elements highlighted in blue color are unsorted in each pass.

Complexity of Insertion sort: O(n2)

Advantages of Insertion sort:

 It performs better than bubble(twice faster) and selection sort(40% faster)


 Easy to implement and generally used to sort small set of data

Comparison of Algorithms
Algorithm Average case Worst case
Bubble sort O(n2) O(n2)
Selection sort O(n2) O(n2)
Insertion sort O(n2) O(n2)
Merge sort O(n log n) O(n log n)

Stack
Define Stack OR Stack is linear data structure. Yes/No? Justify your answer

A stack is a linear data structure in which data may be inserted/deleted from one end only (which is
called top of stack). It is also referred to as LIFO (Last input First Output).

Stack can be implemented using linear data structures like Array or Linked list, which stores data in
particular sequence.

Memory representation of stack using an array

Consider stack contains five integer


elements represented with an array A in
which each element occupy 2 bytes
memory. Array starts with base address of
2000.

Infix to Postfix conversion


Convert following expression into postfix form. Covert the following infix expression into a
Give stepwise procedure. A+B↑C*(D/E)-F/G. -- postfix expression and show details of stack at
Winter 2018 each step of conversion.
Consider input expression as (A+B↑C*(D/E)-F/G) Expression: ((A + B) * D) ∧ (E – F)
Infix Stack Postfix expression Consider input expression as
characte (((A + B) * D) ∧ (E – F))
r Infix Stack Postfix expression
scanned characte
( ( r
A ( A scanned
+ (+ A ( (
B (+ AB ( ((
↑ (+↑ AB ( (((
C (+↑ ABC A ((( A
* (+* ABC↑ + (((+ A
( (+*( ABC↑ B (((+ AB
D (+*( ABC↑D ) (( AB+
/ (+*(/ ABC↑D * ((* AB+
E (+*(/ ABC↑DE D ((* AB+D
) (+* ABC↑DE/ ) ( AB+D*
- (- ABC↑DE/*+ ^ (^ AB+D*
F (- ABC↑DE/*+F ( (^( AB+D*
/ (- / ABC↑DE/*+F E (^( AB+D*E
G (- / ABC↑DE/*+FG - (^(- AB+D*E
) Empty ABC↑DE/*+FG/- F (^(- AB+D*EF
) (^ AB+D*EF-
Postfix expression= ABC↑DE/*+FG/- ) Empty AB+D*EF-^

Postfix expression= AB+D*EF-^


Convert given infix expression to postfix Convert following infix expression into a postfix
expression using stack – 8 Marks expression. Show all steps.
(A + B) *D + E/(F + A *D) + C (P + (Q*R – (S/T^U)*V)*W) – Summer 2018 – 8
Consider input expression as ((A + B) *D + E/(F + Marks
A *D) + C)
Infix Stack Postfix expression
Infix Stack Postfix expression characte
characte r
r scanned
scanned ( (
( ( P ( P
( (( + (+ P
A (( A ( (+( P
+ ((+ A Q (+( PQ
B ((+ AB * (+(* PQ
) ( AB+ R (+(* PQR
* (* AB+ - (+(- PQR*
D (* AB+D ( (+(-( PQR*
+ (+ AB+D* S (+(-( PQR*S
E (+ AB+D*E / (+(-(/ PQR*S
/ (+/ AB+D*E T (+(-(/ PQR*ST
( (+/( AB+D*E ^ (+(-(/^ PQR*ST
F (+/( AB+D*EF U (+(-(/^ PQR*STU
+ (+/(+ AB+D*EF ) (+(- PQR*STU^/
A (+/(+ AB+D*EFA * (+(-* PQR*STU^/
* (+/(+* AB+D*EFA V (+(-* PQR*STU^/V
D (+/(+* AB+D*EFAD ) (+ PQR*STU^/V*-
) (+/ AB+D*EFAD*+ * (+* PQR*STU^/V*-
+ (+ AB+D*EFAD*+/+ W (+* PQR*STU^/V*-W
C (+ AB+D*EFAD*+/+C ) Empty PQR*STU^/V*-W*+
) Empty AB+D*EFAD*+/+C+
Postfix Expression for Given Equation is:
PQR*STU^/V*-W*+
Convert the given infix expression to postfix Convert following expression into postfix form
expression using stack and the details of stock at with illustration of all stages. – Summer 2017
each step of conversion. – Winter 2016 A + B ^C * (D/E) – F % G
P * Q ↑R – S/T + [U/V]
Consider input expression as:
Consider input expression as (P * Q ↑R – S/T + (A + B ^C * (D/E) – F % G)
[U/V])
Infix Stack Postfix expression
Infix Stack Postfix expression characte
characte r
r scanned
scanned ( (
( ( A ( A
P ( P + (+ A
* (* P B (+ AB
Q (* PQ ^ (+^ AB
↑ (*↑ PQ C (+^ ABC
R (*↑ PQR * (+* ABC^
- (- PQR↑* ( (+*( ABC^
S (- PQR↑*S D (+*( ABC^D
/ (-/ PQR↑*S / (+*(/ ABC^D
T (-/ PQR↑*ST E (+*(/ ABC^DE
+ (+ PQR↑*ST/- ) (+* ABC^DE/
[ (+[ PQR↑*ST/- - (- ABC^DE/*+
U (+[ PQR↑*ST/-U F (- ABC^DE/*+F
/ (+[/ PQR↑*ST/-U % (-% ABC^DE/*+F
V (+[/ PQR↑*ST/-UV G (-% ABC^DE/*+FG
] (+ PQR↑*ST/-UV/ ) Empty ABC^DE/*+FG%-
) Empty PQR↑*ST/-UV/+
Postfix Expression for Given Equation is:
Postfix Expression for Given Equation is: ABC^DE/*+FG%-
PQR↑*ST/-UV/+
Evaluate postfix expression

Evaluate the following postfix expression : -- Evaluate the following postfix expression :
5, 6, 2, +, *, 12, 4, /, – 5 7 + 6 2 – * -- 6 Marks – Summer 2019 (I Scheme)
Show diagrammatically each step of evolution using
stack. 4 Marks – Summer 2019 (I Scheme) Charact Operan Operan Value Stack
OR er d1 d2
 Convert the following arithmetic expression P written scanned
in postfix notation into infix. – Summer 2015 – 4 5 5
Marks 7 5,7
P : 5, 6, 2, +, *, 12, 4, /, – also evaluate P for final value + 5 7 5+7=12 12
Characte Operand Operand Value Stack 6 12,6
r scanned 1 2 2 12,6,
5 5 2
6 5,6 - 6 2 6-2=4 12,4
2 5,6,2 * 12 4 12*4=4 48
+ 6 2 6+2=8 5,8 8
* 5 8 5*8=40 40
12 40,12 Result of above postfix expression evaluation is 48
4 40,12,4
/ 12 4 12/4=3 40,3
- 40 3 40- 37
3=37
Infix Expression = 5 *(6+2) -(12/4) Note: You can give
different variable name to each value
above[A=5,B=6,C=2,D=12,E=4] and then do above stack
operations then we will get similar type of equation as
shown below e.g. A*(B + C) –(D/E)
.
Result of above postfix expression evaluation is 37
Consider the following arithmetic expression written in Find out infix equivalent of the following postfix expression.
postfix notation : – Winter 2014 – 4 Marks
10, 2, *, 15, 3, /, +, 12, 3, 2, ↑, +, +. Evaluate this (i) AB + C * D –
expression to find its value – Winter 2015 – 8 Marks (ii) ABC * + D –
Characte Operand Operand Value Stack
r scanned 1 2 i) AB + C * D –
10 10 Characte Operand Operan Value Stack
2 10,2 r scanned 1 d2
* 10 2 10*2=20 20 A A
15 20,15 B A,B
3 20,15,3 + A B A+B (A+B)
/ 15 3 15/3=5 20,5 C (A+B),C
+ 20 5 20+5=25 25 * (A+B) C (A+B)*C (A+B)*C
12 25,12 D (A+B)*C,D
3 25,12,3 - ((A+B)*C) D ((A+B)*C)- ((A+B)*C)-
2 25,12,3,2 D D
↑ 3 2 3↑2=9 25,12,9
+ 12 9 12+9=21 25,21 ii) ABC * + D –
+ 25 21 25+21=46 46 Characte Operand Operan Value Stack
r scanned 1 d2
Result of above postfix expression evaluation is 46 A A
B A,B
C A,B,C
* B C B+C A,(B*C)
+ A (B*C) A+(B*C) A+(B*C)
D A+(B*C),D
- A+(B*C) D A+(B*C)- A+(B*C)-D
D

Infix to Prefix conversion

Algorithm:

OR

Note: we will use first algorithm as it is simple and we can reuse postfix logic and has to remember
that only

Convert the following infix expression to its prefix Find prefix equivalent of following expressions: –
form using stack - 2 Marks Summer 2019 (I Summer 2019 – 4 Marks
Scheme) i) [(A + B) + C] * D
A+B–C*D/E+F ii) A + [(B * C) + D]
Let’s consider input expression as –
(A + B – C * D / E + F) 1) Let’s consider expression as ([(A + B) + C]
* D)
Step 1: Reverse the infix string with interchange Step 1: Reverse the infix string with interchange
of left & right parentheses of left & right parentheses
(F+E/D*C-B+A) (D*[C+(B+A)])
Step 2: Obtain postfix expression for expression Step 2: Obtain postfix expression for expression
in step 1 i.e. (F+E/D*C-B+A) in step 1 i.e. (D*[C+(B+A)])
Infix Stack Postfix expression Infix Stack Postfix expression
characte characte
r r
scanned scanned
( ( ( (
F ( F D ( D
+ (+ F * (* D
E (+ FE [ (*[ D
/ (+/ FE C (*[ DC
D (+/ FED + (*[+ DC
* (+* FED/ ( (*[+( DC
C (+* FED/C B (*[+( DCB
- (- FED/C*+ + (*[+(+ DCB
B (- FED/C*+B A (*[+(+ DCBA
+ (+ FED/C*+B- ) (*[+ DCBA+
A (+ FED/C*+B-A ] (* DCBA++
) Empty FED/C*+B-A+ ) Empty DCBA++*

Step 3: Reverse the postfix expression to get Step 3: Reverse the postfix expression to get
prefix expression prefix expression
+A-B+*C/DEF *++ABCD

2) Let’s consider input expression as (A +


Convert infix expression into prefix expression: [(B * C) + D])
(A+B)*(C/G)+F -- Winter 2018 - I scheme- 2 Step 1: Reverse the infix string with interchange
Marks of left & right parentheses
([D+(C*B)]+A)
Let’s consider input expression as – Step 2: Obtain postfix expression for expression
((A+B)*(C/G)+F) in step 1 i.e. ([D+(C*B)])

Step 1: Reverse the infix string with interchange Infix Stack Postfix expression
of left & right parentheses characte
(F+(G/C)*(B+A)) r
Step 2: Obtain postfix expression for expression scanned
in step 1 i.e. (F+(G/C)*(B+A)) ( (
[ ([
Infix Stack Postfix expression D ([ D
characte + ([+ D
r ( ([+( D
scanned C ([+( DC
( ( * ([+(* DC
F ( F B ([+(* DCB
+ (+ F ) ([+ DCB*
( (+( F ] ( DCB*+
G (+( FG + (+ DCB*+
/ (+(/ FG A (+ DCB*+A
C (+(/ FGC ) Empty DCB*+A+
) (+ FGC/
* (+* FGC/ Step 3: Reverse the postfix expression to get
( (+*( FGC/ prefix expression
B (+*( FGC/B +A+*BCD
+ (+*(+ FGC/B
A (+*(+ FGC/BA
) (+* FGC/BA+
) Empty FGC/BA+*+

Step 3: Reverse the postfix expression to get


prefix expression
+*+AB/CGF

Translate the following infix expression to its Evaluate the following prefix expression: – * + 4 3
equivalent prefix expression. 2 5 show diagrammatically each step of evaluation
(x + y) * (p-q) using stack. -- 4 Marks – Summer 2019 (I Scheme)
Also evaluate above prefix expression with
following values: x = 2, y=3, p=6, q=2 To evaluate simply reverse the prefix expression
– Summer 2016 – 8 Marks with values above and then evaluate in same way
as we evaluate postfix expression
Let’s consider input expression as – 5234+*-
((x + y) * (p-q))
Charact Operan Operan Value Stack
Step 1: Reverse the infix string with interchange er d1 d2
of left & right parentheses scanned
((q-p)*(y+x)) 5 5
Step 2: Obtain postfix expression for expression 2 5,2
in step 1 i.e. ((q-p)*(y+x)) 3 5,2,3
Infix Stack Postfix expression 4 5,2,3,
characte 4
r + 4 3 4*3=12 5,2,1
scanned 2
( ( * 12 2 12*2=2 5,24
( (( 4
q (( q - 24 5 24- 19
- ((- Q 5=19
P ((- qp Result = 19
) ( qp-
* (* qp-
( (*( qp-
y (*( qp-y
+ (*(+ qp-y
x (*(+ qp-yx
) (* qp-yx+
) Empty qp-yx+*

Step 3: Reverse the postfix expression to get


prefix expression
*+xy-pq

Evaluate above prefix expression with following


values: x = 2, y=3, p=6, q=2
*+ 2 3 – 6 2

To evaluate simply reverse the prefix


expression with values above and then
evaluate in same way as we evaluate postfix
expression
26–32+*
Charact Operan Operan Value Stac
er d1 d2 k
scanned
2 2
6 2,6
- 6* 2 6-2=4 4

3 4,3
2 4,3,
2
+ 2 3 2+3=5 4,5
* 5 4 5*4=2 20
0
Result = 20
Note: *Operand 1 is top element in stack here
while it is operand 2 in case of postfix evaluation

Queue
Definition

A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first is the first
one to be taken out. The elements in a queue are added at one end called the REAR and removed from
the other end called the FRONT.

Queue is a liner data structure and can be implemented using Array or Linked list.

Concept of queue is similar as People moving on an escalator, People waiting for a bus, People standing
outside the ticketing window of a cinema hall, Cars lined at a toll bridge etc.

Explain/define the term front and rear with relevance to queue. List the operations to be performed
at these ends.
Front end: This end is used for deleting an element from a queue. Initially front end is set to --1. Front
end is incremented by one when a new element has to be deleted from queue.

Rear end: This end is used for inserting an element in a queue. Initially rear end is set to -1. Rear end is
incremented by one when a new element has to be inserted in queue.

Draw the diagram of queue to represent front and rear pointers of queue

Sketch representation of queue as an array

INSERT (50)

DELETE

Enlist operations of queue

 Insert/enqueue: Adding new elements to the queue  Deletion: Removing an element from the
queue
 Delete/dequeue: Removing an element from the que
 isEmpty: To check whether queue is empty or not.
 isFull: To check whether queue is full or not
 peek/Retrieve: Retrieve the value of first element of queue, if queue is not empty

Describe queue full and queue empty operation conditions on linear queue with suitable diagrams
/example

Queue Full: Inserting an element in a queue which is already full is known as Queue Full condition (Rear
= Max-1)

Max is maximum number of elements in a queue. If rear pointer is not equal to max-1 then a new
element can be added to a queue. If queue is full then new element cannot be added to a queue.

Queue Empty: Deleting an element from queue which is already empty is known as Queue Empty
condition (Front = Rear = -1)

When front=rear pointer is -1 then we can not delete any data from a queue.

Enlist queue operations condition. - 2 Marks – Summer 2019 (I Scheme)

 Queue full
 Queue Empty

Algorithms
Write the procedure for inserting and deleting an element from queue OR Write algorithm to insert an
element into a linear queue OR Write an algorithm to delete an algorithm from a queue
Algorithm for INSERTing an element Algorithm for DELETEing an element
Step 1: IF REAR = MAX-1 Step 1: IF FRONT = -1 OR FRONT > REAR
Write OVERFLOW Write UNDERFLOW
Goto step 4 ELSE
[END OF IF] SET VAL = QUEUE[FRONT]
Step 2: IF FRONT = -1 and REAR = -1 SET FRONT = FRONT + 1
SET FRONT = REAR =0 [END OF IF]
ELSE Step 2: EXIT
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
Applications of Queue
 In computer system, queues are used in waiting lists for a single shared resource like printer, disk,
CPU
 Queues are used as buffers on MP3 players and portable CD players, iPod playlist
 In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until
a service representative is free.
 Handling of interrupts in real-time systems
 Queues are used to transfer data asynchronously between two processes (IO buffers), e.g., pipes,
file IO, sockets

Show the effect of INSERT and DELETE operations on to the Linear queue of size 10. The Linear queue
sequentially contains 10, 20, 30, 40, and 50 where 10 is at front of the queue. Show diagrammatically
the effect of –

1. INSERT (12) 2. INSERT (34) 3. DELETE 4. INSERT (56)

An array A will be used to implement the queue i.e. A[10] = {10,20,30,40,50}

INSERT (12)

INSERT (34)
DELETE

INSERT (56)

Linked list representation of Queue

Original Queue

Queue after INSERT operation

Queue after DELETE operation

Program
Write a menu driven program to insert, delete an #include <stdio.h>
element in a queue and display the queue – 8 #define size 20
Marks int main()
OR {
Write a ‘C’ program to implement a queue with int queue[size], front=-1,rear=-1, option,i,n;
insert and delete operation printf("Queue operations Menu\n");
printf("1. INSERT\n");
printf("2. DELETE\n");
printf("3. PEEK\n");
printf("4. DISPLAY\n");
printf("0. Exit\n");
while(option!=0)
{
printf("Enter Queue operation option\n");
scanf("%d",&option);
switch(option)
{
case 1:
printf("Enter number to be inserted in
Queue\n");
scanf("%d",&n);
if(rear==size-1)
printf("Stack Overflow");
else if(front==-1 && rear==-1)
{
front=rear=0;
queue[rear]=n;
}
else
{
rear++;
queue[rear]=n;
}

break;
case 2:
if(front==-1 || front>rear)
{
printf("Queue Underflow");
}
else
{
printf("Number deleted from queue=
%d\n",queue[front]);
front++;
if (front>rear)
front =rear=-1;
}

break;
case 3:
if(front==-1 || front>rear)
{
printf("Queue Empty\n");
}
else
printf("Number peek(front) from Queue =
%d\n",queue[front]);

break;
case 0:
exit(0);
case 4:
if(front==-1 ||front>rear )
printf("Queue is empty\n");
else
{
printf("Queue elements\n");
for (i=front;i<=rear;i++)
printf("%d\n",queue[i]);

}
break;
default:
printf("Not a valid queue operation\n");
}

return 0;
}

State the disadvantage of linear queue. How to overcome disadvantage of linear queue?
Disadvantage of linear queue:
On deletion of an element from existing queue, front pointer is shifted to next position. This results into
virtual deletion of an element. By doing so memory space which was occupied by deleted element is
wasted and hence inefficient memory utilization is occur.

As shown in above example, even though there is space (A[0] & A[1]) available, Queue overflow
condition occurs as Rear=MAX-1.

There are 2 solutions to overcome this issue:


1. Shift all queue elements to left so that space
is vacant at rear end. But this is complex and
time consuming process
2. Use circular queue - which joins front and
rear end of a queue i.e.
If front != 0 and rear = MAX – 1, then it means
that the queue is not full. So, set rear = 0 and
insert the new element there
Types of Queues
 Linear Queue (which we studied above)
 Circular Queue
 Priority Queue
 Multiple Queue
 Dequeue/Double ended Queue

Circular Queue
Draw and explain construction of circular queue

Define circular queue. Give its advantage. Sketch the diagram of circular queue

Definition
A circular queue is a linear data structure where
it store all elements in a specific order. It has two
ends front and rear where front is used to delete
an element and rear is used to insert an element.
The rear end of circular queue is connected to
front end of the same. It follows circular path
while performing insertion and deletion.

Advantage:
It allows insertion of an element in a queue when
queue has empty space in it and hence effective For INSERT operation
memory space utilization  If front = 0 and rear = MAX – 1, then the
circular queue is full and new element can
not be inserted
 If rear != MAX – 1, this means Queue has
space and then rear will be incremented and
the value will be inserted
 If front != 0 and rear = MAX – 1, then it
means that the queue is not full. So, set rear
= 0 and insert the new element there
For DELETE operation
 If front = –1, then there are no elements in
the queue. So, an underflow condition
 If the queue is not empty and front = rear,
then after deleting the element at the front
the queue becomes empty and so front
and rear are set to –1.
 If the queue is not empty and front = MAX–1,
then after deleting the element at the front,
front is set to 0.

Priority Queue
What is priority queue? Describe priority queue with suitable example

A priority queue is a data structure in which each element is assigned a priority. The priority of the
element will be used to determine the order in which the elements will be processed.

The general rules of processing the elements of a priority queue are:


 An element with higher priority is processed before an element with a lower priority
 Two elements with the same priority are processed on a first-come-first-served basis

Application

Priority queues are widely used in operating systems to execute the highest priority process first.

Priority queue can be represented using arrays or linked lists.

Priority Queue using linked list:

Each node has 3 parts – i) Information/data element ii) Priority of element iii) Address of next
node/element.

If we are using a sorted linked list, then the element with the higher priority will precede the element
with the lower priority.

Lower priority number means higher priority. For example, if there are two elements A and B, where A
has a priority number 1 and B has a priority number 2 then A will be processed before B as it has higher
priority than B

Insertion When a new element has to be inserted in a priority queue, we have to traverse the entire list
until we find a node that has a priority lower than that of the new element

Deletion: The first node of the list will be deleted and the data of that node will be processed first.

Advantage of Priority Queue


 Preferences to the higher priority process are added at the beginning. High priority process executes
first
 Keep the list sorted in descending order of Priority.

Multiple Queue
When we implement a queue using an array, the size of the array must be known in advance. If the
queue is allocated less space, then frequent overflow conditions will be encountered. To deal with this
problem, the code will have to be modified to reallocate more space for the array.
In case we allocate a large amount of space for the queue, it will result in sheer wastage of the memory.
Thus, there lies a tradeoff between the frequency of overflows and the space allocated. So a better
solution to deal with this problem is to have multiple queues or to have more than one queue in the
same array of sufficient size.

Dequeue/Double ended Queue


 Dequeue is a special type of data structure in which insertions and deletions will be done either at
the front end or at the rear end of the queue
 It is also often called a head-tail linked list because elements can be added to or removed from
either the front (head) or the back (tail) end.
 Following operations can be performed on Double ended/DeQueue:
Insert at rear end and delete from front end (same as that of linear/circular queue)
Insert at front end and delete from rear end (opposite to linear/circular queue)

 In the computer’s memory, a deque is implemented using either a circular array or a circular doubly
linked list
 There are two variants of a double-ended queue/Dequeue:
1. Input restricted deque In this dequeue, insertions can be done only at one of the ends, while
deletions can be done from both ends
2. Output restricted deque In this dequeue, deletions can be done only at one of the ends, while
insertions can be done on both ends.

Queue as a abstract data type(ADT)


Explain Queue as abstract data type. OR Describe how queue works as an abstract data type

Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value(data
members) and a set of operations(member functions).
The definition of ADT only mentions what operations are to be performed but not how these operations
will be implemented. It does not specify how data will be organized in memory and what algorithms will
be used for implementing the operations. It is called “abstract” because it gives an implementation-
independent view. The process of providing only the essentials and hiding the details is known as
abstraction.

Operations performed on Queue:

1. Queue() - creates a new queue that is empty


2. isEmpty( )- Check whether the queue is empty
3. isFull( )- Check whether the queue is full
4. Insert( )/enqueuer()- Insert an element in the queue at rear end
5. Delete( )/dequeuer()- Delete an element of a queue from front end
6. Peek() – Retrieve the value of front end
7. size() returns the number of items in the queue

Differentiate/Distinguish between stack and queue

Stack Queue
Insertion and deletion operations are performed Insertion and deletion operations are performed
at same end at different end
Stack works on LIFO (Last In First Out) principle Queue works on FIFO (First In First Out) principle
Only one pointer is used which is called Top Two separate pointers user – Front and Rear
Memory is not wasted Memory is wasted if linear Queue is used.
Example: Stack of plates or books Example: Bus Queue, Ticket Queue
Applications: Recursion, Reversing the list, Polish  Applications: waiting lists for a single shared
notations(Infix to Prefix/Postfix) etc. resource like printer, disk, CPU in computer,
Call center call queue etc.

Diagram of stack using array: Diagram of Queue using Array:


Linked List
Define linked list with example. Write its two advantages and disadvantages OR Explain the concept
of linear list with example

Define linked list

 It is a liner collection of data elements. These data elements are called as nodes.
 Linked list is a data structure which in turn can be used to implement other data structures like
stack, Queue etc.
 Each node contains 2 parts: first part stores INFO(information)/data of any simple data type or array
or structure. Second part contains address of the next node in sequence

 START stores the address of the first node in list. If START = NULL, then the linked list is empty
 We can traverse the entire list using START which contains the address of the first node; the NEXT
part of the first node in turn stores the address of its succeeding node.
 The last node will have no NEXT node connected to it, so it stores NULL (or -1) value. Hence NULL
indicates end of list.

Define the terms – Node, Information, Next pointer, NULL pointer, Empty list for linked list

Node It is Data element which contains information/data as well as address of next node
Information It is data which is store inside each node. It can be of simple data type or
array/structure etc.
Address Address indicates location of node
Next Pointer It is one of field of node structure which contains an address of next node
NULL Pointer It is address field of the last node in the linked list which specifies end of the list by
holding value as a NULL.
Empty List A linked list is said to be empty if head (start) node contains NULL pointer

Advantages:

 We can add any number of elements in the list using dynamic memory allocation
 Insertion/Deletion/Updation can be done easily just by storing address of new node in previously
existing node i.e. without movement of data elements for insertion/deletion

Disadvantages:

 Extra memory space required for storing address of the next node
 Data need to be accessed sequentially only so different amount of time is required to search/access
each data element
 It is not easy to sort elements stored in linear linked list

Differentiate between array and Linked List


Array Linked List
Stores fixed number of data elements Can store any number of data elements until
restricted by system memory
Store the data in consecutive memory location Stores data at random memory locations
Allow random access of data using index of array Data need to be accessed sequentially only
Insertion/Deletion operation is complex one Insertion/Deletion operation can be done at any
point (at beginning/end/middle) easily just by
changing next pointer/start pointer values
No extra space to store address of next data Extra space is required to store address of next
nodes

List and define operations of linked list with diagram (as above)
Explain linked list as an abstract data structure
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of value and a
set of operations.

The definition of ADT only mentions what operations are to be performed but not how these operations
will be implemented. It does not specify how data will be organized in memory and what algorithms will
be used for implementing the operations. It is called “abstract” because it gives an implementation-
independent view. The process of providing only the essentials and hiding the details is known as
abstraction

Elements (Data member) : head(/start), rear(/tail), count(of nodes)


Operations(Member functions) performed on linked list are as below:
Explain operations on singly linked list
Operation Definition
Create() Create a node in linked list
Insert() Insert a new node in linked list – Either at beginning of list or at end or at any position in
between
Delete() Delete a node in linked list. – Either at beginning of list or at end or at any position in
between
Search() Search specific data element in linked list.
Display() Used to display all node’s information
Count() Count number of nodes present in linked list
Traverse() Going through all the nodes of a linked list from one end to the other end.
isEmpty() To check if node is empty

State and describe three types of linked list with suitable diagram
Types of linked list
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Singly linked list:


 A singly linked list is the simplest type of linked list in which every node contains some data and
address of the next node of the same data type.
 A singly linked list allows traversal of data only in one way

Doubly Linked List:

 In a doubly linked list, every node contains some data and two addresses – one for next node and
another for previous node.
 Doubly linked list allows traversal of data only in both direction

Circular linked list


 In a circular linked list, the last node contains a pointer to the first node of the list.
 We can have a circular singly linked list as well as a circular doubly linked list.
 While traversing a circular linked list, we can begin at any node and traverse the list in any direction,
forward or backward, until we reach the same node where we started. Thus, a circular linked list has
no beginning and no ending.
Singly linked list
Traversing a linked
list Algorithm

Write an algorithm
to traverse a singly
linked list

Find/print number
of nodes in linked
list
Write an algorithm
to count number of
nodes in singly linked
list

Searching a value in
linked list

Write an algorithm
for searching a node
in linked list.

SET POS=NULL means that values is not found in if loop and hence not found
in list

Create a singly linked list using data fields 15, 20, 22, 58, 60. Search a node 22 from the SLL and show
procedure step-by-step with the help of diagram from start to end - Summer 2019 (I Scheme)

1. Singly linked list using given data will look like below.
PTR->DATA=15 since PTR->DATA!=22 lets move to next node
2. PTR->DATA=20 Since PTR->DATA!=22 lets move to next node

3. PTR->DATA=22 since PTR->DATA=22 it is found at location of 3 rd node

Inserting a new node in a linked list


 At beginning
 At end
 After given node
 Before given node

Inserting a new node at Algorithm:


beginning

Write an algorithm to insert


an element at the beginning
and end of linked list. --
Winter 2018 - I scheme- 6
Marks

OR
Explain insertion of new
node at start and at end in
singly linked list

AVAIL means if memory space is free/available. First check if memory


space is available for new node. If memory is not available then
display ‘Overflow’ message.
If free memory is available, allocate it to new node and set data and
next pointer is set with Start address. New node will be START node
now and hence START=New node address now.
Example:
Inserting a new Algorithm:
node at end
Write an algorithm
to insert an element
at the beginning and
end of linked list. --
Winter 2018 - I
scheme- 6 Marks

OR

Explain insertion of
new node at start
and at end in singly
linked list

OR
Write an algorithm
to insert a new node
as the last of a singly
linked list. Give
example (Refer
example below)
Example:
Inserting a new node Algorithm:
after a given node
Write an algorithm to
insert a node in between
in a link list.

Example:
Add a new node with value 9 after the node containing data 3.
Inserting a new node Algorithm:
before a given node

Write an algorithm to
insert a node in between
in a link list.

Example:
Add a new node with value 9 before the node containing 3
Deleting a node from a linked list
First node

Last node

Node after a given node

Node before a given node

Deleting a first node Algorithm:

Describe procedure to
delete an element from
singly linked list using
diagram. -- Winter 2018 - I
scheme- 6 Marks

Example:
Deleting a last node Algorithm:

Describe procedure to
delete an element from
singly linked list using
diagram. -- Winter 2018 - I
scheme- 6 Marks

Example:

Deleting a node after Algorithm:


given node

Describe procedure to
delete an element from
singly linked list using
diagram. -- Winter 2018 - I
scheme- 6 Marks
Write algorithm to delete
an intermediate node
from a Singly Linked List. --
Sample question paper – I
scheme- 4 Marks

Example:

Write a program to traverse a /* Program to simulate singly linked list */


linked list/singly linked list – Refer #include <stdio.h>
create linked list and Display #include <malloc.h>
function struct node
{
Explain insertion of new node at int data;
start and at end in singly linked list struct node *next;
};
Write a ‘C’ program to insert a struct node *start = NULL;
new node at the beginning into struct node *create_ll (struct node *);
singly linked list struct node *display (struct node *);
struct node *insert_beg (struct node *);
Write a ‘C’ program to insert new struct node *insert_end (struct node *);
node at the end of linked list struct node *delete_beg (struct node *);
struct node *delete_end (struct node *);
Write a program in ‘C’ to insert an struct node *insert_before (struct node *);
element in a linear queue. -- struct node *insert_after (struct node *);
Winter 2018 - I scheme- 4 Marks struct node * delete_node (struct node *);
struct node * delete_after (struct node *);
int
main ()
{
int option;
do
{
printf ("*****Linked List Menu*****\n");
printf ("1. Create a list\n");
printf ("2. Display a list\n");
printf ("3. Insert at beginning\n");
printf ("4. Insert at end\n");
printf ("5. Insert before\n");
printf ("6. Insert after\n");
printf ("7. Delete at beginning\n");
printf ("8. Delete at end\n");
printf ("9. Delete node\n");
printf ("10. Delete after\n");
printf ("0. Exit\n");
printf ("Please enter your option\n");
scanf ("%d", &option);
switch (option)
{
case 1:
start = create_ll (start);
break;
case 2:
start = display (start);
break;
case 3:
start = insert_beg (start);
break;
case 4:
start = insert_end (start);
break;

case 5:
start = insert_before (start);
break;
case 6:
start = insert_after (start);
break;
case 7:
start = delete_beg (start);
break;
case 8:
start = delete_end (start);
break;
case 9:
start = delete_node (start);
break;
case 10:
start = delete_after (start);
break;
}
}
while (option != 0);

return 0;
}

struct node * create_ll (struct node *start)


{
struct node *new_node, *ptr;
int num;
printf ("Enter -1 to end\n");
printf ("Enter the data :");
scanf ("%d", &num);
while (num != -1)
{
new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = num;

if (start == NULL)
{
start = new_node;
start->next = NULL;
}
else
{
ptr = start;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = new_node;
new_node->next = NULL;
}
printf ("Enter the data :");
scanf ("%d", &num);
}
return start;
}

struct node * display (struct node *start)


{
struct node *ptr;
ptr = start;

while (ptr != NULL)


{
printf ("%d ", ptr->data);
ptr = ptr->next;
}
return start;
}

struct node * insert_beg (struct node *start)


{
struct node *new_node;
int num;

printf ("Enter the data :\n");


scanf ("%d", &num);
new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = num;
new_node->next = start;
start = new_node;
return start;
}

struct node * insert_end (struct node *start)


{
struct node *new_node, *ptr;
int num;
ptr = start;
printf ("Enter the data :\n");
scanf ("%d", &num);
new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = num;
new_node->next = NULL;

while (ptr->next != NULL)


ptr = ptr->next;
ptr->next = new_node;
return start;
}

struct node * insert_before (struct node *start)


{
struct node *new_node, *ptr, *preptr;
int num, val;
ptr = start;
printf ("Enter the data :\n");
scanf ("%d", &num);
printf ("Enter the node value before which new data to be
added :\n");
scanf ("%d", &val);
new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = num;
new_node->next = NULL;

while (ptr->data != val)


{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = new_node;
new_node->next = ptr;
return start;
}

struct node * insert_after (struct node *start)


{
struct node *new_node, *ptr, *preptr;
int num, val;
ptr = start;
printf ("Enter the data :\n");
scanf ("%d", &num);
printf ("Enter the node value after which new data to be
added :\n");
scanf ("%d", &val);
new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = num;
new_node->next = NULL;
preptr=ptr;
while (preptr->data != val)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = new_node;
new_node->next = ptr;
return start;
}

struct node * delete_beg (struct node *start)


{
struct node *ptr;
ptr = start;
start = ptr->next;
free (ptr);
return start;
}

struct node *delete_end (struct node *start)


{
struct node *ptr, *preptr;
ptr = start;
while (ptr->next != NULL)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = NULL;
free (ptr);
return start;
}

struct node * delete_node (struct node *start)


{
struct node *new_node, *ptr, *preptr;
int num, val;
ptr = start;
//printf ("Enter the data :\n");
//scanf ("%d", &num);
printf ("Enter the node value before which data to be
deleted :\n");
scanf ("%d", &val);
//new_node = (struct node *) malloc (sizeof (struct node));
//new_node->data = num;
//new_node->next = NULL;

while (ptr->data != val)


{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = ptr->next;
free(ptr);
return start;
}

struct node * delete_after (struct node *start)


{
struct node *new_node, *ptr, *preptr;
int num, val;
ptr = start;
//printf ("Enter the data :\n");
//scanf ("%d", &num);
printf ("Enter the node value after which data to be deleted
:\n");
scanf ("%d", &val);
//new_node = (struct node *) malloc (sizeof (struct node));
//new_node->data = num;
//new_node->next = NULL;
preptr=ptr;
while (preptr->data != val)
{
preptr = ptr;
ptr = ptr->next;
}
preptr->next = ptr->next;
free(ptr);
return start;
}

Differentiate between linear linked list, circular linked list and doubly
linked list
Point Singly linked list Doubly linked list Circular linked list
Traversal direction Can traverse in single Can traverse in both Can traverse in
direction only directions single/both direction
depending upon type
of circular list
(singly/doubly)
No. of Pointers Uses one pointer(Next) Uses two pointers One or two depending
(Next and Previous) upon type of circular
list (singly/doubly)
Memory space for Less memory space More memory space as depending upon type
node compared to doubly as two pointers need to of circular list
only single pointer be stored in addition to (singly/doubly)
need to be stored in data
addition to data
Addition in between 2 addresses need to be 4 addresses need to be 2/4 addresses
updated updated depending upon type
of circular list
(singly/doubly)
Deletion in between 1 addresses need to be 2 addresses need to be 1/2 addresses
updated updated depending upon type
of circular list
(singly/doubly)
Link to node Each node is connected Next node also knows Last node knows about
to next node about previous node first node and vice
versa
Last node Last node connected to Last node connected to Last node is connected
NULL NULL back to first node
Diagram Refer diagram already Refer diagram already Refer diagram already
covered covered covered
Structure struct node struct node Depends upon type of
{ { circular
int data; int data; list(singly/doubly)
struct node *next; struct node *next;
} struct node *prev; Singly circular:
} struct node
{
int data;
struct node *next;
}
Doubly circular:
struct node
{
int data;
struct node *next;
struct node *prev;
}

Circular linked list


Describe circular linked list with suitable diagram. Also state advantage of circular linked list over
linear linked list

 We can have a circular singly linked list as well as a circular doubly linked list.
 In a singly circular linked list, the last node contains a pointer to the first node of the list.
 In doubly circular linked list, last node contains pointer to first node and first node contains pointer
to last node.
 While traversing a circular linked list, we can begin at any node and traverse the list in any direction,
forward or backward, until we reach the same node where we started. Thus, a circular linked list has
no beginning and no ending.
Describe any two terms from the following: information Field/ Data field, Address, Next Pointer with
respect to circular linked list with diagram – 2 Marks

Advantages of circular linked list


Describe advantage of circular linked list over linear linked list

 Any node can be starting point in search operation. We can traverse the whole list by starting from
any point. We just need to stop when the first visited node is visited again.
 Useful for implementation of circular queue. We do not have to maintain front and rear pointers if
we use circular linked list to implement it.
 Circular lists are useful in applications to repeatedly go around the list e.g. when multiple
applications are running on a PC, it is common for the operating system to put the running
applications on a list and then to cycle through them, giving each of them a slice of time to execute,
and then making them wait while the CPU is given to another application
 Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci
Heap

Insert at
beginnin
g
Insert at
end

Deleting With example, describe how circular linked list works when a node is
first node deleted from beginning of list
Original circular list:

Circular list after deleting first node:

Deleting
last node

Applications of Linked list


1. Polynomial representation: Polynomial 6X3 + 9X2 + 7X + 1 can be represented in linked list as below.

2. For implementation of circular queue


3. Circular lists are useful in applications to repeatedly go around the list e.g. when multiple
applications are running on a PC, it is common for the operating system to put the running
applications on a list and then to cycle through them, giving each of them a slice of time to
execute, and then making them wait while the CPU is given to another application
4. Circular Doubly Linked Lists are used for implementation of advanced data structures like
Fibonacci Heap
Trees
Define Tree.

Tree is non-linear data structure which is mainly used to store data that is hierarchical in nature.

Tree has finite number of nodes in which there is one special node called root node and remaining
nodes are divided into disjoint set which form the sub trees of the main tree

Basic Terminology

Node A node of a tree is an item or information along with the branches to other nodes.
Root node Topmost node in tree is called root node.
OR
node that has no parent node

e.g. node A is root node


Sub-trees If root node R is not NULL then trees T1,T2,T3 are called as sub-trees of R
Degree of Number of children nodes/Subtrees any node has.
node
Degree of Maximum number of child nodes of any node in tree.
tree
Leaf/Termina Node that has no child node is called leaf node e.g. E,F,J,K,H,I
l node The degree of a leaf node is zero.
D,E,F are leaf nodes as they don’t have any children.
Edge/Arc It is the line connecting a node N to any of its successor nodes
In-degree In-degree of a node is the number of edges arriving at that node
Out-degree Out-degree of a node is the number of edges leaving that node
Path Sequence of consecutive edges is called a Path e.g. Path from root node A to node I is
A,D,I
Ancestor All the node along the path from root to the particular node.
node e.g. nodes A, C, and G are the ancestors of node K.
Descendant A descendant node is any successor node on any path from the node to a leaf node.
node OR
A descendant refers to any element that is connected lower down the hierarchy tree

e.g. nodes C, G, J, and K are the descendants of node A.


Level of node Position of a node in the hierarchy of a tree is called as level of node

Level of node B is 1, Level of node G is 2

Every node in the tree is assigned a level number in such a way that the root node is
at level 0, children of the root node are at level number 1.
Thus, every node is at one level higher than its parent. So, all child nodes have a level
number given by parent’s level number + 1.
e.g. Level of B,C,D is 1, Level of E,F,G,H,I is 2 etc.
Depth/Height Maximum number of levels in a tree is known as depth of a tree
of Tree
Depth of the tree in the example above is 3
Sibling All nodes that are at the same level and share the same parent are called siblings
(brothers)

B and C are siblings; E and F are siblings,


Height of a The longest path from root node to leaf node is called Height of tree.
tree OR
Maximum level of any node in the tree

Height of above tree is 3


Parent If N is any node in T that has left successor S1 and right successor S2, then N is called
the parent of S1 and S2.
Complete A binary tree in which every non leaf node has exactly two children and all leaf nodes
binary tree are at same level is called complete binary tree.
Types of Trees
State types of trees

 General trees
 Binary trees
 Binary search trees
 Expression trees (not in syllabus)
 Tournament trees (not in syllabus)
 Forests (not in syllabus)

Applications of Trees
 File system directories
 Database design
 Implement hash table, maps
 Compiler construction
 Storage and retrieval of symbol tables
 Store complex data like structure or record
Applications of tree (from internet)

 Binary Search Trees(BSTs) are used to quickly check whether an element is


present in a set or not.
 Heap is a kind of tree that is used for heap sort.
 A modified version of tree called Tries is used in modern routers to store
routing information.
 Most popular databases use B-Trees and T-Trees, which are variants of the
tree structure we learned above to store their data
 Compilers use a syntax tree to validate the syntax of every program you
write.

https://www.programiz.com/dsa/trees

1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. struct node {
5. int data;
6. struct node* left;
7. struct node* right;
8. };
9.
10. struct node* createNode(value){
11. struct node* newNode = malloc(sizeof(struct node));
12. newNode->data = value;
13. newNode->left = NULL;
14. newNode->right = NULL;
15.
16. return newNode;
17. }
18.
19. struct node* insertLeft(struct node *root, int value) {
20. root->left = createNode(value);
21. return root->left;
22. }
23.
24.
25. struct node* insertRight(struct node *root, int value){
26. root->right = createNode(value);
27. return root->right;
28. }
29.
30. int main(){
31. struct node *root = createNode(1);
32. insertLeft(root, 2);
33. insertRight(root, 3);
34.
35. printf("The elements of tree are %d %d %d", root->data, root->left->data,
root->right->data);
36. }

You might also like