ADT implementation

The specification of an ADT (Abstract Data Type) defines abstract data values and abstract operations for the user. Of course, the ADT must implemented in program code.

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

Previous post

Next post