Transcript Abstract Data Types

CHAPTER 2
Data Design and Implementation
Definitions
Atomic or primitive type A data type whose elements are
single, non-decomposable data items
Composite type A data type whose elements are composed
of multiple data items
Structured composite type An organized collection of
components in which the organization determines the
means of accessing individual data components or subsets
of the collection
2
Atomic (Simple) and Composite Data
Types
3
Java’s Built-In Types
4
Definitions
Data abstraction The separation of a data type’s logical
properties from its implementation
Data encapsulation The separation of the representation of data
from the applications that use the data - a feature that
enforces information hiding
5
Collections
 A collection is an object that serves as a repository for other
objects.
 The Java Collections Framework contains classes that
represent collections of objects.
 In general, a collection refers to an object whose role is to
provide methods to add, remove and manage the elements
that are in the collection.
6
Collections
 The ArrayList class in the Collections Framework represents
a collection that is implemented with an array.
 Some collections are homogeneous – that is they contain
objects all of the same type., others are heterogeneous – e.g. a
ArrayList – so they can contain objects of different types.
7
Collections & ADT’s
 Collections can be implemented in a variety of ways. The
ArrayList uses an array.
 All operations are performed by using the methods that
perform operations on array.
 A data structure is a way to organize and access data
 A structure that is supposed to store a collection of
numbers in order should never allow unordered numbers
to occur
8
ABSTRACT DATA TYPES
An abstract data type is a collection of data and the
particular operations that are allowed on that data.
An ADT, therefore has a name, a domain of
values(data) and a set of operations that can be
performed (methods) on the data
An ADT is considered abstract because the operations
that you can perform on it are separated from the
underlying implementation.
9
ADT & Objects.
 We define a Stack ADT with LIFO(Last in-first out)
characteristics that requires special operations. We do not
specify whether the underlying implementation must be an
array or a linked list.
 The ADT specifies what can be done, not how it is to be
done ,
 The concept of the ADT is separate from the details of how it
stores its data and implements its operations.
10
Data Structures and Interfaces
Classes are perfect for ADT’s because all objects have a
well-defined interface whose implementation is hidden in
the class.
In Java, an ADT is expressed in an Interface and
implemented in a concrete data structure – specifically
in a class. The data structure is usually an array or a
linked list.
The class defines the data stored and how it is stored
and what operations can be performed on it. E.g. in a
Stack, items may only be taken from the top.
11
ADT’s – Abstract Data Types
 This encapsulated ADT is reusable and reliable because its
interaction with the rest of the system is controlled.
 E.g., for an ArrayList, access to the collection is allowed
anywhere in the array.
 ADT’s can be represented in classes by arrays or by linked
lists. The choice of an array or a linked list depends upon the
implementation
12
Basic Operations on Encapsulated Data
 A constructor is an operation that creates a new instance
(object) of the data type.
 Transformers (sometimes called mutators) are operations that
change the state of one or more of the data values. (setters
and getters)
13
Basic Operations on Encapsulated Data
 An observer is an operation that allows us to observe the state
of one or more of the data values with out changing them. The
method peek() in a stack
 An iterator is an operation that allows us to process all the
components in a data structure sequentially.
14
Data Levels of an ADT
 Logical (or abstract) level an ADT: Abstract view of the data
values (the domain) and the set of operations to manipulate
them. A Stack or Queue
 Application (or user) level: Here the application programmer
uses the ADT to solve a problem.
 Implementation level: A specific representation of the
structure to hold the data items, and the coding of the
operations in a programming language. Can be implemented
with either a linked list or an array
15
Communication between the Application Level and
Implementation Level
16
Combining our Built-In Types and Classes into
Versatile Hierarchies
1.
Aggregate objects—The instance variables of our objects
can themselves be references to objects.
2.
Arrays of objects—Simply define an array whose
components are objects.
17
Example of an Aggregate Object
Suppose we define:
public class Point
{
private int xValue
private int yValue
Then, we could define a new circle class as:
public class NewCircle
{
private Point location;// class contains another object
private float radius;
public boolean solid;
}
18
Designing ADTs
 Determine the general purpose.
 List the specific types of operations the application
program performs.
 Identify a set of public methods to be provided by the
ADT class that allow the application program to perform
the desired operations.
19
Designing ADTs


Identify other public methods which help make the ADT
generally usable.
Identify potential error situations and classify into
1. Those that are handled by throwing an exception
2.
Those that are handled by contract
3.
Those that are ignored.
20
Designing ADTs
6.
Define the needed exception classes.
7.
Decide how to structure the data.
8.
9.
Decide on a protection level for the identified data.
Identify private structures and methods.
10. Implement the ADT.
11. Create a test driver and test your ADT.
21
The ArrayList Class
 Part of the java.util package. Functionality is similar to
that of an array.
 However, an array list can grow and shrink; its size is not
fixed for its lifetime. Thus is virtually a vector.
 Hold variables of type Object.
 Capacities grow and shrink, depending on need.
22
Array Lists
 An array list has a size indicating how many objects it is
currently holding, and
 Has a capacity indicating how many elements the underlying
implementation could hold without having to be increased.
23
Implementing Lists with Arrays

An array implementation of a list could follow strategies
similar to those used for a queue – which we will look at
later

We could fix the beginning of the list at index 0 and shift
as needed when an element is added or removed

However, there is no avoiding a shift when an element in
the middle is added or removed

Let's examine the fixed version
24
24
ArrayList Operations
25
26
27
Use an array list when

Space is an issue.

The amount of space required may change from one
execution of the program to the next.

The actively used size of an array list changes during
execution.
5.
The position of an element in the array list has no relevance
to the application ad ArrayList is not ordered.
28