Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

BCA – 402 DATA STRUCTURE and ALGORITHM

1. Introduction and Overview 1.2

Basic Terminology; Elementary data organization:- (a)
Data.
(b) Data item.
i) Group item.
ii) Elementary data item.
(c) Organization of data. i)
Attribute ii) Entity iii)
Entity set.
(d) Information. i) Field ii)
Record iii) File
(e) Primary key.
(f) Classification of record. i)
Variable length ii) Fixed
length.

(a) Data :- Data are simply value or set of value.

Ex.: “LATUR”, 8.
(b) Data item :- Data item is single unit of values.
Ex.: “LTUR”,67.
Further data item are get divided into two parts.
i) Group items ii) Elementary items.
i) Group items :- Data items that are divided into subitems are
called group items.
Ex.: Employee Name : More Ram Hari

By: Chimle Mahesh 1 / 35

Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Employee name get divided into three subitems as first name, middle
name and last name.
ii) Elementary items :- Data items that are not divided into
subitems are called elementary item.
Ex.: 14 – 03 – 2022.
Social security number is treated as a single item.
(c) Organization of data :-
Collection of data are frequently organized into hierarchy of fields,
records and files.
- The above concept can be more cleared using following additional
terminology i.e. attribute, entity and entity set.
i) Attribute :- A attribute is a specified memory area used to store
data.
ii) Entity :- A entity is something that has retain attributes or
properties which may be assigned values. Here assigned values may
be either numeric or non-numeric.
Ex.: Attributes: Roll No. Name Grade
Values: 01 Ajay A
iii) Entity Set :- Entities with similar attributes form an entity set.
Each attribute of an entity set as a range of values, the set of all possible
values that could be assigned to the particular attribute.
Ex.: All the employees in an organization.
(d) Information :- A meaningful or processed data at particular attribute
is called as “information”.
The way that data are organized into the hierarchy of fields, records and files,
shows the relationship between attributes, entities and entity set as:
i) Field :- A field is a single elementary unit of information
representing an attribute of an entity.

1. By:Chimle Mahesh 2 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

ii) Record :- A record is the collection of field values of a given

entity. iii) File :- A file is the collection of records of the entities in a
given entity set.
(e) Primary key :- Every record in a file may contain many field items, but
the value in certain field may determine the record in the file uniquely. Such
a field K is called a primary key, and the values K1, K2, K3, …. Kn in such a field
are called key values or keys.
(f) Classification of Records :-
Records may also be classified according to the length.
A file can have fixed-length records or variable-length record. -
In fixed-length records, all the records contain the same data items
with the same amount of space assigned to each data item.
-In variable length records, file records may contain different lengths.
Ex.: Student records usually have variable lengths, since different student
take different number of courses.
Usually variable length records have a minimum and a maximum
length.

1.3 Data Structures :-

The logical or mathematical model of a particular organization
of a data is called a data structure.
The choice of a particular data model depends on two considerations:
i.The data model must be large in structure to show the actual
relationship of the data in the real world. ii.The structure should be
simple enough that one can effectively process the data when necessary.

By:Chimle Mahesh 3 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Following figure shows types of data structures:

Data Structure

[A] Primitive [B] Non-Primitive

Int
Float i) Linear ii) Non-linear
Character Arrays Tree
Boolean Stack Graph
Queue

Linked list
[A] Primitive Data Structure :-
Primitive data structure are basic data types i.e. int, real, character,
Boolean, float. These data types are primitive because they are directly
understand by the machine.

[B] Non-Primitive Data Structure :-

Linear and non-linear data structures are non-primitive data
structures.
❖ Linear Data structure :- Linear data structure’s are,
a) Arrays.
b) Stack.
c) Queue.
d) Linked list.
I) Arrays: -
The simplest type of data structure is linear array.

1. By:Chimle Mahesh 4 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Using a linear array, a list of finite number ‘n’ of similar data elements
referenced respectively by the set of ‘n’ consecutive (serially)
numbers, usually 1, 2, 3, ……….. n.
The elements of an array A may be denoted by the notation :
1. Subscript notation as A1, A2, A3, ……, An.
2. Parenthesis notation as A(1), A(2), A(3), …….., A(n).
3. By the bracket notation as A[1], A[2], A[3], ……., A[n]
Regardless of the notation, the number K in A[K] is called a
subscript and A[K]is called a subscripted variable.
II) Stacks :-
A stack, also called a last-in-first-out (LIFO) system, is a linear list in
which insertions and deletions place only at one end, called the Top.
This structure is similar in its operation to a stack of dishes on a spring
system as shown in following figure.
TOP

Disk

Sprig Container

As container is open at top side, new dishes are interested only at the
top of the stack and dishes can be deleted only from the top of the
stack.
III) Queue :-
A queue, also called a first-in first-out (FIFO) system, is a linear list in
which deletions can take place only at one end of the list, the ‘front’ of

By:Chimle Mahesh 5 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

the list, and insertions can take place only at other end of the list, the
‘rear’ of the list.
The structure operates in a same way as line of people waiting for bus
at bus-stop as Bus Stop shown in
figure.

Front -End

Rear-End
Fig: Queue of People

IV) Linked List :-

- A linked list, or one way list is a linear collection of data
elements, called ‘nodes’.
- Where the linear order is obtained by using pointers.
- Every node of linked list is get divided into two fields:
1. The first field is INFO which is used to store information of
the element.
2. The second field is LINK or next pointer field which is used to
store address of the next node in the list.
- Following figure shows a linked list with four nodes.

START

Next pointer field of second node.

Information field of second node.

Fig. Linked List with 4 nodes.

1. By:Chimle Mahesh 6 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- It is clear that, in above fig. each node is pictured with two fields.
- The left field use the actual information, and right field use store
the address of the next node.
- Arrow shows the order of the nodes.
- The next pointer or LINK field of the last node contains a invalid
address called ‘null pointer’.
- The null pointer (X) is used to shows the end of the list.
- The linked list has also a list pointer variable called START which
contains address of first node in the list.
- The starting address o the list which is stored in START is used
to traverse the whole linked list.
- Here if the linked list has no any node then such a list is called
‘null list’ or ‘empty list’ and it is denoted by the null pointer
assigning to START i.e. START = NULL.
❖ Non – Linear Data Structure :-
Tree and graph are the non – linear data structure.
a) Tree :- data frequently contain a hierarchy relationship between
various elements, the data structure which shows such relationship is
called ‘Tree’.
Getting more about trees consider the following two examples.
i) Record structure. ii) Algebraic
expression.
i) Record Structure :- An employee personal record may contain
following data items.
Ex.: Social_security_no Name Address Age Salary.

By:Chimle Mahesh 7 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- In above data items, name and address may be group items with
sub item i.e.
Name :- F_Name, M_Name, L_Name.
Address :- Street Address & Area Address.
- Further are its may be group item having sub item city, state and
pin code number.
- The hierarchical structure of above data element is in term of
tree’s is as follows,

Employee

Social Security No Name Address Age Salary

F_Name Street

M_Name Area

L_Name

City

State

Pin Code

This tree structure in terms of level numbers is pictured as bellow,

01. Employee
(2) Social Security Number
(2) Name

1. By:Chimle Mahesh 8 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

(3) F_Name
(3) M_Name
(3) L_Name
(2) Address
(3) Street
(3) Area
(4) City
(4) State
(4) Pin Code
(2) Age
(2) Salary.

ii) Algebraic Expression :- Consider the algebraic expression (5x

– y)3 * (a + 10b). Using vertical arrow for expatiation and asterisk (*)
for multiplication even algebraic expression can be represented
interims of trees as follows,

b) Graph :- Data sometimes contain a relationship between pairs of

elements which is not necessary hierarchical in nature. The data
structure which shows such type of relationship is called a ‘Graph’. Ex.:
Consider an airline flies only between the cities that are connected by
lines as shown in following fig.

By:Chimle Mahesh 9 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Delhi

Mumbai Kolkatta

Aurangabad Pune

Fig. A graph shows airlines flies between cities .

1.4 Data Structure Operation :-

- A data structure that one choose for a given situation depends
on a frequency with which specific operations used to process
data.
- There are nearly eight operation in data structure.
- Out of them first four play major role. They are as follow,
1. Traversing.
2. Searching.
3. Inserting.
4. Deleting.
5. Sorting.
6. Messaging.

1. By:Chimle Mahesh 10 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

7. Copying.
8. Concatenation.
1. Traversing :-
- This operations is used to accessing each record exactly once of
process certain items in the records.
- Ex.: We have 1, 5, 10, 7 items into data structure.
- Then access (visit) all items means read one five, seven, ten in
certain manner called as ‘Traversing’.
2. Searching :-
- This operation is used to finding the location of the record with
the given key value.
- Ex.: If we have data 1, 5, 10, 7 stored sequentially.
- We want to find location of data 10, it is located ‘3 rd’ location is
called as, ‘Searching’.
3. Inserting :-
- This operation is used to adding a new record to the structure.
- Ex.: Data as 1, 5, 10, 7.
- We want to insert ‘20’ at ‘4th’ location after that output is 1, 5, 10,
20, 7.
4. Deleting :-
- This operation is used to removing a record from the structure.
- Ex.: Data as 1, 5, 10, 20, 7
- We want to delete data on ‘3rd’ location after delete output is 1,
5, 20, 7.

By:Chimle Mahesh 11 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

5. Sorting :-
- This operation is used to arrange the records in same logical
order.
6. Merging :-
- This operation is used to combining the records in two different
sorted fields into a single a sorted file.
7. Copying :-
- This operation is used to make the duplication of the record.
8. Concatenation :-
- This operation is used to combine any two records into single
record.

1.5 Notion and Concept of algorithm :-

The following summarizes certain basic conversation that are used in
writing algorithms.

1. Identifying Numbers :- Each algorithm is assign an identifying

number.
Ex.: Algorithm 4.3 refers to their third algorithm in chap. 4
2. Steps :- The steps of the algorithm are executed one by one starting
from step1.
3. Name of the Algorithm :- Every algorithm is given an identifying
name written in capital letters.
4. Introduction Comments :- Algorithm name is followed by a brief
description which input data, purpose and identifiers and variable
which are used in algorithm.

1. By:Chimle Mahesh 12 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

5. Comments :- Comment is a written in bracket which indicate the

purpose of the step.
6. Variable Name :- Variable name will use capital letters like ‘MAX’ or
‘DATA’. Single letter names of variables used as counters or subscripts
will also be capitalized in the algorithm and lower case may be used
for these variables in the mathematical description and analysis.
7. Assignment Statement :- Assignment statements will use the dots –
equal notation as :=.
Ex.: MAX := DATA [1]
Some text use the backward arrow () or equal to sign (=) for this
operation.
8. Input / Output :-
- Data element may be assign to the variable by read statement as
:- Read : variable name Ex.: Read : a
- Similarly, messages placed in quotation mark and data in
variables may be output by means of write as print statement
with following form.
Write : Messages or Variable name
Ex.: Write : “Have a nice day.”
Ex.: Write : MAX
9. Procedures :-
- The term ‘Procedure’ will be used for an independent
algorithmic module which solve a particular problem.
- The use of word ‘Procedure’ or ‘Module’ rather than
‘Algorithm’.

By:Chimle Mahesh 13 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The term procedure will also be used to describe a certain type

of sub algorithm.
10. Control Structures Statement :-
- Control may be transfer to any step ‘n’ of the algorithm by using
the goto statement as,
Ex.: “goto step n”
- There are following control structure or type of logic or flow of
control.
I. Sequence Logic / Sequential Flow.
II. Selection Logic / Conditional Flow.
III. Iteration Logic / Repetitive Flow.

I. Sequence Logic :- In this structure the modules are executed

sequentially.
II. Selection Logic :-
- In this structure a required module is get selected out of several
modules.
- The frequently used structure is if structure.
- Here end of the if structure by the statement :- [End of if
structure]
- The conditional structure are divided into three types.
i) Single Alternative. ii)
Double alternative. iii)
Multiple Alternative.
i) Single Alternative :- This structure has the form:

If Condition, Then :

1. By:Chimle Mahesh 14 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[Module A]
[End of If structure]
ii) Double Alternative :- This structure has a form:

If Condition(1), Then :
[Module A]
Else :
[Module B]
[End of If structure]
iii) Multiple Alternative :- This structure has the form:

If condition(1), Then :
[Module A]
Else if condition (2),Then:
[Module A2]
. .
. .
Else if condition (n), Then:
[Module An]
Else [Module B]
[End of If structure]

III. Iteration Logic :-

- It includes loops. Here the end of loop is indicated at the end of
the structure by the statement:
[End of loop]
- In data structure generally repetitive loops are used as
following.
i) Repeat for …….. loop. ii)
Repeat while ….. loop.

By:Chimle Mahesh 15 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

i) Repeat for …… loop :-

- The repeat for …… loop uses an index variable, such as K, to
control the loop.
- The loop will usually have the form
Repeat for K = R to S by T
[Module]
[End of loop]
ii) Repeat while ….. loop :-
- The repeat while …. Loop uses a condition to control the loop.
- The loop will usually have the form:

Repeat while condition :

[Module]
[End of loop]

11. Exit Statement :- Exit statement is used to terminate algorithm.

12. Sub Algorithm :-
- A sub algorithm is an independently define algorithm.
- The algorithm is define separately from the main algorithm and
the purpose is to perform some complication when required
under control of the main algorithm.
- Sub algorithm receives values, called arguments from the main
algorithm and send back the result to the main algorithm.
- Sub algorithm may be call by many different algorithms, sub
algorithms or it may be called by itself recursively.
- Sub algorithms are classified into two basic categories that are,
(1) Function Sub Algorithm.
(2) Procedure Sub Algorithm.

1. By:Chimle Mahesh 16 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

(1) Function Sub Algorithm :-

- Function is used to return single value to the calling algorithm.
- Here transfer of control back and returning of the value are
perform by the statement : [Return (value)]
- The function begin as, : Function_name : NAME(PAR1, PAR2,
……, PARn)

(2) Procedure Sub Algorithm :-

- A procedure sub algorithm works similar to a function but
doesn’t return any value explicitly.
- Only control is transferred back to the calling algorithm by the
statement ‘return’.
- In procedure sub algorithm changed parameters are return to
the main algorithm automatically.
- A procedure begins as follows,
Procedure_Name :
NAME(PAR1, PAR2, ……. PARn)

1.6 ALGORITHMS: COMPLEXITY, TIME-SPACE TRADEOFF :-

- A well-defined list of steps for solving a particular problem is
called ‘Algorithm’.
- The most important use of these steps is to develop effective
algorithm for processing our data.

By:Chimle Mahesh 17 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The time and space are two important measurements which are
used to calculate the efficiency of an algorithm.
- The complexity of an algorithm is the function which gives the
running time and/or memory space used by the input size.
- There are two case usually investigates to find complexity.
1. Worst Case.
2. Average Case.
1. Worst Case :-
- The maximum value of F(n) for any possible input.
- C(n) = n is complexity of linear search algorithm.
2. Average Case :-
- The excepted value of F(n).

1. By:Chimle Mahesh 18 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Number ‘n’ is item in DATA, so no. of comparison can be any of

By:Chimle Mahesh 19 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

the no. 1, 2, 3, ………, n and each no. occurs in probability

then,

- In algorithm analysis different algorithms are compared by

calculating the efficiencies of these algorithms.
- Ex.: Consider an algorithm ‘A’ with ‘n’ size of the input data.
- The time is measure in terms of number of comparison perform
in sorting and searching.
- Space is measure by counting the maximum memory space
required to store given ‘n’ size of data. Hence, for algorithm a
complexity function c(n) which gives the running time and
storage space for into data size n.
- Following are the two algorithm they are compared using
complexity function.
- Suppose, we are given the name of the employee and we want to
find their telephone number.
- Here, telephone number may be easily display using one of the
following way.
1. Linear Search.
2. Binary Search.

1. By:Chimle Mahesh 20 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1. Linear Search :-
- It is clear that time required execute the algorithm is
proportional to the number of comparisons performed by the
linearly.
- In this method each name of the file is get compared so the
average number of comparisons for the file with ‘n’ records is
equal to
- Hence, the complexity of linear search algorithm is

2. Binary Search :-
- In this method the name are stored in sorting order
alphabetically.
- This algorithm compare a given name with the name in the
middle of the list : This tells which half of the list the name
contain.
- Then compare name with the name in the middle of the correct
half to determine which quarter of the list contains name.
- Continue the process until finding name in the list. - Hence, the
complexity of the binary search method is c(n) = log 2n

1.8 Linear Array :-

A linear array is a list of finite number ‘n’ of similar type of data elements
such that
The element of an array are referenced by index set consisting of ‘n’
consecutive numbers.
The elements of an array are stored (placed) in successive memory location.

By:Chimle Mahesh 21 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

A number ‘n’ is called length or size of the array.

Suppose the index set consists of the integers 1, 2, 3, ……, n then the length
or the number of elements of an array can be obtained from the index set by
the formula.
length = UB – LB + 1
OR
length = UB (if LB = 1)

Here ‘UB’ is the largest index called upper bound and ‘LB’ is the lower bound
i.e. smallest index of an array.

DATA 30 15 35 40 50

LB 30 10 1 2 3
4 15
2 35
3 40
4 50
UB 5

length = UB – LB + 1
length =5–1+1 length= 4 – 0 + 1
=4+1 =4+1
=5 =5
- The element of an array may be denoted by the notation :

4. Subscript notation as :
A1, A2, A3, ……, An.
5. Parenthesis notation as:

1 .9 Representation of an Linear Array in Memory :- Consider

linear array LA stored in computer memory.
We know that the internal memory of a computer is a simply sequence
of addresses location as shown in following figure.

1. By:Chimle Mahesh 22 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

A(1), A(2), A(3), …….., A(n).

6. By the bracket notation as:
A[1], A[2], A[3], ……., A[n].

1000

1001

1002

1003

1004

Fig. Computer
Memory

In above representation computer doesn’t keep track of the address of

each element of an array.
If each keep track only the address of the first element of an array
because the elements of an array get stored in successive memory
cells.
Here the address of the first element of an array is represented by base
[LA] which is equal to 1000 and called base [LA] address of LA using
this base address computer calculate the address of any element K of
an array by using the formula as,

By:Chimle Mahesh 23 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

LOC [LA [K]] = Base [LA] + W [K – LB]

Here, ‘k’ is any location of ‘LA’. ‘W’ is the number of cells per word for
an array.
Ex.: W = 4 each indicate that it requires four cells of internal memory
to store each element.
Here, time require to access any element of an array at location ‘k’ is
cell because accessing is perform directly without scanning other
elements.
For determing internal memory location of ‘n’:
Consider an array DATA [10 : 80], suppose base address of DATA
i.e. Base [DATA] = 1000 and W = 4 words per cells for an array
element at location 12 is
LOC [DATA (k)] = Base [DATA] + W (k – LB)
LOC [DATA (12)] = 1000 + 4 (12 – 10)
= 1008
1.10 Traversing Linear Array :-
Suppose LA is the Linear Array used to store a list of elements in
computer memory.
To print each element of LA or count the number of elements of LA
traversing operation is use.
Accessing or processing each element of an array LA exactly once is
called “Traversing”.
Following is an algorithm which traverses a linear array LA.

Algorithm 1.1 : TRAVERS LA (LA, LB, UB, k)

Let LA is linear array with ‘n’ element, k is a counter,
variable LB is lower bound, UB is upper bound.
Step 1. : [Initialize counter k]

1. By:Chimle Mahesh 24 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

set k LB
Step 2. :
Repeat step 3 & 4 while
(k <= UB)

Step 3. : Apply PROCESS to LA[k]

Step 4. : [Increase counter k by 1]
set k k+1
[End of step 2 loop]
Step 5. : [Finished] Exit.

1.11 Inserting and Deleting Linear Array :-

- Let LA is a linear array used to store collection of data elements

in computer memory.
- Here, insertion operation is used to add a new element to an
array and deletion operation is used to remove any one of the
element from an array.
- If the allocation memory space for a linear array is large enough
the insertion operation of an element at the end of the linear
array can be perform easily then, the insertion of an element in
the middle of the linear array that means when one need to
insert a element middle of the array then on the average half of
the element must be moved downward to the new location so
that new element get inserted and also the order of other
elements get preserved.
- Similarly, an element at the end of the linear array may be
deleted easily than the element present in the middle of the

By:Chimle Mahesh 25 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

array that means for deletion of an element from the middle of

an linear array is difficult because each next element of an array
must be moved one location upward in order to fill up the array.
- Following is an algorithm to insert data element ITEM into the
kth position in a linear array LA.

Algorithm 1.2 : INSERTITEM (LA, k, n, ITEM)

Let LA is linear array with ‘n’ element, k is a positive
integer such that k <= nth algorithm perform insert
element ITEM into the kth position in LA.

Step 1. : [Initialize counter J]

set J N
Step 2. :
Repeat step 3 & 4
while J >= K
[Move Jth element
Step 3. :
downward]
set LA[J + 1] LA[J]
Step 4. : [decrease counter J by 1]
set J J–1
[End of step 2 loop]
Step 5. : [Insert element ITEM at location K]
set LA [K] ITEM
Step 6. : [Reset N]
set N N+1
Step 7. : [Finished] Exit.

Following is an algorithm delete the kth element from linear

array and assign it to variable ITEM.

1. By:Chimle Mahesh 26 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Algorithm 1.3 : DELETEITEM (LA, K, N, ITEM)

Let LA is linear array with ‘n’ element, k is a positive
integer such that k <= N. The algorithm delete k th element
and store in ITEM.

Step 1. : [Store element of location K into ITEM]

set ITEM LA[K]
Step 2. :
[shift element upward] Repeat
for J K to N – 1

Step 3. : [Move J + 1 element upward]

set LA[J] LA[J + 1]
[End of step 2 loop]
Step 4. : [Reset N]
set N N–1
Step 5. : [Finished] Exit.

1.12 Searching Method :-

- Let a collection of data element are stored in computer memory
by using a linear array LA.
- In data structure searching operating is used to find the location
LOC of the given ITEM of information.
- Here a search is set to be successful or unsuccessful according to
weather ITEM is present or not (absent) in list.

By:Chimle Mahesh 27 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- This method is depend on the type of data structure used to

maintain such list in memory.
- Normally operations like inserting, deleting and updating result
in data modification.
- This means that the operations inserting and deleting are used
to modify the data.
- Hence, these operations are closely related to searching.
- That is in deletion of an ITEM one must search for the location of
the ITEM and for insertion of an ITEM in the given list one must
search for the proper place.
- Here the operations insertion and deletion also required at
certain line which depend on the type of data structure used for
it.
- The complexity of searching algorithm is measured in term of
the number of comparison required to search an ITEM in given
list.
- In data structure particular element is search using one of the
following two searching methods.
I. Linear Search Method.
II. Binary Search Method.

I. Linear Search Method :-

- Let LA is a linear array with ‘n’ elements.
- The accurate way to search given ITEM in LA is to make
comparison of ITEM with each element of LA one by one i.e. first

1. By:Chimle Mahesh 28 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

test weather LA[1] = ITEM. Then last weather LA[2] = ITEM and
so on.
- The method which traverses LA sequentially to search ITEM is
called ‘Linear Search’ or ‘Sequential Search’.
- In this search, first the ITEM is stored at LA (N + 1) location as =
LA (N + 1) = ITEM.
- Then searching is started from the first element of the list, here
if ITEM is present at that time this search method display a
message successful search and if ITEM is not present in the list
then this search method display a message unsuccessful search
and reset the location variable LOC to Null or Zero.
- Following is a algorithm to find the location LOC of given
element ITEM for an array LA.

Algorithm 1.4 : LINERSRH (LA, LOC, N, ITEM)

Let LA is linear array with ‘N’ element and ITEM is a given
item of information. This algorithm perform finding the
location LOC of ITEM in LA or sets LOC = 0 if the search is
unsuccessful.

Step 1. :
[Insert ITEM at the end of the LA] set
LA (N + 1) ITEM
Step 2. : [Initialize counter location]
Set LOC 1
Step 3. : [Search for ITEM in LA]
Repeat step 4
while (LA [LOC] ITEM)

By:Chimle Mahesh 29 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Step 4. : [Increase location LOC by 1]

LOC LOC + 1
[End of step 3 loop]
Step 5. : [Is search successful ?] If
LOC N + 1, Then
write “Unsuccessful search” and LOC
0 else write “Successful search a location
LOC”.
[End of if structure]
Step 6. : [Finished] Exit.

2. Binary Search Method :-

- Suppose LA is a linear array which is stored in increasing order

according to alphabetically.
- Binary search is an efficient algorithm method which find the
location LOC of the given item of information in the given array
LA.
- This method works as follows,
- Assign the pointer variable START and END denote starting and
ending locations of the elements in a list, i.e. START = 1 or LB
and END = N or UB.
- Calculate middle of the list and store it at pointer variable MID
as,
MID = INT [START + END] / 2

- Here INT [K] is used to obtain int value of K.

1. By:Chimle Mahesh 30 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Compare ITEM with middle element that means if ITEM = LA

[MID], then print a message search is “successful” and assign

value of MID to LOC as LOC = MID and exit.

- If ITEM LA [MID] then determine its proper half as :-

a. If ITEM < LA[MID], then ITEM can appear in the left half.
Hence to search ITEM in left half reset value of END as:
END = MID – 1 and repeat step 2.

b. If ITEM > LA[MID], then ITEM can appear in the right

half.
Hence to search ITEM in right half reset value of START
as:
START = MID+1 and repeat step 2.

- Here if there N elements, then this algorithm begins with

assigning START = 1 and END = N.
- The above steps 2–4 repeated still value of START < END.

- If an ITEM is not appear then algorithm assign LOC = Null (0)

value.
- It indicates that ITEM is not present

- Ex.: Consider a list to be sorted array LA of 14 elements.

LA : 10 11 20 22 30 33 40 44 50 55 60 66 70
77
- Apply the binary y search method to LA to search for value ITEM
= 44.

By:Chimle Mahesh 31 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1.
10 11 20 22 30 33 40 44 50 55 60 66 70 77

1 2 3 4 5 6 7 8 9 10 11 12 13 14

After initializing START & END it becomes START = 1 &

END = 14
Then calculate the middle MID as,
MID = INT [SART + END] / 2
= INT [1 + 14] / 2
= INT [7]
MID = INT [7]
Hence, LA [MID] = 40

2. Since 44 > 40, START changes its value by,

START = MID + 1 =7+1 =
8
Hence, the list 44 50 55 60 66 70 77
become, 8 9 10 11 12 13 14

START = 8 & END = 14

Calculate the MID = INT [START + END] / 2
= INT [8 + 14] /2
= 11
LA [MID] = 11
2. Since, 44 < 60, END changes its value by END = MID – 1
= 11 – 1
= 10

1. By:Chimle Mahesh 32 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Hence, the list 44 50 55 become,

8 9 10
Let, START = 8 & END = 10

calculate middle MID as,

MID = INT [START + END] / 2
= INT [8 + 10] / 2
=9
LA [MID] = 50
3. Since 44 < 50, END changes its value by, END = MID – 1
=9–1
=8
LA [MID] = 44
Let, START = 8 & END = 8

calculate middle MID as,

MID = INT [START + END] / 2
= INT [8 + 8] / 2
= INT [8]
LA [MID] 44

4. Since 44 = 44, search is successful at location LOC = MID i.e.

8.

Following is an algorithm binary search method.

Algorithm 1.5 : BINARYSRH (LA, LOC, N, MID, START, END,

ITEM)

By:Chimle Mahesh 33 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Let LA is a sorted linear array with N element and ITEM is

a given information for which we have to make search.
The variable START,END,MID are the local pointer
variable used to stone location of beginning, ending and
middle element of the list respectively. This algorithm
perform finding the location LOC of ITEM in LA or sets
LOC = Null.

Step 1. : [Initialize pointer START & END]

set START = 1 or LB & END = N or UB.
Step 2. : Repeat step 3 & 4 or through 4
While START <= END
Step 3. : [Calculate Middle]
MID = INT [(START + END) / 2]
Step 4. : [Is element ITEM pointer in LA]
if [ITEM < LA(MID)], then
[END changes]
Set END=MID-1.
Else if ITEM > LA [MID], then
[START changes its value]
set START = MID + 1
else
write “Successful Search”
set LOC = MID and Exit
[End of if structure]
[End of step 2 loop]
Step 5. : [set LOC]

1. By:Chimle Mahesh 34 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

write “Unsuccessful search”

LOC = Null
Step 6. : Exit.

Complexity of Binary Search :-

In this algorithm there is deduction of half comparison the

total comparison require to locate certain ITEM are determine
using a complexity function F(N) as,
F(N) = [log2 N] + 1

By:Chimle Mahesh 35 / 35
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

2. Sorting and Linked list

2.2 Bubble Sort :
Suppose the list of numbers DATA[1], DATA[2], ……., DATA[N] is in
memory.
The bubble sort algorithm works as follows :
Step 1 : Compare DATA1[1] & DATA [2] and arrange them in the
desired order, so that DATA[1] < DATA[2].
- Then compare DATA[2] & DATA[3] and arrange them, so that
DATA[2] < DATA[3].
- Continue this process until we compare DATA[N – 1] with DATA[N]
and arrange them, so that DATA[N – 1] < DATA[N].
- In step 1, there are N – 1 comparisons take place.
- After completing step 1, DATA[N] will contain largest element is
“Bubble up” to the Nth position.
Step 2: Repeat step 1 with one less comparison that means continue
comparison until we compare DATA[N – 2] with DATA[N – 1] and
arrange them so that DATA[N – 2] < DATA[N – 1].
- In step 2, there are N – 2 comparison take place.
- After completing step 2 DATA[N – 1] will contain second largest
element is “Bubble up” to the N-1 position.
|
|
|
Step N – 1: Compare DATA[1] with DATA[2] and arrange them, so
that DATA[1] < DATA[2].
- After N – 1 steps the list will be sorted in ascending order.
- Here during each step the largest element is “bubbled up” to the N th
position.
- In bubble sort method each of the above step is called “PASS”.

By: Chimle. M. D. 1 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Hence to sort a DATA[N] element bubble sort algorithm required N –

1 passes and each pass has N-PASS comparisons.
Ex.: Sort the following list DATA by using bubble sort method and shows
all passes.
42 23 74 11 65 15 10 08
Ans: In bubble sort there are n-1 passes perform i.e 8-1=7 as shown in follows.
Each pass has n-pass comparisons perform.
Circle indicate swapping of two elements
Pass 1: In pass one there are N – 1 comparison are perform as :
i. Compare DATA[1], with DATA[2], since 42 > 23, interchange
them. Hence given list becomes,
23 42 74 11 65 15 10 08

ii. Compare DATA[2] with DATA[3]. Since 42 < 74, a list not alter.
iii. Compare DATA[3] with DATA[4]. Since 74 > 11, interchange them.
Hence given list becomes,
23 42 11 74 65 15 10 08

iv. Compare DATA[4] with DATA[5]. Since 75 > 65, interchange them.
Hence given list becomes,
23 42 11 65 74 15 10 08

v. Compare DATA[5] with DATA[6]. Since 74 > 15 interchange them.

Hence given list becomes,
23 42 11 65 15 74 10 08

vi. Compare DATA[6] with DATA[7]. Since 74 > 10, interchange them.
Hence given list becomes,
23 42 11 65 15 10 74 08

By: Chimle. M. D. 2 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

vii. Compare DATA[7] with DATA[8]. Since 74 > 08, interchange them.
Hence given list becomes,
23 42 11 65 15 10 08 74

After completing first pass the largest number 74 is bubbled up to

the last position i.e 8th, but the remaining numbers are still unsorted.

Pass 2: In Pass 2, there are n-pass i.e 8-2=6 comparisons perform

in following table.

After completing second pass the second largest no. 65 is bubbled up to

the next–to–last position (n – 1) i.e 7th but the remaining numbers are
unsorted.
Pass 3: In Pass 3, there are n-pass i.e 8-3=5 comparisons perform
in following table.

By: Chimle. M. D. 3 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

After completing of pass 3 the third largest no. 42 is bubbled up to the

position (n – 2)i.e. 6th, but the remaining number unsorted.

Pass 4: In Pass 4, there are n-pass i.e 8-4=4 comparisons perform

in following table.

After competing of pass 4 the fourth largest no. 23 is bubbled up

position (n – 3) i.e. 5th ,but the remaining number unsorted.

Pass 5: In Pass 5, there are n-pass i.e 8-5=3 comparisons perform

in following table.

By: Chimle. M. D. 4 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

After completing of pass 5 the fifth largest no. 15 is bubbled up to

position (n – 4) i.e. 4th, but the remaining number unsorted.
Pass 6: In Pass 6, there are n-pass i.e 8-6=2 comparisons perform
in following table.

By: Chimle. M. D. 5 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

i. 11 10 08 15 23 42 65 74

By: Chimle. M. D. 6 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

ii. 10 11 08 15 23 42 65 74

10 08 11 15 23 42 65 74

After completing of pass 6 the sixth largest no. 11 is bubbled up to the

position (n – 5) i.e. 3rd. But the remaining number is unsorted.

Pass 7: In Pass 7, there are n-pass i.e 8-7=1 comparisons perform

in following table.

By: Chimle. M. D. 7 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

i. 10 08 11 15 23 42 65 74

By: Chimle. M. D. 8 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

08 10 11 15 23 42 65 74
After completing of pass 7, list get sorted i.e.,
08 10 11 15 23 42 65 74

Q. Sort the given list by using Bubble Sort Method.

a) 32 51 27 85 66 23 13 57
b) 25 48 37 22 57 86 33 92

An algorithm for Bubbled Sort Method :

Algorithm 2.2 : BUBBLESRT (DATA, N, PASS, PTR, TEMP)

Let DATA is linear array unsorted with N element. PASS, PTR,
TEMP are the local variables used to count the PASS, point
element location and to store value temporary respectively.
This algorithm perform sort the given list in ascending order.
Step 1: Repeat through step 5
For PASS =1 to N – 1
Step 2: [Initialize pointer PTR]
Set PTR = 1
Step 3: Repeat through step 5
While PTR <= N – PASS
Step 4: [Is element at PTR & PTR + 1 in out of order?]
If (DATA[PTR] > DATA[PTR + 1]), then:
[Interchange (PTR) & DATA(PTR + 1)]
TEMP = DATA[PTR]
DATA[PTR] = DATA [PTR + 1]
DATA[PTR + 1] = TEMP

By: Chimle. M. D. 9 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[End of if structure]
Step 5: [Increase PTR by 1]
set PTR = PTR + 1
[End of step 3 loop]
[End of step 1 loop]
Step 6 : [Finished] Exit.

• Complexity of Bubbled Sort Method :

- Time require to sort given list in terms of comparison perform in
the algorithm.
- The complexity function F(N) is used to count number of
comparison.
- Here in bubbled sort method, in pass 1 there are N – 1
comparisons are perform and this part place a largest element at
the last position.
- In second pass there are N – 2 comparison perform and it place
the second largest element of the second last position. Repeat the
above process until we execute all passes.
- Hence the number of comparison perform in each pass determine
as,
F(N) = (N – 1) + (N – 2) + …….. + 2 + 1
N(N – 1) N2

= 2 = 2 + 0(N) F(N)
= 0(N2)
- That means time require execute the bubble sort algorithm is
propositional to N2.
- Here N is the number of input elements.

By: Chimle. M. D. 10 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

2.1 Selection Sort Method :

- Suppose linear array list DATA is in memory with N elements
DATA[1], DATA[2], ……., DATA[N].
- A selection sort algorithm works as follow, Pass 1:
- Find the location LOC of the smallest element in the list of N elements
DATA[1], DATA[2], ……, DATA[N] and the DATA[LOC] and
DATA[1].
- Then, DATA[1] is sorted.
Pass 2:
- Find the location LOC of the smallest element form the list of N – 1
elements DATA[2], DATA[3], ……., DATA[N] and then interchange
DATA[LOC] with DATA[2].
- Then DATA[1], DATA[2] are sorted, since DATA[1] < DATA[2]1.
|
|
|
Pass N-1 :
- Find the location of the smallest element from the list of elements
DATA[N – 1], DATA[N].
- Then interchange DATA[LOC ]with DATA[N-1].
- Then DATA[1], DATA[2], ………, DATA[N] is sorted, since DATA[N –
1] <= DATA[N].
- After completing N – 1 passes the list of DATA becomes a sorted list
in ascending order.

By: Chimle. M. D. 11 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Ex.: Sort the given list in ascending order using selection sort method
write all passes.
- Consider unsorted list DATA contains 8 elements as follows,
42 23 74 11 65 12 10 05

Ans: Following table shows selection sort algorithm to DATA .

- Observe that, LOC gives the location of the smallest element among
DATA[PASS], DATA[PASS + 1], ……, DATA[N] during pass … pass.
- The Circle elements indicate the elements which are to be interchange
DATA[LOC] with DATA[PASS].

Pass DATA DATA DATA DATA DATA DATA DATA DATA

(1) (2) (3) (4) (5) (6) (7) (8)
Pass 1,
42 23 74 11 65 12 10 05
loc=8
Pass 2,
05 23 74 11 65 12 10 42
loc=7
Pass 3,
05 10 74 11 65 12 23 42
loc=4
Pass 4,
05 10 11 74 65 12 23 42
loc=6
Pass 5,
05 10 11 12 65 74 23 42
loc=7
Pass 6,
05 10 11 12 23 74 65 42
loc=8
Pass 7,
05 10 11 12 23 41 65 74
loc= 0
Sorted 05 10 11 12 23 41 65 74
List

By: Chimle. M. D. 12 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

• Algorithm for Selection Sort Method :

Procedure 2.1 : MIN (DATA, N, PASS, LOC)

Let DATA is a unsorted list with N element. This procedure
finds the location LOC of the smallest element among
DATA[PASS], DATA[PASS + 1], …….., DATA[N].
Step 1: [Initialize variable MIN and LOC]
set MIN DATA[PASS] and
LOC PASS
Step 2: Repeat for J PASS + 1 to N
Step 3: If MIN > DATA[J], then
Set MIN = DATA[J] and LOC = J
[End of step loop]
Step 4: Return.

Algorithm 2.1 : SELECTSRT (DATA, N, LOC, TEMP)

Let DATA is a linear array with unsorted element with N
element. LOC sorted location, TEMP is temporary variable.
This algorithm perform selection sort method.
Step 1: Repeat step 2 & 3
For PASS =1 to N – 1
Step 2: Call MIN (DATA, PASS, N, LOC)
Step 3: [Interchange DATA(PASS) and DATA(LOC)]
Set TEMP = DATA[PASS]
DATA[PASS] = DATA[LOC]
DATA[LOC] = TEMP

By: Chimle. M. D. 13 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[End of step 1 loop]

Step 4: [Finished] Exit.

• Complexity of Selection Sort Method :

- In this algorithm, there are N – 1 comparisons are perform during
pass 1 to find first smallest element, there are N – 2 comparisons
during pass 2. Find the second smallest element and so on.
- Thus the number of comparisons performed during whole method
execution is determine by complexity function F(N) as :
F(N) = (N – 1) + (N – 2) + …….. + 2 + 1
N(N – 1)

i.e. =2 = 0(N2) hence,

F(N) = 0(N2).
- This means that time required execute selection sort algorithm
proportional to N2.
- Here N is a input element.

2.3 :Insertion Sort Method :

- Suppose an array DATA with N elements DATA[1], DATA[2], …….,
DATA[N] is in memory.
- The insertion sort algorithm scan DATA from DATA[1] to DATA[N],
inserting each element DATA[PASS] into it’s a proper position in the
previously sorted sub array DATA[1], DATA[2],
…………..DATA[PASS–1], i.e. :

Pass 1 : DATA[1] by itself is trivially sorted

By: Chimle. M. D. 14 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Pass 2: DATA[2] is inserted either before or after DATA[1], so that

DATA[1] , DATA[2] is sorted.

Pass 3: DATA[3] is inserted into its proper place in

DATA[1],DATA[2], that is, before DATA[1], between DATA[1] and
DATA[2], or after DATA[2], so that DATA[1] , DATA[2], DATA[3] is
sorted.
|
|
|

Pass N: Insert DATA[N] into its proper place in DATA[1], DATA[2],

…. , DATA[N–1]. So that DATA[1], DATA[2], …. , DATA[N–1]is sorted.
- After completion Pass N list get sorted in ascending order.

Ex.: Sort the given list LA in ascending order by using insertion sort
method and shows all passes.
LA={20,50,70,55,15,10,25}
Ans: Following table shows insertion sort algorithm.
The circle element indicate Pass.
The arrow indicate proper place for element.

By: Chimle. M. D. 15 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Algorithm 2.3 : INSERTIONSRT (DATA, N, PASS, PTR, TEMP)

DATA is a linear array with N unsorted element. PASS variable
is used to shows the passes. PTR is a pointer variable and
TEMP is temporary variable. This algorithm perform insertion
sort method.
Step 1: [Initialize sentinel element]
Set DATA[0] = –
Step 2: Repeat step 3 to 5
For PASS = 2 to N
Step 3: Set TEMP = DATA[PASS] and
PTR = PASS – 1
Step 4: Repeat while (TEMP < DATA[PTR])
(a) DATA[PTR + 1] = DATA[PTR]

By: Chimle. M. D. 16 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[Moves element Forward]

(b) Set PTR = PTR – 1
[End of step 4 loop]
Step 5: [Insert element in proper place]
Set DATA[PTR + 1] = TEMP
[End of step 2 loop]
Step 6: Return.

• Complexity of Insertion Sort Method :

- The number F(N) of comparisons in the insertion sort algorithm can
be easily computed.
- First of all the worst case occurs when the array DATA is in reverse
order and the linear loop must use the maximum number PASS – 1 of
comparisons.
Hence, F(N) = 1 + 2 + ………. + (N – 1)
N(N – 1)

= 2 = 0(N2)
- Further more, one can show that on the average their will be
approximately comparisons in the linear loop.
- Accordingly for the average case,
N–1

F(N) = + +……….. + 2

–
N(N 1)

= 4

= 0(N2)

2.4 Linked List :-

- A linked list is a linear collection of data elements, called ‘nodes’.
- Here, the linear order is obtained by using pointers.
- A linked as also called as ‘one–way–list’.

By: Chimle. M. D. 17 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Every node of linked list is get divided into two fields.

1. First field is INFO which is used to store information of the
element.
2. Second field is LINK or next pointer field which is used to store
address of the next node in the list.
- Following figure shows a linked list with four nodes.
START

Next pointer field of second node.

Information field of second node.

Fig. Linked List with 4 nodes.

- It is clear that, in above fig. each node is pictured with two fields.
- The left field use the actual information, and right field use store the
address of the next node.
- Arrows are used to show the order of the nodes.
- The next pointer or LINK field of the last node contain a invalid
address called ‘null pointer’.
- The null pointer (X) is used to shows the end of the list.
- The linked list has also a list pointer variable called START which
contains address of first node in the list.
- The starting address o the list which is sorted in START is used to
traverse the whole linked list.
- Here if the linked list has no any node then such a list is called ‘null
list’ or ‘empty list’. And it is denoted by the null pointer assigning to
START i.e. START = NULL.

By: Chimle. M. D. 18 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

2.5 Representation of Linked List in Memory :-

- Suppose list be a linked list for the storage of such a list in memory it
requires linear arrays.
- One is a general array set “INFO”, another pointer array set “LINK”.
- An array INFO[K] will contain the information part and an array
LINK[k] will contain the address of the next element of the list.
- In linked list, a pointer variable START is used to store starting
location of the list. NULL is used to show the end of the list.
- If the subscripts of an array INFO & LINK will be positive integer, then
NULL = 0 used to show end of the linked list.
- Here, the nodes of the linked list doesn’t need occupy the adjacent
dement in the array INFO & LINK.
- Also more than one linked list may be maintain in the same linear
array but only by storing the static address of the second list. Another
pointer variable set START = 1 & so on.
- Ex.: suppose we want to store the words :- BCA–SEM 3 using a linked
list.
- The linked list representation of these words is as follows.

START

B C A S E M 5

- Internal representation of linked list is as follow,

By: Chimle. M. D. 19 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

START INFO LINK

1
2 3
3 B 0
4 E
6
5 A
6 C 8
7 – 7
8 M 5
9 5
9
2
4

- The actual list can be obtain as follows,

START = 3 INFO[3] = B
LINK[3] = 6 INFO[6] = C
LINK[6] = 5 INFO[5] = A
LINK[5] = 7 INFO[7] = –
LINK[7] = 9 INFO[9] = S
LINK[9] = 4 INFO[4] = E
LINK[4] = 8 INFO[8] = M
LINK[8] = 2 INFO[2] = 3
LINK[2] = 0

- The NULL value, so that the list has ended.

2.6 Searching Linked List :

- Let LIST is a linked list stored in memory using linear array INFO and
pointer array LINK.

By: Chimle. M. D. 20 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- In data structure searching operation is used to find the location LOC

of an ITEM in a given list.
- As the LIST may or may not be sorted in memory.
- Hence there are two searching algorithm are used to find the location
LOC of a node where an item appear in the list.
- These algorithms are, 1. LIST is unsorted.
2. LIST is sorted.

1. LIST is Unsorted :
- An algorithm to search an ITEM in unsorted linked List.
- Let LIST is a unsorted linked list stored in memory with INFO and
LINK.
- START is a pointer variable which is used to stored initial address of
linked list.
- Then one searches for ITEM in list by traversing to the list using
pointer variable PTR and comparing ITEM with the contains
INFO[PTR] of each node, one by one of list.

- Before we update the pointer PTR by, PTR LINK [PTR] - We

require to tests.
- First we have to check to see weather we have reached the end of the
list i.e. PTR = NULL.
- If not then check INFO[PTR] = ITEM, search become successful.

Algorithm 2.4 : SEARCHULL (LIST,INFO, LOC, LINK, START, PTR,

ITEM)
Let given linked list is unsorted which stored in memory INFO
variable, LINK is a linked list and START is a starting pointer
variable. This algorithm search a location LOC of the node
where ITEM appear or set LOC = NULL. Here PTR is a local

By: Chimle. M. D. 21 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

pointer variable which indicate the node which is going to

process.
Step 1.: [Initialize pointer PTR]
set PTR START
Step 2.: Repeat step 3 while
PTR NULL
Step 3.: [Is ITEM present at node PTR?]
If ITEM = INFO[PTR], then:
Write : “Successful search” and
Set LOC= PTR and Exit.
Else
[Now point to the next node]
Set PTR = LINK[PTR]
[End of if structure]
[End of step 2 loop]
Step 4.: write “Unsuccessful search” and
Set LOC = NULL
Step 5.: [Finished] Exit.
2. LIST is Sorted :
- An algorithm to search an ITEM in sorted linked List.
- Suppose list is sorted linked list stored in memory.
- This algorithm makes search for the location LOC of an ITEM in LIST
by traversing list using pointer variable PTR.
- Here while traversing an ITEM of information is compare with each
node of the list successful.
- Here traversing is stop when, 1. ITEM is appear at location PTR.
2. ITEM < INFO[PTR] or.
3. There is no further element to make comparison i.e. PTR =
NULL.

By: Chimle. M. D. 22 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Algorithm 2.5 : SEARCHULL (INFO, LOC, LINK, START, PTR, ITEM)

Let given linked list is sorted which stored in memory with
INFO and LINK. START is a starting pointer variable and PTR
is a local pointer variable which indicate the node which is
going to process. This algorithm finds the location LOC of the
node where ITEM first appear in the list or set LOC = NULL.

Step 1.: [Initialize pointer PTR]

set PTR START
Step 2.: Repeat step 3 while
PTR NULL
Step 3.: [Is ITEM present at node PTR?]
If ITEM = INFO[PTR], then Write
: “Successful search” and Set
LOC= PTR and Exit.
Else if ITEM < INFO[PTR], then
Write “ITEM is out of range” and
Set LOC = NULL and Exit
Else
[update PTR]
Set PTR = LINK[PTR]
[End of if structure]
[End of step 2 loop]
Step 4.: write “Unsuccessful search” and
Set LOC = NULL
Step 5.: [Finished] Exit.

• Complexity for Searching Algorithm :-

By: Chimle. M. D. 23 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1. Sorted Searching Algorithm Complexity :-

a. The complexity of this algorithm is set as complete searching
algorithm for sorted linear array.
b. A sorted linear array we can apply binary search whose running
time is propositional to log2N.

2. Unsorted Searching Algorithm Complexity :-

a. The worst case running time is propositional to the number N of
elements in list and the average case running time is
approximately propositional to N/2.

2.7 Memory Allocation and Garbage Collection :-

1. Memory Allocation :-

- Let a linked list stored in memory using linear array INFO and pointer
array LINK.
- The linked representation of a linked list as follows,

STAR

15 50 10 20 35

START
INFO LINK
1 1 20 4
2 15 5
2
3 10
3 1
4 35
4 5 50 0
5 3

By: Chimle. M. D. 24 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- From above representation, it is clear that one can’t insert any

element (node) in given linked list because there is no any memory
space present.
- Now suppose an element 20 is deleted from the list.
- We know in linked list deletion is take place only by changing.
- The link address of previous node.
- Here a previous node of node 20 is 10.
- Hence, in the LINK field of the node 1 10 will contain the address of
node 35, if one deleted node 20.
- Now though the element 20 is deleted still it is present physically in
the memory cell at location one.
- Hence, one can’t insert new element in this linked list.
- To overcome above problem, some mechanism is used which will
collects, memory space of deleted node are then available for future
use.
- A mechanism which performs such function is known as “Memory
Allocation”.
- In case of linked list, a memory allocation is perform by describing
another special list in the same arrays INFO and LINK.
- Here all the unused memory cells and the cells of deleted nodes will
be linked list by this special list.
- A variable AVAIL which is pointer of type of used to store beginning
location of the special linked list and invalid address NULL is used to
indicate the end of the special list.
- The special list is also known by the list of available space or free
storage list.
- A data structure with frequently will be denoted by writing : LIST
(INFO, LINK, START, AVAIL)

By: Chimle. M. D. 25 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Ex.: Consider a list of books is stored in linear array book & LINK then
available memory space in the linear array book may be linked as :

AVAIL
INFO LINK
1 1 DBMS 4
2
START
2 6
3 BASIC
3 5
4 HTML
4 5 C++ 0
6 5 1
6 0

- In above fig. AVAIL indicates first location i.e. 2 is the available space,
next 6 is available space.

2. Garbage Collection :

- It is mechanism or technique which perform the collection of all

deleted space on to the free storage list.
- The kernel of operating system such function in computer.
- To make such collection operating system to the following two steps
:
▪ Computer traverses all lust or memory cell and apply tags
(margin) to the memory cell which are currently in use.
▪ Then computer check all memory cells and collects all untag
memory cells on to the free storage list.
- Generally the garbage collection is take place n two cases:

▪ If there is no memory space at all left in the free storage list.

▪ When CPU has no any work i.e. CUP in idle state.

By: Chimle. M. D. 26 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

• Overflow and Underflow :

1. Overflow :
a. Overflow refers the situation one wants to insert the data into the
data structure, which is already filled.
b. This situation can be handle by printing message “OVERFLOW”.
c. In case of linked list overflow will occur when AVAIL = NULL.

2. Underflow :
a. Underflow refers a situation where one wants to delete data from a
empty data structure.
b. This situation can be handle by printing message “UNDERFLOW”.

c. In case of linked list underflow will occur when START = NULL.

2.8 Insertion and Deletion in linked list.

Insertion into Linked List:
- Suppose a linked list is stored in memory in the form of ,
- LIST (INFO, LINK, START, AVAIL)
- A variable ITEM contains new information that to be added into the
list.
- The node in the AVAIL list is used for insertion by using the following
steps :
a. Check for available spaces in AVAIL list. If AVAIL = NULL then
print a message “OVERFLOW”.
b. Removing first node from the AVAIL list and store at pointer
variable NEW as :

By: Chimle. M. D. 27 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Set NEW = AVAIL and AVAIL = LINK [AVAIL]

c. Place a new information ITEM into the new node as, Set
INFO[NEW] = ITEM.

- The schematic or systematic diagram as follow:

AVAIL STAR Free – storage list

ITEM

- Algorithm which insert nodes into linked list come up in various

situation.
a. Insert a node at the beginning of the list.
b. Insert a node after the node with a given location.
c. Insert a node into a sorted linked list.

1. An algorithm to insert ITEM at the beginning of the linked list.

STAR

NEW

ITEM

Fig. Insertion at the

beginning at a linked list

Algorithm 2.6 : INSERTBLL (INFO, AVAIL, NEW, LINK, START, ITEM)

By: Chimle. M. D. 28 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Let LINK is a linked list with memory array INFO and LINK.
START and AVAIL is a link pointer variable which indicates
address of beginning with actual linked list. Here NEW is a
local pointer variable used to store address of node. This
algorithm perform insert an ITEM of information at the
beginning of the given linked list.

Step 1. : [Is Overflow ?]

If AVAIL = NULL, then
Write : “OVERFLOW” and Exit
[End of if structure]
Step 2. : [Remove first node from AVAIL]
Set NEW = AVAIL and
AVAIL = LINK[AVIAL]
Step 3. : [place ITEM into NEW node]
Set INFO[NEW] = ITEM
Step 4. : [link NEW node at the beginning]

Set LINK[NEW] START

Step 5. : [change START to the NEW node]
Set START = NEW
Step 6. : [Finished] Exit.

2. An algorithm to insert an ITEM after given node. (After given

location.) ITEM = 90, LOC = 3.

STAR

By: Chimle. M. D. 29 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

10 05 08 40

AVAIL

ITEM

Fig. Insertion after given lolinked list. cation in

Algorithm 2.7 : INSERTLOC (INFO, START, ITEM, LOC, AVAIL,

LINK, NEW)

Let linked list is stored in memory with INFO and LINK. START
and AVAIL is a LINK pointer variable which indicate the
address of beginning actual linked list. This algorithm perform
to insert ITEM after the given location LOC.
Otherwise is LOC = NULL insert at beginning.

Step 1.: [Is Overflow ?]

If AVAIL = NULL, then
Write : “OVERFLOW” and Exit
[End of if structure]
Step 2.: [Remove first node from AVAIL]
Set NEW = AVAIL and
AVAIL = LINK[AVIAL]

By: Chimle. M. D. 30 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Step 3.: [place ITEM into NEW node]

Set INFO[NEW] = ITEM
Step 4.: If LOC = NULL, then
[Insert as first node]
Set LINK[NEW] = START and
Set START = NEW
Else:
[Insert node after a given location]
Set LINK[NEW] = LINK[LOC] and
LINK[LOC] = NEW
[End of if structure]
Step 5.: [Finished] Exit.

3. Algorithm to insert an ITEM into a sorted linked list.

- Suppose list is a sorted linked list stored in memory using linear array
INFO and LINK.
- When an ITEM is to be inserted into a sorted linked list, then it must
be satisfy the condition.
INFO[A] < ITEM < INFO[B]. Where A and B are two successive
nodes.
- To insert a NEW ITEM into a sorted linked list, one must know the
required location LOC of a node after which ITEM is to be inserted.

Procedure to find location LOC of a node is a sorted linked list, ITEM = 20.

LOC P PTR
STAR

9 10 15 25 30

- This procedure find location LOC of a node A. here value is < ITEM.

By: Chimle. M. D. 31 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The location is search by traversing a list using point variable PTR

and comparing ITEM with INFO[PTR].
- Here, while traversing the location of precidy node is save using a
pointer variable LOC P as shown in above figure.
- The pointer variable LOC and PTR is updated as,
Set LOCP = PTR and
PTR = LINK[PTR]
- Here, the traversing get stop as soon as ITEM < = INFO[PTR]
- If the above condition become true then this procedure set value of
LOC as,
LOC = LOCP and return.
- Also if given list is empty or ITEM < INFO[START] then it
Set LOC = NULL and return.
Procedure 2.2 : FINDLOCLL (INFO, LINK, START, ITEM, LOC)

Let this procedure find the location LOC of a node in a sorted

linked list such that INFO[LOC] < ITEM or Set LOC = NULL.
Here, PTR and LOC are the actual local pointer variable used to
store address of a node which is going to process and address
of previous node respectively.

Step 1.: [Is Underflow ?]

If START = NULL, then
Write “UNDERFLOW (empty list)”, and
LOC = NULL and Exit.
[End of if structure]
Step 2.: [Is ITEM < Starting element ?]
If ITEM < INFO[START], then
Set LOC = NULL and return

By: Chimle. M. D. 32 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

[End of if structure]
Step 3.: [Initialize LOCP and PTR]
Set LOCP = START and
PTR = LINK[START]
Step 4.: [Make search]

While PTR NULL

Step 5. : [check ITEM and INFO(PTR)]
If ITEM < INFO[PTR], then
LOC = LOCP and return
Else
[update LOCP and PTR]
Set LOC = PTR and
PTR = LINK[PTR]
[End of if structure]
[End of step 4 loop]
Step 6. : Set LOC = LOCP
Step 7.: Return. [Return to the point of call]

4. An algorithm to insert ITEM at location in sorted linked list.

Algorithm 4.8 : INSERTSLL (LINK, INFO, LOC, START, PTR, AVAIL,

ITEM)

Let given linked list is a sorted linked list which is stored in

memory using a linear array INFO and LINK. This algorithm
insert an ITEM into given linked list.

Step 1.: [use procedure 4.1 to find location LOC]

Call FINDLOC (INFO, LINK, START, LOC, ITEM)

By: Chimle. M. D. 33 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Step 2.: [use algorithm 4.7 to insert ITEM after given

location]
Call INSERTFLOC(INFO, LINK, START, ITEM)
Step 3.: [Finished] Exit

Deletion From Linked List :

- LIST is a linked list with a node X between node A and node B as

shown in following figure.

STAR
Data List
Node A
Node B

10 05 50 20

AVAIL

Free Storage List

- We know in linked list deletion take place as soon as the next pointer
field of node A point to node B.
- When node X is deleted from the list its used memory space is
immediately return to the beginning of the AVAIL list shown in above
figure.
- From figure it is observe that three pointer fields are changes as
follows,
▪ The next pointer field of node A to node B, here node X
previously pointed.
▪ The next pointer field of X now points to the first node in he
free storage list.
▪ AVAIL now points to the deleted node X.

By: Chimle. M. D. 34 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- When deletion operation occurs, their must be to cases consider :

▪ If deleting the node X is the first node in the list then START
will point node B.
▪ If deleting node X is the last node in the list, then the LINK
pointer field of node A will contain a NULL pointer.

1. An algorithm delete a node following a given node :

- Deletion algorithm will return the memory space of the deleted node
X to the beginning of the AVAIL list.
- Here LOC is a location of the deleted node X as,
LINK[LOC] = AVAIL and AVAIL = LOC
- These two operations are shown in following figure.

LOC

Node X

AVAIL

Free Storage List

2. An algorithm check to see if there is node in the list if not i.e.
START = NULL then print message “Underflow”.

Algorithm 4.9 : DELNODE (INFO, LINK, AVAIL, LOC, START, LCOP)

Let LIST be a linked list stored in memory with INFO and LINK.
LCO is a location of Node X which will delete and LOCP is a
location of the node precidy X. When X is the first node then
LOCP = NULL. This algorithm delete the node X with location
LOC.

By: Chimle. M. D. 35 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Step 1.: If LOCP = NULL, then

Set START = LINK[START]
[Delete first node]
Else
Set LINK[LOCP] = LINK[LOC]
[Delete node X]
[End of if structure]
Step 2.: [Insert deleted node at the AVAIL list]
Set LINK[LOC] = AVAIL and
AVAIL = LOC
Step 3.: [Finished] Exit.

2. An algorithm delete a node with a given item of information.

- Let LIST be a linked list in memory.

- Suppose we are given an ITEM of information and we want to delete
from the LIST.
- The first node which contain ITEM one need to node the location of
the node preceding location etc.
- If the node X is first node then set LOCP = NULL an ITEM doesn’t
appear in the LIST at that time set LOC = NULL.
- Traverse the LIST using the pointer variable PTR and while
traversing variable PTR and while traversing compare ITEM with
INFO[PTR] at each node, while traversing keep track of the location
of the preceding node by using pointer variable SAVE.
- Here SAVE & PTR updated as,
SAVE = PTR & PTR = LINK[PTR]

- Traversing continues as long as INFO[PTR] ITEM.

- Following is a procedure which points find location LOCP and LOC.

By: Chimle. M. D. 36 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Procedure 4.2 : FINDLOCPLOC (INFO, LINK, START, PTR, LOCP, ITEM,

LOC)

This procedure find the location LOC of the first node X which
contains ITEM and location LCOP of the preceding node X. If
ITEM doesn’t appear in the LIST, then the procedure set LOC =
NULL and if ITEM appears in the first node then it sets LCOP =
NULL.

Step 1.: [Is list empty ?]

If START = NULL, then
Write “List is Empty”(Underflow), and
Set LOCP = NULL and
LOC = NULL and
Return
[End of if structure]
Step 2.: [Is ITEM present at first node of the list?]
If INFO[START] = ITEM, then
Write “Successful search”, and
Set LOC = START and
LOCP = NULL and Return
Step 3.: [Initialize pointer SAVE and PTR]
Set SAVE = START and
PTR = LINK[START]
Step 4.: Repeat step though 5

While PTR NULL

Step 5. : [Is item present at node PTR?]
If INFO[PTR] = ITEM, then
Write “successful search”, and

By: Chimle. M. D. 37 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Set LOCP = SAVE and

LOC = PTR and Return
Else :
[update pointer SAVE and PTR]
Set SAVE = PTR and
PTR = LINK[PTR]
[End of if structure]
[End of step 4 loop]
Step 6. : [Set LOCP & LOC]
Write “Unsuccessful search”
Set LOCP = NULL and
LOC = NULL
Step 7.: Return. [Return to the point of call]

Following is an algorithm which delete node X (node n) with

ITEM of information.

Algorithm 4.10 : DELITEM (INFO, LINK, LOC, START, LCOP)

This algorithm deletion from linked list the first node X which
contain the ITEM of information.

Step 1.: [Use procedure 4.2 to find location LOC of X its

preceding node LOCP]
Call FINDLOCPCOL[INFO, LINK, START, LOC,
LOCP]

Step 2.: [Is underflow ?]

If LOC = NULL, then
Write “UNDERFLOW”, and

By: Chimle. M. D. 38 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Exit
Step 3.: [Is ITEM of node present at the beginning the list ?]
If LOCP = NULL, then
[Delete node]
Set START = LINK[START]
[End of if structure]
Step 4.: [Delete node from location LOC using preceding
node LOCP]

Set LINK[LOCP] = LINK[LOC]

Step 5.: [Insert deleted node at the begin of AVAIL list]
Set LINK[LOC] = AVAIL and

AVAIL LOC
Step 6.: [Finished] Exit.

By: Chimle. M. D. 39 / 39
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

3. Stacks, Queues, Recursion

TOP
3.1 Stacks :-

Disk

Sprig Container

Figure: Stack

- Stack is a restricted data linear data structure of the list of elements

in which an element may be inserted or deleted only at one end called
the top of the stack that means the last ITEM to added to a stack is a
first ITEM to be remove.
- Stack are also called “LIFO” (Last In First Out) - Also the stack is

known by “Piles” and ‘push down list’.

- There are two basic operation associated with stack.
1. Push.
2. POP.
1. Push :- This operation is use to insert an element into a stack.
2. POP :- This operation is use to remove an element from the top of
the stack.

- Ex.: Suppose the following five elements are push in order on to an

empty stack.
AA BB CC DD EE
- Here the notational design of stack for above element is given as,
Stack : AA BB CC DD EE
- Similarly the graphical representation or above stack on element is
given as,

By: Chimle M. D. 1 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

STACK STACK
1 N AA .
Top 5 2 BB N–13 Top .
CC 5 EE
DD 4 4 DD
EE 5 3 CC
N–1 2 BB
N 1 AA
Fig.(a)

Fig(b)

Top 5

1 2 3 5 6 47 8
AA BB CC D EE
D
STACK Fig (c) N– N
1

- An AVAIL list of the linked list is the best example of stack.

- Here in AVAIL list the nodes where removed or inserted only from /
at beginning of the AVAIL list.

Use of Stack :-
Stack are used to indicate the order of it processing of data when
certain steps of the processing are postponed until other condition
are fulfill.

By: Chimle M. D. 2 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

3.3 Memory Representation of Stack (Array Representation of

Stack):-
- Stack are representation is the computer memory by a one way linked
list or linear array.
- By default stack is represented using a linear array say STACK.
- The pointer variable TOP and MAXSTEK used to indicate the TOP
element of the stack and the maximum length of stacks.
- The condition TOP = 0 or TOP = NULL will indicate that the stack is
empty.
- Ex.: Consider stack of maximum length 9 with 4 elements.
STACK
1 2 3 4 5 6 7 8 9
FD SD CD V
D

Top MAXSTK

- In above fig. TOP = 4 indicate that stack has four elements and
MAXSTK = 9, which gives the maximum length of this stack.
- Here the location 5, 6, 7 indicate blank places for the new ITEM.

3.4 Some Arithmetical Expressions :

By: Chimle M. D. 3 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- Let x is an arithmetic expression which include constant and

operation.

- The binary operations , *, /, +, &, – may have following levels of

precedence (order of execution.)

1. Exponentiation ( )
2. Multiplication (*) and division (/)
3. Addition (+) and subtraction (–)
- In any parenthesis expression be operators of same precedence level
are executed from left–to–right.
- Ex.: Consider the following parenthesis are arithmetical expression.

x = (3 3+4*2 3 – 20 / 5)
=3 3+4*2 3–4
= 27 + 4 * 8 – 4
= 27 + 32 – 4
= 59 – 4
= 55

- The above expression x will be evaluable according to operator

preceding level as:

i. First evaluate the highest precedence level i.e. exponent ( ) to

obtain.
x = 27 + 4 * 8 – 20 / 5
ii. Then evaluate the next highest precedence level i.e.
multiplication & division from left to right to obtain,
x = 27 + 32 – 4
iii. All last evaluate the lowest precedence level i.e. addition and
subtraction from left–to–right to obtain,
x = 55

By: Chimle M. D. 4 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

iv. It is observe that, any expression to evaluate it is traversed three

times according to the preceding levels of the operators. Polish Notation :-

- Generally in arithmetic expression the operator symbol is placed in

between two operands. This is called Infix notation.
Ex.: A + B, C – D, E * F, G / H.
- By using this notation either parenthesis or some operator
precedence convention the expression.
(A + B) * C and A + (B *
C) are different.
Ex.: Suppose A = 2, B = 5, C = 3 then
= (2 + 5) * 3 = 2 + (5 * 3)
= 21 = 17
- Polish notation is a notation in which the operator symbol is placed
before its two operand.
Ex.: +AB, – CD, *EF, /GH
- This notation is also called Prefix notation.
- This notation is invented by polish mathematician Jan Lukasirewicz.
- In this notation brackets ([]) are used to indicate a partial translation
of the infix expression into polish notation.

Infix Notation Partial Polish

Notation Notation
a. (A + B) * C [+AB] * C * + ABC
b. A + (B * C) A + [* BC] + A * BC
c. (A + B) / (C (+ AB) / (– / + AB – CD
– D) CD)

- Reverse polish notation in which operator symbol is placed after its

two operands.

By: Chimle M. D. 5 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

AB +, CD –, EF* , GH /. Also this notation is called Postfix

notation.
- Here, the brackets are also used to indicate only postial translation.
- Computer solve an arithmetic expression written in infix notation
using two steps.
i. It converts the infix notation into postfix notation.
ii. It evaluate the postfix notation.
- For above both steps stack is main storage structure which is used to
give task.

3.5 Recursion :-
- Suppose P is a procedure containing either a call statement to itself
or call statement to a second procedure that may result in a call
statement back to the original procedure P.
- Then P is a recursive procedure.
- The recursion is mainly divided into two parts.
1. Recursive procedure.
2. Recursion function.

1. Recursive Procedure :-

- A procedure P is set to be recursive procedure if containing either a

call statement to a second procedure that may result in a call
statement back to the original procedure P.
- Here main program cannot run independently.
- Following are the two properties :

By: Chimle M. D. 6 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

1) There must be certain criteria called base criteria for which

the procedure does not call itself.
2) Each time the procedure does not call itself, it must be
closer to the base criteria.
2. Recursion Function :
- Similarly a function set to be recursively define.
- If the function definition refers to itself.
- Again in order for the definition not to be circular, it must have the
following two properties:
1) There must be certain arguments, called base value. For
which the function does not refer to itself.
2) Each time the function does refer to itself, the argument of
a function must be closer to a base value.
- Recursion function with these two properties is also set to be well
defined.

- Following are the examples :

I. Factorial Function.
II. Fibonacci Sequence. I. Factorial
Function :

- The product of positive integer from one (1) to n inclusive is called “n

– factorial” and usually denotes by n!.
N! = 1 * 2 * 3 * …………….. (n – 2) * (n – 1) * n;
- It is also convenient to define 0! = 1, 1! = 1, 2! = 2, 3! = 6.
- The function is defined for all non-negative integer n i.e. n! = n *(n –
1)!
- Following is an algorithm for calculating factorial recursively.
Algorithm 5.5 : FACTORIAL (FACT, N)

By: Chimle M. D. 7 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Let, N is a numerical value and FACT is a variable used to store

factorial of N. This algorithm calculate factorial of N.

Step 1. : [Is N null?]

If N = 0 OR N=1, then:
Set FACT = 1 and Exit.
[End of if structure]
Step 2. : [Initialize FACT]
Set FACT = 1
Step 3. : [Call factorial recursively]
Call FACTORIAL (FACT, N-1)
Step 4. : Set FACT = N * FACT Step 5. : [Finished] Exit.
II. Fibonacci Sequence :
- Fibonacci sequence as follows, 0, 1, 1, 2, 3, 5, 8, 13, …………. i.e. F 0 = 0,
F1 = 1, and each succeeding term is the sum of the two preceding
terms.
- An algorithm for finding the 17th term of the Fibonacci sequence as
follow.
Algorithm 5.6 : FIBONACCI (FIB, N)
Let N is variable for number, FIB is a variable which is stored
sequence. This algorithm perform to find the Fibonacci
sequence.

Step 1. : If N = 0, or N = 1 then
FIB = 1 and Exit
[End of if structure]
Step 2. : Call FIBONACCI (FIB.A, N – 2)
Call FIBONACCI (FIB.B, N – 1)
Step 3. : set FIB=FIB.A + FIB.B
Step 4. : [Finished] Exit.

By: Chimle M. D. 8 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

3.6 Queue :-
- A queue is a linear list element of in which deletion can take place
only at one end called the front and insertion can take place only at
the other end, called the rear.
- The term ‘front’ and ‘rear’ are used to describing linear list only when
it is implemented as a queue.
- Queue are also called FIFO (First In First Out) or FCFS (First Come
First Serve), because element in a queue will be first element out of
the queue.
- In other word the order in which element enter a queue is the order
in which they leave.
- Following figure shows the queue of people waiting for bus.
BUS Stop

Rear- Front-
End End

Fig: Queue waiting for BUS

- The people waiting a BUS stop, each new person to comes takes
his/her place at the end of the line and when the bus come the front
in line board first line.

• Memory Representation of Queue :

- Queue may be represented in the computer using one way list or
linear array.
- A linear array QUEUE and two pointer variables FRONT and REAR
that containing the location of front element and rear element of the
queue.

By: Chimle M. D. 9 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- The condition front is equal to NULL will indicate FRONT = NULL.

- The queue is empty (underflow).
- Ex.: consider a list of four elements, AA, BB, CC, DD.
- The above element will be stored in a memory a linear array queue
with N element as follow.
Queue:
AA BB CC DD …
1 2 3 4

FRONT = 1 REAR = 4
- Similarly when an element is array in the queue the value of rear is
increased by one as REAR = REAR +1.
- Hence, after increasing one element queue become.

AA BB CC DD EE
1 2 3 4 5

FRONT =1 REAR =5
- When an element is deleted the value of FRONT increased by one as
,

BB CC DD EE
1 2 3 4 5

FRONT = 2 REAR = 5
- It is REAR that after N insertion, the REAR element of the queue will
be occupy.
- Queue of (N), it means that queue will occupy last port of array.

• Insertion and Deletion :

By: Chimle M. D. 10 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

I] Insert ITEM in QUEUE:

- The following is an algorithm to insert ITEM at the REAR of QUEUE.

Algorithm 5.7 : QINSERT (QUEUE, N, ITEM, FRONT, REAR) Let QUEUE

is a linear array with N element. FRONT and REAR is a pointer
variable indicate FRONT and REAR element. This algorithm
perform to insert ITEM of information at the REAR of QUEUE.

Step 1. : [Is QUEUE Overflow?]

If FRONT = REAR = N, then
Write “OVERFLOW” and Exit.
[End of if structure]
Step 2. : [FIND new value for REAR]
If FRONT = NULL, then
Set FRONT = 1 & REAR =1
Else if REAR = N, then:
Set REAR = 1
Else
Set REAR = REAR + 1
[End of if structure]
Step 3. : [Insert new ITEM]
Set QUEUE[REAR] = ITEM
Step 4. : [Finished] Exit.

II] Deleting ITEM from QUEUE :-

Algorithm 5.8 : QDELET (QUEUE, N, ITEM, FRONT, REAR)

Let QUEUE is a linear array with N element. FRONT and REAR
is a pointer variable indicate FRONT and REAR element. This

By: Chimle M. D. 11 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

algorithm perform to delete an ITEM of information at the

FRONT of QUEUE.

Step 1. : [Is QUEUE empty?]

If FRONT = NULL, then
Write “UNDERFLOW” and Exit.
[End of if structure]
Step 2. : [Delete FRONT and store in ITEM]
Set ITEM = QUEUE[FRONT]
Step 3. : [QUEUE has only one element to start]
If FRONT = REAR, then
Set FRONT = NULL and
REAR = NULL
Else if
FRONT = N, then
Set FRONT = 1
Else
FRONT = FRONT + 1
[End of if structure]
Step 4. : [Finished] Exit.

3.7 De-Queue (Double Ended Queue) :-

- De-queue is a linear list in which elements can be added or the
remove at either end but not in the middle.
- The term de-queue is a contradicting if the name double ended queue.
- There are various way of representing,
- A de-queue is a computer unless it is otherwise stated or implied.

By: Chimle M. D. 12 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- We will assume our de-queue is maintain by a circular array dequeue

with pointer left and right, which point to the two ends of the de-
queue.
- We assume that the element extended from the left end to the right
end in the array.
- Following are the two de-queue in which in diagram.
- Each with four element maintain in an array with N = 9 memory
location.
- The condition LEFT = NULL will indicate de-queue is empty.
-
DE-QUEUE
AA BB CC D
D
1 2 3 4 5 6 7 8 9
LEFT = 4 fig. (a) RIGHT = 7

DE-QUEUE
YY ZZ W XX
W
1 2 3 4 5 6 7 8
LEFT = 7 fig. (b) RIGHT = 2

- There are two variation of DE-QUEUE.

1. Input restricted de-queue.

2. Output restricted de-queue. Which are intermediate between
de-queue & a queue.

By: Chimle M. D. 13 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

An input restricted de-queue is a de-queue which allows deletion at

both end of the list.
An output restricted de-queue is a de-queue which allows deletion at
only one end of the list but, allows insertions at both ends of the list.

3.8 Priority Queue :

- Definition : A priority queue is a collection of element such that each
element has been assign a priority and such that the order in which
element are deleted and processed comes from the following rules.
1. An element of higher priority is processed before any element
of lower priority.
2. Two elements with the same priority are processed according
to the order in which they were added to the queue.
- A priority queue is a time showing system.
- Programs of high priority are processed 1 st and programs with the
same priority from a standard queue.
- There are various ways of maintaining a priority queue in memory.
- We will discuss two of them.
1. Using one way list.
2. Using multiple queues.
1. Using one way list :-
- One way to maintain a priority queue in memory by means of one way
list as follow,
a. Each node in the list with contain three ITEMs of information.
An information field INFO, a priority number PRN and a link
number LINK.

By: Chimle M. D. 14 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

b. A node x precids node by in the list, when x has higher priority

than by or when both have the same priority but x was added
to the list before y.
This means that the order in the one way list corresponds to the order
of the priority queue.
Priority number in operate in the visual way.
- The lower priority number, the highest priority number.
- Ex.: Following fig. shows schematic diagram of priority queue with
seven elements.
START

AA 1 BB 2 CC 2 DD 4 EE 4 FF 4 GG 5

- Following fig. shows the way the priority queue may appear in
memory using arrays INFO, PRN, LINK.

START INFO PRN LINK

By: Chimle M. D. 15 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
- BB 2 6
7
- DD 3 4
EE 4 9
1
AA 1 1
2
3 CC 2 3
10
4
5 GG 5 0
AVAIL
6 FF 4 8
7 11

8
9 12

1
0 0

1
1
1
2

- The main property of the one way list representation of a priority

queue s that the element in the queue.
2. Array Representation of Priority Queue:
To maintain a priority queue in memory is to use a separate queue
for each level of priority.
Each such queue will appear in its own circular array and must have
its own pair of pointers, FRONT and REAR.
- In fact, if each queue is allocated the same amount of space, a two
dimensional array QUEUE can be used instead of linear array.

By: Chimle M. D. 16 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

- Following figure indicate this representation for the priority queue

and observed that FRONT [K] and REAR [K] contain front and rear
element respectively.
START

AA 1 BB 1 CC 2 DD 4 EE 4 FF 4 GG 5

FRON REA
1 2 3 4 5 6T R
1
2 2 2 1 AA
3 B
4 1 3 2 CC
B
5 0 0 3

5 D
- The new 1 4 FF EE
4 D
that
maintains 4 5 GG
the queue of
elements with priority number K.

By: Chimle M. D. 17 / 17
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

4. Tree
Tree is a non-linear data structure. This structure is
mainly used to represent data containing a hierarchy or
hierarchical relationship between elements.
Ex.: Records, tables & family tree.
❖ Binary Tree :
- A binary tree T is defined as a finite set of elements called nodes
such that:
a) T is empty (called null tree or empty tree), or
b) T contains a distinguished node R, called the root of T and
the remaining nodes of T form an ordered pair of disjoint
binary trees T1 & T2.
- If binary tree T does contain a root R, then two trees T1 and T2
are called left and right sub trees of R respectively.
- If T1 is non-empty then its root is called left successor of R.
- Similarly, if T2 is non-empty then its root is called the right
successor of R.
- Consider following binary tree:

By: Chimle M. D. 1 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

C
B

E
D H
G

F
K
J

- The binary tree T represents as follows,

i. T consists of 11 nodes, represented by the letters A to L,
excluding I.
ii. The root node of T is the node A at the top of diagram.
iii. A left downward slanted line from a node N indicates a left
successor of node N, and right downward slanted from N
indicated right successor of N.
- In above tree observe that,

a) B is a left successor and C is a right successor of node A.

b) The left sub tree of root A consists of the nodes B, D, E & F
and right sub tree of A consists of the nodes C, G, H, J, K &
L.
- Any node N in binary tree T may have 0, 1 & 2 successors. The
nodes with no successor are called Terminal nodes.

By: Chimle M. D. 2 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

- In above tree T, the nodes A, B, C, H has two successors & the

node E, J, has one successors and the node D, F, G, K & L has no
successor. Hence, these are terminal nodes.
- Binary tree T & T1 is said to be similar if they have similar
structure set.

A E

Fig. T Fig. T1
B F

D G H
C

The binary tree T and T1 is said to be copies if they are some

value of node.

❖ Tree Terminology :
In tree terminology, the relationship between the node of the tree is
described using three ways:
1.Family relationship.
2.Graph theory.
3.Horticulture concept.
1. Family Relationship :-
Suppose N is a node in T with left successor S1 and right successor S2.
Then N is called the parent (or father) of S1 and S2. S1 and S2 are called
left and right child of N.

By: Chimle M. D. 3 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

Furthermore, S1 and S2 are said to be siblings (brothers). Every node

N in a binary tree T, except the root, has a unique parent, called the
predecessor of node N.
If node L is child of node N, then node L is said/called descendant of
node N, and N is called an ancestor of L.
Here, node L may be left or right descendant of N according to location
in sub tree of root N.
2. Graph Theory :
A line drawn from a node N of T to a successor is called an edge and a
sequence of consecutive edge is called a path.
3. Horticulture Concept :-
A terminal node is called a leaf and a path ending in a leaf is called
branch.
Note: the depth (height) of a tree T is the maximum number of nodes
in branch of tree.
Ex.: Consider a following tree.

1
A

2
B C

3
G H

4 K
J

L 5

By: Chimle M. D. 4 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

The above tree has depth = 5.

❖ Types of Binary Tree :

1. Complete Binary Tree :
- The tree T is said to be complete binary tree if all its levels,
except possibly the last, have the maximum number of possible
nodes, and if all the nodes at the last level appear as left.

3
2

6 7
5
4

12
11
9 10
8

Consider above complete binary tree T12 with 12 nodes.

- In complete binary tree, children and parent of any node N can
be determined as follows,
1) A left child of node N is 2 N.
2) A right child of node N is 2 N + 1.
3) A parent of node N is integer of N / 2.
- Ex.: Consider a node 5 then its left, right child and parent may be
determined as follows,
1) A left child of node 5 is 2 5 = 10.

By: Chimle M. D. 5 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

2) A right child of node N is 2 5 + 1 = 11.

3) A parent of node 5 is integer [5/2] = 2.
2. Extended Binary Tree : 2 Trees :
- A binary tree T is said to be an extended binary tree or 2.
- If each node N has either 0 or 2 children.
- The nodes with 2 children are called internal nodes and the
nodes with zero children are called external nodes.
- In the diagram, these nodes are differentiated by drawing circles
for internal nodes and square for external nodes.
- Ex.: Consider following binary tree.

- The conversion of above binary tree into an extended binary tree

or 2-tree as follows.
-

By: Chimle M. D. 6 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

- This tree is an extended binary tree or 2-tree because the nodes

in original tree are here internal nodes, and new nodes are the
extended node.
- Ex.: A tree representation of any algebraic expression which
consist only binary operations.
- Consider following binary expression i.e. (x + j) / ((a – b) + z)
- A tree representation of above expression is a 2-tree which is as
follows,

+ +

z
x y –

a b

❖ Traversing Binary Tree:

- Traversing is one of the common data structure function which
is perform on a tree to process or visit each node of the tree
exactly once in a systematic manner.
There are mainly three standard way used to traverse given
binary tree T with root B.
- These three ways are:
1)Preorder Traversing.

By: Chimle M. D. 7 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

2) Inorder Traversing.
3) Postorder Traversing.
- For detail study of above traversal methods, consider a following
binary tree.

B D

E E G
C

2. Preorder Traversing :-
- This traversing method works on follows, I. Process the Root
node R.
II. Traverse the left sub tree of R in preorder.
III. Traverse the right sub tree of R in P preorder.
- Also this traversing method is called node-left-right (N-L-R)
traversal.
- The preorder traversal of given tree T shown in above fig. is:
A B C E D E F G.
3. Inorder Traversal :-
- This traversing method works as follows, I. Traverse the left sub
tree of R in inorder.
II. Process the root R.
III. Traverse the right sub tree of R in inorder.

By: Chimle M. D. 8 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm
-

- Also this traversing method is called left-node-right (L-N-R)

traversal.
- The inorder traversal of given tree T shown in above figure is,
C B E A E F D G.
3. Post-order Traversal :-
- This traversing method works as follows,
I. Traverse the left sub tree of R in post order.
II. Travers the right sub tree of R in post order.
III. Process the root node R.
- Also this traversing method is also called left-right-node (L-RN)
traversal.
- The post order traversal of given tree T shown in above figure is:
C E B F E G D A.

▪ Header Nodes : Threads.

❖ Header Nodes :
- Suppose a binary tree T is maintained in memory by means of
linked representation.
- Sometimes header node, is added to the beginning of T.
- When this extra node is used the tree pointer variable, which we
will call HEAD (instead of ROOT), will point to the header node
and the left pointer of the header node will point to the ROOT[T].
- Following figure shows a symatic picture of binary tree that uses
a linked representation with a header node.

By: Chimle M. D. 9 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

HEAD

Header Node

B C

D E G H

F J K

- Suppose, a binary tree T is empty. Then, T will still contain a

header node, but the left pointer of the header node will contain
the null value. Thus, the condition is,
LEFT [HEAD] = NULL. It will indicate an empty tree.
- In above representation of binary tree T is used to a header node
as a sentinel. That is, if a node has an empty sub tree, then the
pointer field for the sub tree will contain the address of the
header node instead of the null value.
- Accordingly, no pointer will even contain an invalid address and
the condition,

By: Chimle M. D. 10 / 13
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

LEFT [HEAD] = HEAD. It will indicate an empty sub tree.

❖ Threads ; Inorder Threadings :

- Consider a linked representation of binary tree T and has
pointer fields LEFT and RIGHT will contain NULL elements.
- This space may be more efficiently used by replacing the null
entries by some other type of information.
- Specially, we will replace certain new entries by special pointers
which point nodes higher in the tree.
- These special pointers are called threads and binary threes with
such pointers are called “threaded trees.”
- The threads n the threaded tree must be distinguished in same
way from ordinary pointers.
- The threads in a diagram of a threaded tree are usually indicated
by dotted lines.
- In computer memory an extra one bit TAG field may be used to
distinguish threads from ordinary pointers or alternatively
threads may be denoted by negative integers when ordinary
pointers are denoted by positive integers.
- There are many ways to thread a binary tree T, but each
threading will corresponding to a particular traversal of T.
- Also, one may choose a one way threading or two way threading
as shown in following diagram.

By: Chimle M. D. 11 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

B C

E G H
D

F K
J

Fin. [a] One–Way

Threading Fin. [b] Two–Way
Inorder Threading

- Accordingly, in the one-way threading of T, a thread will appear

in the RIGHT field of one node and will point to the next node in
the inorder traversal T.
- And in the two-way threading of T, a thread will also appear in
the LEFT field of a node and will point to the preceding node in
the inorder traversal of T.
- The LEFT pointer of the first node and the RIGHT pointer of the
last node will contain the NULL values.

By: Chimle M. D. 12 / 13
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

- When T does not have header node.

❖ General Tree :-
- A general tree is defined to be non empty finite set T of elements
called nodes, such that:
1. T contains a distinguished elements R, called the ROOT of
T.
2. The remaining elements T from an ordered collection of 0
[zero] or more disjoints tree T1, T2, ….., Tm.
- The trees T1, T2, ….., Tm are called sub trees of the root R and the
roots of T1, T2, ….., Tm are called successors of R.
- Terminology from family relationships, graph theory and
horticulture is used for general trees in the same way as for
binary tree.
- In particular if is node with successors S1, S2, ….., Sm then N is
called parent and S1, S2, ….., Sm. are called children’s of N. And
relationship between S1 and S2 are called sibling of each other.
- Ex.: Following figure shows general tree T with 13 nodes, A B C
D E F G H J K L M N.

By: Chimle M. D. 13 / 14
Class: BCASY(Sem IV) COCSIT, Latur Sub: Data Structure and algorithm

D
B

E F
K
G J
H
M N

- In above general tree T has: A is root of T and A has 3 children;

the first child B, second C and third child D observe that,
1. The node C has 3 children.
2. Each of the nodes B and K has only two children.
3. Each of the nodes D and H has only one child.
4. The nodes E, F, G, J, M, N have no children. Therefore, these
are called ‘Terminal Nodes.’

By: Chimle M. D. 14 / 13