CS2040 Lecture Note #2 ADT

Abstract Data Type

1. Software engineering Issues

- Program Design Principals

       a. Abstraction

            Using Java Interface

             Concentrate on what can be done and not how

       b. Coupling

           Classes should not interdepend on each other

       c. Coherent

           Class is one entity

           Clear logical grouping of all functionalities

       d. Information Hiding

           Only expose necessary info to the outside

             If class q use T, whatever class changes the T function, q should not be affected

            However, this does not mean that its completely isolating the class. 

            q does not know how T does the work but knows how to call and what it produces

            Information hiding can apply to data 

            - Data abstraction : What can do to collection of data, seperated from how to do it

            - Data structure: Construct that store a collection of data

            - ADT : Collection of data and specification on the operation on the data

             e.g add, remove, query

Data structure is a construct that can be defined within a programming language to store a collection of data

ADT is a collection of data together with a specification of a set of operation on that data.

Specification indicate what the operations do but not how to implement them

Data stuctures are part of an ADT implementation

-> when a language does not support a necessary data operation, we need to creat our own ADT

The wall of ADT operations isolates a data structure from the program that uses it,

An interface is what the class understand and use the ADT

The interface is the WALL

Java's predefined ADT

E.g int, boolean,String

Some adt:

- Constructors

int[] x = {1,2};

- Mutators

x[1] = 4;

- Accessors 

int y = x[1] + x[0];

ADT are like a class that contains operations of data types.

Refer to  slide 19 Lecture 4

Java Interface

Can be use to specify common behavior for a set of unrelated classes.

It can also have constant definition: public static final

One such example is the comparable interface that uses the compareTo method

Next ADT and Linked List>