Data Structures
Chapter 1
INTRODUCTION TO DS & ALGORITHM
Data Structure – Algorithm – Dynamic Memory Management - Performance
Analysis: Space Complexity, Time Complexity, Asymptotic Notations ( Big O,
Omega, Theta)
DATA STRUCTURE
What is Data?
Dictionary definition:
The quantities, characters or symbols on which operations are performed by a
computer, which may be stored and transmitted in the form of electrical signals and
recorded on magnetic, optical or mechanical recording media.
C=a+b
In the above statement, an operation is performed on both quantities. These data are
operated, stored and transmitted there by conforms to the conditions of being called
Data.
Information
When Data becomes Information?
Data is a collection of characters such as latipac fo aidni
Information is : Capital of India.
When meaning is extracted from data, data becomes information.
In simple words, if data is in an order / in a systematic way.. it gets a structure.
Such processed data becomes information.
There by, to get information, data need to have a structure and for that one
need to know Data Structures.
,Data Structures
It is an organized or systematic way of arranging and storing data.
Systematic way of arranging data increases the efficiency of managing the
data.
Efficiency in terms of time and space.
Data structures provides means for managing large amounts of data.
It also enables searching, sorting, inserting and deleting data.
Data structures are categorized into two as
o Primitive Data Structures
o Non Primitive Data Structures
Primitive Data Structures
Primitive Data Structures are the most basic data structures available in all
programming languages such as int, float, character, Boolean, double, void etc
Non Primitive Data Structures
Non primitive data structures are complex data structures that are built using
primitive data structures such as arrays, linked lists, stacks, queues, trees, graphs
and hash tables.
Arrays: A collection of homogeneous elements stored in contiguous memory
locations.
Linked Lists: A collection of homogenous elements that are linked using pointers.
Stacks : A Collection of elements that follow First-in-First-Out (FIFO) mechanism.
Queues: A Collection of elements that follow Last-in-first-out (LIFO) mechanisms.
Trees: A hierarchical data structure consisting of nodes that are connected by edges.
Graphs: A non linear data structure consisting of nodes and edges.
Hashtable : A data structure that stores data in an associated manner using a hash
function.
Set: A collection of unique elements.
Maps: An abstract data type that contains key value pairs.
, Choice of Data Structure
Choice of data structure for a particular task depends on the type of data, amount of
data to be processed, operations to be performed on the data and the efficiency
requirements of the program.
♪ The idea of data structure is to reduce the space and time complexity of
tasks.
Why is Data Structures required?
Data Structures are required for the following reasons:
1. Data Search
Imagine, if there are 1 Million data (106) available and if an item needed to
searched, the entire (106) need to be searched. Every time a search occurs,
the whole bunch is searched, slowing down the search operation.
2. Processor Speed
Though the speed of the processor is high, if the data grows to 1 billion,
processor has its own speed limit. Therefore, the search operation is slow.
3. Too Many Parallel requests
When there are too many hits parallelly from the clients looking for data, the
operation is slow.
To resolve, the above constraints Data Structures are needed.
Data are organized in a structured way based on the type of data and operations to
be performed on the data.
ALGORITHM
Algorithm is a step by step procedure.
It provides set of instructions for a methodical implementation of ideas in a particular
order.
Algorithm is independent of any programming languages. It can be implemented in
any programming language.
Why an algorithm needs to be analyzed?
Chapter 1
INTRODUCTION TO DS & ALGORITHM
Data Structure – Algorithm – Dynamic Memory Management - Performance
Analysis: Space Complexity, Time Complexity, Asymptotic Notations ( Big O,
Omega, Theta)
DATA STRUCTURE
What is Data?
Dictionary definition:
The quantities, characters or symbols on which operations are performed by a
computer, which may be stored and transmitted in the form of electrical signals and
recorded on magnetic, optical or mechanical recording media.
C=a+b
In the above statement, an operation is performed on both quantities. These data are
operated, stored and transmitted there by conforms to the conditions of being called
Data.
Information
When Data becomes Information?
Data is a collection of characters such as latipac fo aidni
Information is : Capital of India.
When meaning is extracted from data, data becomes information.
In simple words, if data is in an order / in a systematic way.. it gets a structure.
Such processed data becomes information.
There by, to get information, data need to have a structure and for that one
need to know Data Structures.
,Data Structures
It is an organized or systematic way of arranging and storing data.
Systematic way of arranging data increases the efficiency of managing the
data.
Efficiency in terms of time and space.
Data structures provides means for managing large amounts of data.
It also enables searching, sorting, inserting and deleting data.
Data structures are categorized into two as
o Primitive Data Structures
o Non Primitive Data Structures
Primitive Data Structures
Primitive Data Structures are the most basic data structures available in all
programming languages such as int, float, character, Boolean, double, void etc
Non Primitive Data Structures
Non primitive data structures are complex data structures that are built using
primitive data structures such as arrays, linked lists, stacks, queues, trees, graphs
and hash tables.
Arrays: A collection of homogeneous elements stored in contiguous memory
locations.
Linked Lists: A collection of homogenous elements that are linked using pointers.
Stacks : A Collection of elements that follow First-in-First-Out (FIFO) mechanism.
Queues: A Collection of elements that follow Last-in-first-out (LIFO) mechanisms.
Trees: A hierarchical data structure consisting of nodes that are connected by edges.
Graphs: A non linear data structure consisting of nodes and edges.
Hashtable : A data structure that stores data in an associated manner using a hash
function.
Set: A collection of unique elements.
Maps: An abstract data type that contains key value pairs.
, Choice of Data Structure
Choice of data structure for a particular task depends on the type of data, amount of
data to be processed, operations to be performed on the data and the efficiency
requirements of the program.
♪ The idea of data structure is to reduce the space and time complexity of
tasks.
Why is Data Structures required?
Data Structures are required for the following reasons:
1. Data Search
Imagine, if there are 1 Million data (106) available and if an item needed to
searched, the entire (106) need to be searched. Every time a search occurs,
the whole bunch is searched, slowing down the search operation.
2. Processor Speed
Though the speed of the processor is high, if the data grows to 1 billion,
processor has its own speed limit. Therefore, the search operation is slow.
3. Too Many Parallel requests
When there are too many hits parallelly from the clients looking for data, the
operation is slow.
To resolve, the above constraints Data Structures are needed.
Data are organized in a structured way based on the type of data and operations to
be performed on the data.
ALGORITHM
Algorithm is a step by step procedure.
It provides set of instructions for a methodical implementation of ideas in a particular
order.
Algorithm is independent of any programming languages. It can be implemented in
any programming language.
Why an algorithm needs to be analyzed?
