Operations needed to support abstract data types whether using dynamic memory allocation (linked data structures) or static memory allocation (array data structures) must fall into one of two categories:
- Primitive operations
- Useful operations (or other operations).
These operations specify the core operations, and any other operation that we require for the abstract data type can be defined in terms of these. You can think of the primitive operations as the building blocks of the data type. The primitive operations are the operations that we must implement in order to service the abstract data type.
It is useful to divide the primitive operations into four sub groups:
- Those that create the data type
- Those that destroy the data type
- Those that inspect or observe the data type
- Those that amend or change the data structure.
The specification of an abstract data type should state what an operation's input and outputs are, and definitely must mention when an input is changed. This falls short of completely specifying the implementation by procedures or functions. Of course, these details eventually need to be decided upon in order for the code to be written and are part of the implementation process.
However, this does not need to be decided until code-generation time; throughout the earlier stages of any design, the exact implementation (at the code level) can be left unspecified.