What is a Data Structure?
A primitive data type holds a single piece of data
e.g. in Java: int, long, char, boolean etc.
Legal operations on integers: + - * / ...
A data structure structures data!
Usually more than one piece of data
Should provide legal operations on the data
The data might be joined together (e.g. in an array): a collection
An Abstract Data Type (ADT) is a data type together with the operations, whose properties are specified independently of any particular implementation.
ADTs use the following principles:
Encapsulation: Providing data and operations on the data
Abstraction: hiding the details.
e.g. A class exhibits what it does through its methods; however, the details of how the methods work is hidden from the user
Modularity: Splitting a program into pieces.
An object-oriented program is a set of classes (data structures) which work together.
There is usually more than one way to split up a program
Modules (i.e. classes) should be as independent as possible
Cohesion: The extent to which methods in a class are related
Coupling: The extent to which a class uses other classes
Strive for high cohesion and low coupling
The ADTs we will examine have high cohesion and low coupling