To implement an ADT, the programmer must do two things:
- choose an concrete data representation of the abstract data, using data type that already exist
- implement each of the allowabel operations in terms of program instructions
Our choice may be based on:
- time efficiency (the speed at which the algorithms execute)
- space efficiency (the economical use of memory space)
- simplicity and readability of the algorithms
Categories of ADT operations
The basic operations that are performed on an abstract data type fall into different categories. Such as:
Constructor: An operation that creates a new instance (variable) of an ADT. For example: creating a new instance of a list
Transformer: An operation that builds a new value of the ADT, given one or more previous values of the type. For example: inserting an item in a list or deleting an item from a list.
Observer: An operation that allows us to observe the state of an instance of an ADT without changing it. For example: checking if a list is empty or searching a list for a target.
Iterator: This is less common operation, it allows us to process all components in an instance of an ADT. For example: printing the items of a list.
Mutators (setters): Changing the value of an attribute
Accessors (getters): getting the value of an attribute
Reference: wikipedia, acm, answers
