Transcript Abstract Data Type

Abstract Data Type
EnhanceEdu
Agenda







Abstraction
Real time example
Definition of Abstract Data Type
Difference between abstract data type and data
structure
Different ADTs
Dictionary ADT
Operations in Dictionary ADT.
EnhanceEdu
Abstraction

Hiding unnecessary details is known as
abstraction.

Only presenting an interface , not the
implementation part .

i.e. only an interface is shown and
implementation part is hidden .

An essential element of object oriented
programming is abstraction.
EnhanceEdu
Real time example

Human manage complexity through abstraction.

People don’t think of a car as combination of tens
of thousands of parts. But as a single well defined
object.

This abstraction allows humans to drive the car
easily without being overwhelmed by the
complexity of the parts that form a car.
EnhanceEdu
Contd..






User just need to know about the parts and their
operations.
How to use the steering, breaks, gears, etc
But, not concerned with the Mechanisms of
Steering, breaks and gears.
To turn left, rotate the steering towards left side.
Same thing applies to ADTs.
User should be knowing about the various
functions in an ADT and what are the parameters
he need to pass to call a function.
EnhanceEdu
Abstract data type
EnhanceEdu
Difference between Abstract Data Type
and Data Structure.

Data Structure



A construct that is defined in a program
language to store collection of data.
Examples: arrays
ADTs and Data Structures are not the
same.


Data Abstraction:
Results in wall of ADT operations between data
structures and the program that access the
data within this data structure.
EnhanceEdu
Example for difference.
EnhanceEdu
Separation of interface from
implementations

When realized in a computer program, the ADT is
represented by an interface, which shields a
corresponding implementation.

Users of an ADT are concerned with the interface,
but not the implementation, as the
implementation can change in the future. (This
supports the principle of information hiding, or
protecting the program from design decisions that
are subject to change.)
EnhanceEdu
Difference between Abstract data type
and abstract data structure



There is a distinction, although sometimes
subtle, between the abstract data type and the
data structure used in its implementation.
For example, a List ADT can be represented
using an array-based implementation or a
linked-list implementation.
A List is an abstract data type with welldefined operations (add element, remove
element, etc.) while a linked-list is a pointerbased data structure that can be used to
create a representation of a List.
EnhanceEdu
Contd..
Similarly, a Binary Search Tree ADT can
be represented in several ways: binary
tree, AVL tree, red-black tree, array, etc.
 Regardless of the implementation, the
Binary Search Tree always has the same
operations (insert, remove, find, etc.)

EnhanceEdu
ADT
•
Abstract data types (ADT) typically seen in
textbooks and implemented in programming
languages (or their libraries) include:

Associative array

Dictionary
Complex number
Priority queue
Container
Dequeue
List
Queue
Set
Multimap
Stack
String
Tree











EnhanceEdu
Dictionary






Searching for the meaning of a word.
Each word in the dictionary has associated
meaning.
Here the word is the key, meaning is the
value.
All the words are arranged in alphabetical
order , which makes retrieving of data easy
and efficient.
Same thing applies to Dictionary in Java.
But, implementation part i.e. arrangement of
data differs from one data structure to
another.
EnhanceEdu
Dictionary(ADT)

The Dictionary class is the abstract parent of any
class, such as Hash table, which maps keys to
values.

Every key and every value is an object. In any
one Dictionary object, every key is associated
with at most one value.

Given a Dictionary and a key, the associated
element can be looked up.
EnhanceEdu
Methods.
Dictionary() is the constructor to create
object for this class.
 The various operations that could be
performed are
elements(), get(Objecy key) , isEmpty()
,keys(),
put(key k,value v), remove(object key),
size() etc

EnhanceEdu
For example:

Consider student details like roll as key and name
as value.
value
key
Create an instance for dictionary class
Dictionary dc = new Dictionary();
1
To insert values into the dictionary .
2
dc.put(1,”ramu”);
dc.put(2,”ajay”);

EnhanceEdu
ramu
ajay
Contd..
dc.elements();
Returns an enumeration of the elements in the
dictionary.
• dc.size();
Returns the size of the structure i.e. value 2.
• dc.isEmpty();
Returns true if the dictionary is empty.
• dc.get(1);
Returns the value associated with this key i.e.
ramu.

EnhanceEdu
Contd..
dc.remove(1);
Removes the key and its associated value
from the dictionary.
 dc.equals(key1,key2);
Compares key1 with key2.

EnhanceEdu
Program
EnhanceEdu
EnhanceEdu