Lecture # 1-2

Dr. M. Nadeem
Books
C++ Plus Data Structure by Nell Dale, 3rd Edition

Data Structures & Algorithms in Java by M. T.

Goodrich 6th Edition

A Practical Introduction to Data Structures and

Algorithm Analysis C. A. Shaffer 3rd Edition

Data Structures with C, Schaum’s Series

Data Structures by DS Malik
Introduction
Data
Set of values, Raw facts
Information
Processed data, meaningful data
Group Item
Data that can be divided into sub items
Entity
Attributes
Introduction
Record
Collection of attributes
Field
Single attribute
File
Collection of records
Primary Key
Fixed Length Record
Variable Length Record
What is Data Structure?
Data Structure is a mathematical or logical way of
organizing data in memory.

Data Structure represent data in memory and also

represents the relationship among the data that is
stored in memory.
What is Data Structure?
Data Structure allows us to manipulate data by
specifying a set of values, set of operations that can
be performed on set of values and set of rules that
needs to be followed while performing
operations.
Characteristics of data Structure
Rich Structure
Ability to model real world

Simple
Easier Processing
Operations on Data Structure
There are various operations that can be performed on
Data Structure:
√ Traversal
√ Insertion
√ Deletion
√ Searching
√ Sorting
√ Merging
Types of Data Structure
Basically Data Structure can be classified into two
categories:

(1) Primitive Data Structure

(2) Non Primitive Data Structure

Primitive Data Structure
"The Data Structure which is directly operated by
machine level instruction is known as Primitive
Data Structure.”
All primary (built in) data types are known as
Primitive data Structure.
Following are Primitive Data Structure:
√ Integer
√ Floating Point
√ Character
Non Primitive Data Structure
"The Data Structure which is not directly operated
by machine level instruction is known as Non
Primitive Data Structure."

Non Primitive Data Structure is derived from

Primitive Data Structure.

Non Primitive Data Structure are classified into two

categories:
(1) Linear Data Structure
(2) Non Linear Data Structure
Linear Data Structure
"The Data Structure in which elements are
arranged such that we can process them in linear
fashion (sequentially) is called linear data
structure.“

Following are Examples of Linear Data Structure:

√ Array
√ Stack
√ Queue
√ Linked List
Linear Data Structure
Array
√ An ordered set (sequence) with a fixed number of
elements, all of the same type
√ Array is a collection of variables of same data type that
share common name.
√ Array is an ordered set which consist of fixed number of
elements.
√ In array memory is allocated sequentially to each
element. It is also known as sequential list.
Linear Data Structure
Array properties:
Ordered so there is a first element, a second one, etc.
Fixed number of elements — fixed capacity
Elements must be the same type (and size);
Direct access: Access an element by giving its location
The time to access each element is the same for all
elements, regardless of position.
One Dimensional Array
Two Dimensional Array

array
Linear Data Structure
 Stack
√ Stack is a linear Data Structure in which insertion and
deletion operation are performed at same end.

√ “A Stack is a special kind of list in which all

insertions and deletions take place at one end,
called the Top”
Linear Data Structure
 Stack
√ Pushdown List
√ Last In First Out (LIFO)

√ Examples:
√ Books on a floor
√ Dishes on a shelf

√ Operations
√ Push
√ Pop stack
Linear Data Structure
Queue
√ Queue is a linear Data Structure in which insertion
operation is performed at one end called Rear end and
deletion operation is performed at another end called
front end
Linear Data Structure
Queue
√ Insertion at the rear end
√ Deleted at the front

√ First In First Out (FIFO)

√ Difference from Stack
• Insertion go at the end of the list, rather than the beginning of
the list.
√ Examples
 Railway Tunnel

queue
Linear Data Structure
Link List
√ Linked list is an ordered set which consist of
variable number of elements.
√ In Linked list elements are logically adjacent
to each other but they are physically not
adjacent.
√ It means elements of linked list are not
sequentially stored in memory.
Linear Data Structure
Link List
√ Link list is a record which are linked together
√A Flexible structure, because can
grow and shrink on demand.
√ Elements can be:
 Inserted
 Accessed
 Deleted
At any position

Linked list
Non-Linear Data Structure
"The Data Structure in which elements are
arranged such that we can not process them in
linear fashion (sequentially) is called Non-Linear
data structure.“
Non Linear Data Structures are useful to represent
more complex relationships as compared to Linear
Data Structures.

Following are Examples of Non-Linear Data Structure:

√ Tree
√ Graph
Non-Linear Data Structure
Tree
A tree is a collection of one or more nodes such that:
√ There is a special node called root node.

√ All the nodes in a tree except root node having only one
Predecessor.
√ Each node in a tree having 0 or more Successor.

√ A tree is used to represent hierarchical information.

Non-Linear Data Structure
Tree
√ Non-linear data structure
√ Each position in the tree is called a node
√ The “top” of the tree is called the root
√ The nodes immediately below a node are called
its children

tree
Non-Linear Data Structure
Graph

√ Non-Linear data structure

√ A Graph is a collection of nodes and edges which is

used to represent relationship between pair of nodes.
√ A graph G consists of set of nodes and set of edges and a
mapping from the set of edges to a set of pairs of nodes
Non-Linear Data Structure
Graph
√ Pair of elements connected with each other

1 3

6 4

5
Complexity of Algorithm
Time Complexity
√ The amount of time needed by a program to complete
its execution is known as Time complexity
√ The measurement of time is done in terms of number of
instructions executed by the program during its
execution
√ Thus Time Complexity depends on the Size of the
program and type of the algorithm being used
Complexity of Algorithm
Space Complexity
The amount of memory needed by a program during its
execution is known as Space complexity.
Total memory space need by the program is the sum of
following two memory:
Fixed size Memory:
√ It contains the space required for simple variables, constants,
instructions and fixed size structured variable such as array.
Variable size Memory:
√ It contains the space required for structured variable to which
memory is allocated run time. It also contains space required
while function is calling itself.
Complexity of Algorithm
Best case Time Complexity
 The measurement of minimum time that is required by an
algorithm to complete its execution is known as Best Case
Time Complexity.
 Time complexity of particular algorithm can be calculated
by providing different input values to the algorithm.
 Consider an example of sorting N elements. If we supply
input values that is already sorted, an algorithm required
less time to sort them.
 This is known as Best case time complexity. However best
case time complexity does not guarantee that the
algorithm will always execute within this time for different
input values.
Complexity of Algorithm
Average case Time Complexity
The measurement of average time that is required by an
algorithm to complete its execution is known as Average
Case Time Complexity.
Time complexity of particular algorithm can be
calculated by providing different input values to the
algorithm.
Consider an example of sorting N elements. Average
time complexity can be calculated by measuring the
time required to complete the execution of an algorithm
for different input values and then calculate the average
time required to sort N elements
Complexity of Algorithm
Worst case Time Complexity
 The measurement of maximum time that is required by
an algorithm to complete its execution is known as Worst
Case Time Complexity.
 Time complexity of particular algorithm can be calculated
by providing different input values to the algorithm.
Consider an example of sorting N elements. If we supply
input values that is in reverse order, an algorithm
required maximum time to sort them. This is known as
worst case time complexity.
 Thus, worst case time complexity always guarantees that
the algorithm will always execute within this time for
different input values.
Asymptotic Notations
Asymptotic Notations are used to describe the
complexity of an algorithm. Complexity of an
algorithm indicates how much time needed by an
algorithm to complete its execution for given set of
input data.

The same problem can be solved using different

algorithms. In order to select the best algorithm for a
problem, we need to determine how much time the
different algorithms will take to run and then select
the better algorithm.
Asymptotic Notations
There are various Asymptotic Notations are available
to describe complexity of an algorithm. Which are
1. Big-Oh Notation
2. Big-Omega Notation
3. Big-Theta Notation
4. Little-oh Notation
5. Little-omega Notation
Asymptotic Notations
Big-Oh Notation
√ Big - O Notation is used to describe the Time complexity
of an algorithm.
√ It means how much time is needed by an algorithm to
complete its execution for the input size of N.
√ For Example a sorting algorithm take longer time to sort
5000 elements than 50.
Asymptotic Notations
Following are commonly used Orders of an algorithm.
√ O(1): An algorithm that will always execute in the same
time regardless of the size of the input data is having
complexity of O(1).
√ O(n): An algorithm whose performance is directly
proportional to the size of the input data is having
complexity of O(n). It is also known as linear
complexity. If an algorithm uses looping structure over
the data then it is having linier complexity of O(n).
Linier Search is an example of O(n).
Asymptotic Notations
Following are commonly used Orders of an algorithm.
√ O(n^2): An algorithm whose performance is directly
proportional to the square of the size of the input data is
having complexity of O(n2). If an algorithms uses
nested looping structure over the data then it is having
quadratic complexity of O(n2). Bubble sort, Selection
Sort are the example of O(n2).
√ O(logn): An algorithm in which during each iteration
the input data set is partitioned into to sub parts is
having complexity of O(logn). Quick Sort, Binary Search
are the example of O(logn) complexity.