Data Structure

Basic Concepts

1
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.

◼ 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.
Introduction
◼ 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

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.
Classification of Data Structure

Non-Primitive DS

Linear List Non-Linear List

Array Queue Graph Trees

Link List Stack

Non-Primitive Data Structure
◼ 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.
◼ 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.
What is Program

◼ A Set of Instructions
◼ Data Structures + Algorithms
◼ Data Structure = A Container stores Data
◼ Algoirthm = Logic + Control

12
Efficiency
◼ Computer Scientists don’t just write programs.
◼ They also analyze them.
◼ How efficient is a program?
◼ How much time does it take program to complete?
◼ How much memory does a program use?
◼ How do these change as the amount
of data changes?
◼ What is the difference between the average case
and worst-case efficiency if any?

13
Technique
◼ How many computations will this program
(function, algorithm) perform to get the
answer?
◼ Many simplifications
◼ view algorithms as C programs
◼ determine by analysis the total number
executable statements (computations) in
program or as a function of the amount of
data
Counting Statements
int x; // one statement
x = 12; // one statement
int y = z * x + 3 % 5 * x / i; // 1
x++; // one statement
int p = x < y && y % 2 == 0 ||
z >= y * x; // 1
Int data[100]; // 100
data[50] = x * x + y * y; // 1

15
Example
int total(int values[],int n) {
int result = 0,i;
for (i= 0; i < n; i++)
result += values[i];
return result;
}

 How many statements are executed by

function total as a function

16
Big O notation – Calculating Algorithm Efficiency

• Big O notation is the language we use for talking about

how long an algorithm takes to run.
• It's how we compare the efficiency of different approaches
to a problem.
• Imagine you have a list of 10 objects, and you want to sort
them in order.
• There’s a whole bunch of algorithms you can use to make
that happen, but not all algorithms are built equal.
• It is simply a way of comparing algorithms and how long
they will take to run.

17
Big O notation
A simplified analysis of algorithm efficiency.

It considers:
• Complexity in terms of input size, N
• Machine independence (Doesn’t consider the machines
hardware)
• Basic computer steps
• Time & space(working storage)
• Originally used by German theorist Paul Bachman
• O means order of (German: "Ordnung von").
• n is the input size in units of bits needed to represent
the input

18
Big O
◼ The most common method and notation for
discussing the execution time of algorithms is Big
O, also spoken Order
◼ Big O is the asymptotic execution time
of the algorithm
◼ In other words, how does the running time of

the algorithm grow as a function of the amount

of input data?
◼ Big O is an upper bounds
◼ It is a mathematical tool
◼ Hide a lot of unimportant details by assigning a
simple grade (function) to algorithms
19
Formal Definition of Big O
◼ T(N) is O( F(N) ) if there are positive
constants c and N0 such that T(N) < cF(N)
when N > N0
◼ N is the size of the data set the algorithm works
on
◼ T(N) is a function that characterizes the actual
running time of the algorithm
◼ F(N) is a function that characterizes an upper
bounds on T(N). It is a limit on the running time
of the algorithm. (The typical Big functions table)
◼ c and N0 are constants
20
What it Means
◼ T(N) is the actual growth rate of the
algorithm
◼ can be equated to the number of executable
statements in a program or chunk of code
◼ F(N) is the function that bounds the growth
rate
◼ may be upper or lower bound
◼ T(N) may not necessarily equal F(N)
◼ constants and lesser terms ignored because it is
a bounding function
21
Typical Big O Functions – "Grades"
Function Common Name
N! factorial Running
time grows
2N Exponential 'quickly' with
N d, d > 3 Polynomial more input.
N3 Cubic
N2 Quadratic
N N N Square root N
N log N N log N
N Linear
Running
N Root - n time grows
log N Logarithmic 'slowly' with
more input.
1 Constant
22
the time required by an algorithm falls under three
types −
Best Case − Minimum time required for program
execution.
Average Case − Average time required for
program execution.
Worst Case − Maximum time required for
program execution.

23
Asymptotic Notations
Following are the commonly used asymptotic
notations to calculate the running time
complexity of an algorithm.

•Ο Notation

•Ω Notation

•θ Notation

24
Big Oh Notation, Ο
• The notation Ο(n) is the formal way to express the upper
bound of an algorithm's running time.
• It measures the worst-case time complexity or the
longest amount of time an algorithm can possibly take to
complete.
Omega Notation, Ω
• The notation Ω(n) is the formal way to express the lower
bound of an algorithm's running time.
• It measures the best-case time complexity or the best
amount of time an algorithm can possibly take to
complete.
Theta Notation, θ
• The notation θ(n) is the formal way to express both the
lower bound and the upper bound of an algorithm's
running time. 25
Data Structure
Aggregation of atomic and composite data into a set with defined
relationships. Structure refers to a set of rules that hold the data
together.
• A combination of elements in which each is either a data type or
another data structure.
• A set of associations of relationship involving combined elements.

26
• Atomic and Composite Data
• Data Type
• Data Structure
• Abstract Data Type

27
28
The Abstract Data Type
The abstract datatype is special kind of datatype, whose
behavior is defined by a set of values and set of operations.

The keyword “Abstract” is used as we can use these

datatypes, we can perform different operations.
But how those operations are working that is totally hidden
from the user.
The ADT is made of with primitive datatypes, but operation
logics are hidden.

Some examples of ADT are Stack, Queue, List etc.

29
Stack −
• isFull(), This is used to check whether stack is full
or not
• isEmpty(), This is used to check whether stack is
empty or not
• push(x), This is used to push x into the stack
• pop(), This is used to delete one element from top
of the stack
• peek(), This is used to get the topmost element of
the stack
• size(), this function is used to get number of
elements present into the stack

30
Queue −
• isFull(), This is used to check whether queue is
full or not
• isEmpry(), This is used to check whether queue is
empty or not
• insert(x), This is used to add x into the queue at
the rear end
• delete(), This is used to delete one element from
the front end of the queue
• size(), this function is used to get number of
elements present into the queue

31
List −
• size(), this function is used to get number of
elements present into the list
• insert(x), this function is used to insert one element
into the list
• remove(x), this function is used to remove given
element from the list
• get(i), this function is used to get element at
position i
• replace(x, y), this function is used to replace x with
y value

32
ADT Implementations

There are two basic structures we can use to

implement an ADT list: arrays and linked lists.
In this section we discuss the basic
linked-list implementation.
• Array Implementation
• Linked List Implemenation

33
Lists
A list is an ordered set of data. It is often used to store
objects that are to be processed sequentially.

A list can be used to create a queue.

34
Arrays
An array is an indexed set of variables, such as
dancer[1], dancer[2], dancer[3],… It is like a set of
boxes that hold things.

A list is a set of items.

An array is a set of
variables that each
store an item.

35
Arrays and Lists
In a list, the missing spot is filled in when
something is deleted.

36
Arrays and Lists
In an array, an empty variable is left behind
when something is deleted.

37
38
39
40
41