Summary: |
An Abstract Data Type (ADT) defines:
A well-specified collection of data (data state)
A set of operations that can be performed upon the data
Abstract – does not say anything about the details of how it actually works. To use data in a program, in the form defined by an ADT, you need to have a concrete (non-abstract) implementation – a data structure.
A data structure consists of
A base storage method (e.g. an array, a list, a tree, a …)
One or more algorithms that are used to access or modify that data
In an object oriented programming language such as Java it is convenient to define a data structure as a class, which contains
Fields to encapsulate the data state
Methods which encapsulate the algorithms for the operations
In Java, an ADT can be expressed as an interface which must be implemented by a class that defines a corresponding data structure.
It is possible to have more than one implementation of the same ADT by creating classes that implement the ADT interface. A programme can be written to use the interface type, and the actual data structure can be chosen at the time the program runs – polymorphism. This is useful as you can have different implementations of an ADT each of which performs better in a specific situation. You will see examples of this later in the module. |