DATA STRUCTURES

AND ALGORITHMS

MRS. BHAWANA ATUL AHIRE

ASSISTANT PROFESSOR
MVP SAMAJ’S KBTCOE, NASHIK
DEFINITION
 Data structure is representation of the logical relationship
existing between individual elements of data.
 In other words, a data structure is a way of organizing all

data items that considers not only the elements stored but
also their relationship to each other.
INTRODUCTION
 Data structure affects the design of both structural &
functional aspects of a program.
Program=algorithm + Data Structure
 You know that a algorithm is a step by step procedure to solve

a particular function.
INTRODUCTION
 That means, algorithm is a set of instruction written to carry
out certain tasks & the data structure is the way of
organizing the data with their logical relationship retained.
 To develop a program of an algorithm, we should select an

appropriate data structure for that algorithm.

 Therefore algorithm and its associated data structures from a

program.
CLASSIFICATION OF DATA
STRUCTURE
 Data structure are normally divided into two broad
categories:
Primitive
Data Structure
Non-Primitive Data Structure
 CLASSIFICATION OF DATA
STRUCTURE

Data structure

Primitive DS Non-Primitive DS

Integer Float Character Pointer

 CLASSIFICATION OF DATA
STRUCTURE

Non-Primitive DS

Linear List Non-Linear List

Array Queue Graph Trees

Link List Stack

PRIMITIVE DATA
STRUCTURE
 There are basic structures and directly operated upon by
the machine instructions.
 In general, there are different representation on different
computers.
 Integer, Floating-point number, Character constants,
string constants, pointers etc, fall in this category.
NON-PRIMITIVE DATA
STRUCTURE
 There are more sophisticated data structures.
 These are derived from the primitive data structures.

 The non-primitive data structures emphasize on

structuring of a group of homogeneous (same type) or

heterogeneous (different type) data items.
NON-PRIMITIVE DATA
STRUCTURE
 Lists, Stack, Queue, Tree, Graph are example of non-
primitive data structures.
 The design of an efficient data structure must take

operations to be performed on the data structure.

NON-PRIMITIVE DATA
STRUCTURE

 The most commonly used operation on data structure are

broadly categorized into following types:
 Create
 Selection
 Updating
 Searching
 Sorting
 Merging
 Destroy or Delete
DIFFERENT BETWEEN THEM
 A primitive data structure is generally a basic structure
that is usually built into the language, such as an integer,
a float.
 A non-primitive data structure is built out of primitive

data structures linked together in meaningful ways, such

as a or a linked-list, binary search tree, AVL Tree, graph
etc.
DESCRIPTION OF VARIOUS
DATA STRUCTURES : ARRAYS
 An array is defined as a set of finite number of
homogeneous elements or same data items.
 It means an array can contain one type of data only,

either all integer, all float-point number or all character.

ARRAYS

 Simply, declaration of array is as follows:

int arr[10]
 Where int specifies the data type or type of elements arrays
stores.
 “arr” is the name of array & the number specified inside the

square brackets is the number of elements an array can store,

this is also called sized or length of array.
ARRAYS
 Following are some of the concepts to be remembered
about arrays:
The individual element of an array can
be accessed by specifying name of the
array, following by index or subscript
inside square brackets.
The first element of the array has index
zero[0]. It means the first element and
last element will be specified as:arr[0]
& arr[9]
Respectively.
ARRAYS

The elements of array will always be

stored in the consecutive (continues)
memory location.
The number of elements that can be stored
in an array, that is the size of array or its
length is given by the following equation:
(Upperbound-lowerbound)+1
ARRAYS
For the above array it would be
(9-0)+1=10,where 0 is the lower bound
of array and 9 is the upper bound of
array.
Array can always be read or written
through loop. If we read a one-
dimensional array it require one loop for
reading and other for writing the array.
ARRAYS
For example: Reading an array
For(i=0;i<=9;i++)
scanf(“%d”,&arr[i]);
For example: Writing an array

For(i=0;i<=9;i++)
printf(“%d”,arr[i]);
ARRAYS
If we are reading or writing two-
dimensional array it would require two
loops. And similarly the array of a N
dimension would required N loops.
Some common operation performed on
array are:
Creation of an array
Traversing an array
ARRAYS
Insertionof new element
Deletion of required element
Modification of an element
Merging of arrays
LISTS
 A lists (Linear linked list) can be defined as a collection of
variable number of data items.
 Lists are the most commonly used non-primitive data
structures.
 An element of list must contain at least two fields, one for
storing data or information and other for storing address of
next element.
 As you know for storing address we have a special data
structure of list the address must be pointer type.
LISTS
 Technically each such element is referred to as a node,
therefore a list can be defined as a collection of nodes as
show bellow:

[Linear Liked List]

Head

AAA BBB CCC

Information field Pointer field

LISTS
 Types of linked lists:
 Single linked list
 Doubly linked list
 Single circular linked list
 Doubly circular linked list
STACK
 A stack is also an ordered collection of elements like
arrays, but it has a special feature that deletion and
insertion of elements can be done only from one end
called the top of the stack (TOP)
 Due to this property it is also called as last in first out

type of data structure (LIFO).

STACK

 It could be through of just like a stack of plates placed on table in

a party, a guest always takes off a fresh plate from the top and the
new plates are placed on to the stack at the top.
 It is a non-primitive data structure.

 When an element is inserted into a stack or removed from the

stack, its base remains fixed where the top of stack changes.
STACK
 Insertion of element into stack is called PUSH and
deletion of element from stack is called POP.
 The bellow show figure how the operations take place on

a stack:

PUSH POP

[STACK]
STACK
 The stack can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic
implementation)
QUEUE

 Queue are first in first out type of data structure (i.e. FIFO)
 In a queue new elements are added to the queue from one

end called REAR end and the element are always removed
from other end called the FRONT end.
 The people standing in a railway reservation row are an

example of queue.
QUEUE
 Each new person comes and stands at the end of the row
and person getting their reservation confirmed get out of
the row from the front end.
 The bellow show figure how the operations take place on

a stack:

10 20 30 40 50

front rear
QUEUE
 The queue can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic
implementation)
TREES
 A tree can be defined as finite set of data items (nodes).
 Tree is non-linear type of data structure in which data

items are arranged or stored in a sorted sequence.

 Tree represent the hierarchical relationship between

various elements.
TREES
 In trees:
 There is a special data item at the top of hierarchy called the
Root of the tree.
 The remaining data items are partitioned into number of
mutually exclusive subset, each of which is itself, a tree
which is called the sub tree.
 The tree always grows in length towards bottom in data
structures, unlike natural trees which grows upwards.
TREES
 The tree structure organizes the data into branches,
which related the information.

A root

B C

D E F G
GRAPH
 Graph is a mathematical non-linear data structure
capable of representing many kind of physical structures.
 It has found application in Geography, Chemistry and

Engineering sciences.
 Definition: A graph G(V,E) is a set of vertices V and a

set of edges E.
GRAPH
 An edge connects a pair of vertices and many have
weight such as length, cost and another measuring
instrument for according the graph.
 Vertices on the graph are shown as point or circles and

edges are drawn as arcs or line segment.

GRAPH
 Example of graph:

6
v2 v5
v1 v3
10

v1 8 11
15
9 v2
v3 v4 v4

[a] Directed & [b] Undirected

Weighted Graph Graph
GRAPH
 Types of Graphs:
Directedgraph
Undirected graph
Simple graph
Weighted graph
Connected graph
Non-connected graph
STATIC DATA STRUCTURE

In Static data structure the size of the structure is fixed. The

content of the data structure can be modified but without
changing the memory space allocated to it.
DYNAMIC DATA STRUCTURE

In Dynamic data structure the size of the structure is not fixed

and can be modified during the operations performed on it.
Dynamic data structures are designed to facilitate change of
data structures in the run time.
DIFFERENCE
Dynamic Data
Aspect Static Data Structure
Structure

Memory is allocated at Memory is allocated at

Memory allocation
compile-time run-time

Size is fixed and cannot Size can be modified

Size
be modified during runtime

Memory utilization is
Memory utilization may
Memory utilization efficient as memory can
be inefficient
be reused

Access time may be

Access time is faster as it
Access slower due to indexing
is fixed
and pointer usage

Arrays, Stacks, Queues, Lists, Trees (with variable

Examples
Trees (with fixed size) size), Hash tables
PERSISTENT VS. EPHEMERAL
 An ephemeral data structure is one for which
only one version is available at a time: after
an update operation, the structure as it
existed before the update is lost.
 A persistent structure is one where multiple
versions are simultaneously accessible: after
an update, both old and new versions can be
used.
EXAMPLES
 Linked List Concatenation :
ABSTRACT DATA TYPES
 Abstract Data type (ADT) is a type (or class)
for objects whose behavior is defined by a
set of values and a set of operations. The
process of providing only the essentials and
hiding the details is known as abstraction.
 ALGORITHM
An algorithm is a finite set of steps required to solve a problem.
An algorithm must have following properties:
1. Input:
An algorithm must have zero or more quantities as input whcih
are externally supplied.
2. Output:
An algorithm must produce one or more output after processing
set of statements.
3. Definiteness:
Each instruction must be clear and ditinct.
4. Finiteness:
The algorithm must terminate after a finite number of steps.
5. Effectiveness:
Each operations must be definite also it should be feasible
EXAMPLE OF AN ALGORITHM
1. Start
2. Accept size for an array : (Read size)
3. Accept array elements values from user i.e. Array elements.
4. Accept element to be searched from user i.e. Read Value
5. Set i=0,flag=0
6. Compare A[i] with value
If(A[i] is a value)
Set flag=1 go to step 8
Else
Move to next data element
i= i+1;
7. If (i<=n) go to step 6
8. If(flag=1) then
Print found and Return i as position
Else
Print not found
9. Stop.
ALGORITHM DESIGN APPROCHES

Top-Down Approach:

Bottom-Up Approach:
TOP-DOWN APPROACH:

A top-down approach starts with identifying
major components of system or program
decomposing them into their lower level
components & iterating until desired level of
module complexity is achieved .

In this we start with topmost module &
incrementally add modules that is calls.

It takes the form of step wise procedure.

In this solution is divided into sub task and each
sub task further divided into smallest subtask.

The sub task are then combined into single
solution.
BOTTOM-UP APPROACH:


It is inverse of top down method.

A bottom-up approach starts with designing
most basic or primitive component & proceeds
to higher level components.

Starting from very bottom , operations that
provide layer of abstraction are implemented.

The programmer may write code to perform
basic operations then combined those to make a
modules ,whcih are finally combined to form
overall system structure.
TIME COMPLEXITY


Time complexity of program / algorithm is the
amount of computer time that it needs to run
to completion.

While calculating time complexity, we
develop frequency count for all key
statements which are important.

Consider three algorithms given below:-

Algorithm A:- a=a+1

Algorithm B:- for x=1 to n step

a=a+1

Loop

Algorithm C:- for x=1 to n step 1

for y=1 to n step 2

a=a+1

loop

Frequency count for algorithm A is 1 as a=a+1
statement will execute only once.

Frequency count for algorithm B is n as a=a+1
is a key statement executes “n‟ times as
loop runs
“n‟ times.

Frequency count for algorithm C is n2 as
a=a+1 is a key statement executes n2
times as the inner
loop runs n times, each time the outer loop
runs and the outer loop also runs for n times.
SPACE COMPLEXITY

Space complexity of a program / algorithm is the amount of
memory that it needs to run to completion.

The space needed by the program is the sum of the following
components.

Fixed space requirements:-

Fixed space is not dependent on the characteristics of the
input and outputs.

Fixed space consists of space for simple variable, fixed
size variables, etc.

Variable space requirements:-

Variable space includes space needed by variables
whose size depends upon the particular problem being
solved, referenced variables and the stack space
required for recursion on particular instance of variables.

e.g. Additional space required where function uses
recursion.
ALGORITHM ANALYSIS:


There are different ways of solving problem &
there are different algorithms which can be
designed to solve a problem.

There is difference between problem &
algorithm.

A problem has single problem statement that
describes it in general terms.

However there are different ways to solve a
problem & some solutions may be more
efficient than others.

There are different types of time complexities
which can be analyzed for an algorithm:
 Best Case Time Complexity:
 Worst Case Time Complexity:
 Average Case Time Complexity:
BEST CASE TIME COMPLEXITY:


It is measure of minimum time that
algorithm will require for input of size “n‟.

Running time of many algorithms varies not
only for inputs of different sizes but also input
of same size.

For example in running time of some sorting
algorithms, sorting will depend on ordering of
input data. Therefore if input data of “n‟ items
is presented in sorted order, operations
performed by algorithm will take least time.
WORST CASE TIME COMPLEXITY:


It is measure of maximum time that
algorithm will require for input of size “n‟.

Therefore if various algorithms for sorting are
taken into account & say “n‟ input data items
are supplied in reverse order for any sorting
algorithm, then algorithm will require n2
operations to perform sort which will
correspond to worst case time complexity of
algorithm.
AVERAGE CASE TIME
COMPLEXITY:


The time that an algorithm will require to
execute typical input data of size “n‟ is
known as average case time complexity.

We can say that value that is obtained by
averaging running time of an algorithm for all
possible inputs of size “n‟ can determine
average case time complexity.
 Big O notation

• Big O notation is used in Computer Science to

describe the performance or complexity of an
algorithm.
• Big O specifically describes the worst-case
scenario, and can be used to describe the execution
time required or the space used (e.g. in memory or
on disk) by an algorithm.
• O(1)
– O(1) describes an algorithm that will always execute in the same time (or
space) regardless of the size of the input data set.
•E.g Push and POP operation for a stack
• O(N)
– O(N) describes an algorithm whose performance will grow linearly and in
direct proportion to the size of the input data set.
– Big O notation will always assume the upper limit.
•E.g. Linear search with unsorted data.
• O(N2)
– O(N2) represents an algorithm whose performance is directly proportional to
the square of the size of the input data set.
– This is common with algorithms that involve nested iterations over the data set.
•E.g. Comparing two dimensional arrays of size n.
O(log N). Logarithmic Time
The iterative halving of data sets described in the binary search
example produces a growth curve that peaks at the beginning and
slowly flattens out as the size of the data sets increase
E.g. Binary search:
an input data set containing 10 items takes one second to
complete, a data set containing 100 items takes two seconds,
and a data set containing 1000 items will take three seconds.

O(N log N). Logarithmic Time

– E.G. More advanced sorting algorithms: quick sort,merge sort.
BIG OH NOTATION (O)
 It is define as upper bound and upper bound
on an algorithm is the most amount of time
required ( the worst case performance).
Big oh notation is used to
describe asymptotic upper bound.
 Mathematically, if f(n) describes the running

time of an algorithm; f(n) is O(g(n)) if there

exist positive constant C and n0 such that,
 0 <= f(n) <= Cg(n) for all n >= n0
BIG OMEGA NOTATION (Ω)
 It is define as lower bound and lower bound on
an algorithm is the least amount of time
required ( the most efficient way possible, in
other words best case).
 Just like O notation provide an asymptotic

upper
bound, Ω notation provides asymptotic
lower bound.

 Let f(n) define running time of an algorithm;

f(n) is said to be Ω(g (n)) if there exists
positive constant C and (n0) such that
 0 <= Cg(n) <= f(n) for all n >= n0
BIG THETA NOTATION (Θ)
 It is define as tightest bound and tightest
bound is the best of all the worst case times
that the algorithm can take.
 Let f(n) define running time of an algorithm.

f(n) is said to
be Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g
(n)).
 Mathematically,

 0 <= f(n) <= C1g(n) for n >= n0

0 <= C2g(n) <= f(n) for n >= n0

 Merging both the equation, we get :

 0 <= C2g(n) <= f(n) <= C1g(n) for n >= n0

S.N
o.
Big Oh (O) Big Omega (Ω) Big Theta (Θ)

It is like (<=) It is like (>=) It is like (==)

rate of growth of an rate of growth is greater meaning the rate of
1.
algorithm is less than or than or equal to a growth is equal to a
equal to a specific value. specified value. specified value.

The upper bound of The bounding of

The algorithm’s lower
algorithm is represented by function from above and
bound is represented by
Big O notation. Only the below is represented by
Omega notation. The
2. above function is bounded theta notation. The
asymptotic lower bound
by Big O. Asymptotic upper exact asymptotic
is given by Omega
bound is given by Big O behavior is done by this
notation.
notation. theta notation.

Big Omega (Ω) – Lower Big Theta (Θ) – Tight

3. Big oh (O) – Upper Bound
Bound Bound

It is define as lower
It is define as upper bound It is define as tightest
bound and lower bound
and upper bound on an bound and tightest
on an algorithm is the
algorithm is the most bound is the best of all
4. least amount of time
amount of time required the worst case times
required ( the most
( the worst case that the algorithm can
efficient way possible, in
performance). take.
other words best case).

Mathematically – Big
Mathematically: Big Oh is 0 Mathematically: Big
Theta is 0 <= C2g(n) <=
5. <= f(n) <= Cg(n) for all n Omega is 0 <= Cg(n) <=
f(n) <= C1g(n) for n >=
>= n0 f(n) for all n >= n0
n0
1-D ARRAY ADDRESS CALCULATION
 Address of A[I] = B + W * (I – LB)
 I = Subset of element whose address to be

found,
B = Base address,
W = Storage size of one element store in any
array(in byte),
LB = Lower Limit/Lower Bound of subscript(If
not specified assume zero).
 Given the base address of an array A[1300 …………
1900] as 1020 and the size of each element is 2 bytes in
the memory, find the address of A[1700].
 Given:

Base address B = 1020

Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Byte
Subset of element whose address to be found I = 1700
 Formula used:

Address of A[I] = B + W * (I – LB)

 Solution:

Address of A[1700] = 1020 + 2 * (1700 – 1300)

= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820
Address of an element of any array say “A[ I ][ J ]” is calculated in two forms as given:
(1) Row Major System (2) Column Major System
Row Major System:
The address of a location in Row Major System is calculated using the following formula:

Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]

Column Major System:

The address of a location in Column Major System is calculated using the following formula:

Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]

Where,
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
M = Number of row of the given matrix
N = Number of column of the given matrix

Number of rows (M) will be calculated as = (Ur – Lr) + 1

Number of columns (N) will be calculated as = (Uc – Lc) + 1
And rest of the process will remain same as per requirement (Row Major Wise or Column Major Wise).
Q 1. An array X [-15……….10, 15……………40] requires one byte of storage. If beginning
location is 1500 determine the location of X [15][20].

Solution:
As you see here the number of rows and columns are not given in the question. So they are
calculated as:

Number or rows say M = (Ur – Lr) + 1 = [10 – (- 15)] +1 = 26 Number or columns say N = (Uc –
Lc) + 1 = [40 – 15)] +1 = 26
(i)Column Major Wise Calculation of above equation
The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, M
= 26 Address of A [ I ][ J ] = B + W * [ ( I – Lr ) + M * ( J – Lc ) ]

= 1500 + 1 * [(15 – (-15)) + 26 * (20 – 15)] = 1500 + 1 * [30 + 26 * 5] = 1500

+ 1 * [160] = 1660 [Ans]

(ii)Row Major Wise Calculation of above equation

The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, N
= 26 Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
= 1500 + 1* [26 * (15 – (-15))) + (20 – 15)] = 1500 + 1 * [26 * 30 + 5] = 1500
+ 1 * [780 + 5] = 1500 +
785
= 2285 [Ans]
TYPES OF LINKED LIST
 Singly Linked List − The nodes only point
to the address of the next node in the list.
 Doubly Linked List − The nodes point to

the addresses of both previous and next

nodes.
 Circular Linked List − The last node in the

list will point to the first node in the list. It

can either be singly linked or doubly linked.
LINKED LIST
 Singly linked List :

 Doubly linked List :

 Circular linked List :

BASIC OPERATIONS IN THE LINKED
LISTS
 Insertion − Adds an element at the
beginning of the list.
 Deletion − Deletes an element at the

beginning of the list.

 Display − Displays the complete list.

 Search − Searches an element using the

given key.
 Delete − Deletes an element using the

given key.