Notes - Data Structure - Algorithm
Notes - Data Structure - Algorithm
Notes - Data Structure - Algorithm
Define Algorithms
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.
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.
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.
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)
Searching
Define searching and give/enlist its type
Types:
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)
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
Limitations:
Highly inefficient for large data
}
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.
Binary search
Explain the working of Binary search with an example
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
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
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’
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
#include <stdio.h>
#define size 10
int main()
scanf("%d",&n);
scanf("%d",&num);
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)
found=1;
break;
else if(arr[mid]>num)
end = mid - 1;
else
begin = mid+1;
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
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.
Open Addressing
o Linear probing
o Quadratic probing
o Double hashing
Chaining – store keys having same hash value as linked list as shown below.
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
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
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.
Algorithm
Example
Perform bubble sort on following data to sort all elements in ascending order.
Program
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.
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
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.
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)
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.
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.
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
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
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+*+
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+*
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
INSERT (50)
DELETE
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.
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 –
INSERT (12)
INSERT (34)
DELETE
INSERT (56)
Original Queue
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.
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.
Application
Priority queues are widely used in operating systems to execute the highest priority process first.
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.
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.
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.
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.
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.
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
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
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
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
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
OR
Explain insertion of new
node at start and at end in
singly linked list
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
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:
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:
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;
}
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;
}
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;
}
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
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:
Deleting
last node
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
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)
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)
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. }