Abstract Data Types

An abstract data type consists of 

- data having the same type
- operations on that data

It does not consist of

- how the data is stored
- how the operations are implemented

Thus, it is language independent.  



A Data Structure is an implementation of an ADT within a programming language (class)



To specify an ADT, we describe its data and specify the operations on the data.

The simplest ADT is the bag.  

It can help to do some code to use the ADT to help confirm your understanding.

Invalid calls, full bag?

You can 

- assume that they won't happen (client spec)
- ignore invalid situations (null op)
- try and guess
- return an indicator
- throw an exception

Just like picking classes (ADTs), this is a revision intensive process.

Use objects for all ADTs, must do type cast back to actual type.

Why?  Otherwise, you would need a "AppleBag", "OrangeBag", "GrapeBag", etc.

Notice that String is a special case, since all objects have a toString method.

What java component is closest to an ADT?

The interface.  You can use an interface class to provide a concrete definition for an ADT that
a developer can work from.


Using an ADT is like using a vending machine

- You can perform only the specific tasks that the machine's interface presents to you
- You must understand these tasks, e.g. you must know what to do to buy a coke
- You cannot see or access the inside of the machine, because a steel shell encapsulates it
- You can use the machine even though you don't know what happens inside
- If someone replaced the machine's inner mechanism with an improved version, leaving the interface
  unchanged, you could still use the machine the same way.

With an ADT

- The client can only perform the operations specific to the ADT (often declared by an interface).
- The client must adhere to the specifications of the operations that the ADT provides.  Thus, it must understand how to use them
- The client cannot access the data within the list without using an ADT operation. 
  The principle of encapsulation hides the data within the ADT
- THe Client can use the ADT, even though it can't access the data directly, and does not know how it is stored.
- If you cange the implementation, the client can use it in the same way, if the interface does not change.

Designing the ADT

Focus on What, not How