Basic terminologies

Basic terminologies for

1. Data Structures
Basic Terminologies
1

2. Data Structures
“Clever” ways to organize information in order to enable
efficient computation
–What do we mean by clever?
–What do we mean by efficient?
2
Basic Terminologies & Asymptotic
Notations

3. Definition
•Data Structure is a way of collecting and organizing data
in such a way that we can perform operations on these
data in an effective way. Data Structures is about
rendering data elements in terms of some relationship, for
better organization and storage.
•Data structures can implement one or more particular 
abstract data types (ADT), which are the means of
specifying the contract of operations and their complexity
.
Data Structures - Introduction 3

4. Picking the best
Data Structure for the job
•The data structure you pick needs to support the
operations you need
•Ideally it supports the operations you will use most
often in an efficient manner
•Examples of operations:
–A List with operations insert and delete
–A Stack with operations push and pop
4
Basic Terminologies & Asymptotic
Notations

5. Terminology
•Abstract Data Type (ADT)
–Mathematical description of an object with set of
operations on the object. Useful building block.
•Algorithm
–A high level, language independent, description of
a step-by-step process
•Data structure
–A specific family of algorithms for implementing
an abstract data type.
•Implementation of data structure
–A specific implementation in a specific language
5
Basic Terminologies & Asymptotic
Notations

6. Terminology
•Data
Data refers to value or set of values.
e.g.Marks obtained by the students.
•Data type
data type is a classification identifying one of various types
of data, such as floating-point, integer, or Boolean, that
determines the possible values for that type; the operations
that can be done on values of that type; and the way values
of that type can be stored
Data Structures - Introduction 6

7. Terminology
•Primitive data type:
These are basic data types that are provided by the
programming language with built-in support. These data
types are native to the language. This data type is
supported by machine directly
•Variable
Variable is a symbolic name given to some known or
unknown quantity or information, for the purpose of
allowing the name to be used independently of the
information it represents.
Data Structures - Introduction 7

8. Terminology
•Record
Collection of related data items is known as record. The
elements of records are usually Called fields or members .
Records are distinguished from arrays by the fact that
their number of fields is typically fixed, each field has a
name, and that each field may have a different type.
•Program
A sequence of instructions that a computer can
interpret and execute.
Data Structures - Introduction 8

9. Terminology examples
•A stack is an abstract data type supporting push, pop and
isEmpty operations
•A stack data structure could use an array, a linked list, or
anything that can hold data
•One stack implementation is java.util.Stack; another is
java.util.LinkedList
9
Basic Terminologies & Asymptotic
Notations

10. Concepts vs. Mechanisms
•Abstract
•Pseudocode
•Algorithm
–A sequence of high-level,
language independent
operations, which may act
upon an abstracted view
of data.
•Abstract Data Type (ADT)
–A mathematical
description of an object
and the set of operations
on the object.
•Concrete
•Specific programming language
•Program
–A sequence of operations in a
specific programming language,
which may act upon real data in
the form of numbers, images,
sound, etc.
•Data structure
–A specific way in which a
program’s data is represented,
which reflects the
programmer’s design
choices/goals.
10

11. Why So Many Data Structures?
Ideal data structure:
“fast”, “elegant”, memory efficient
Generates tensions:
–time vs. space
–performance vs. elegance
–generality vs. simplicity
–one operation’s performance vs. another’s
The study of data structures is the study
of tradeoffs. That’s why we have so
many of them!
11Basic Terminologies & Asymptotic
Notations