Think of a light switch: you can turn it on or off without knowing whether it uses a toggle or buttons. An abstract data type (ADT) works the same way. It specifies the operations available to a user and what they do, without prescribing the internal design. section 7.4 section 7.1
An ADT is the first of three levels. A data structure refines it by specifying how data is organized and the computational complexity of its operations. An implementation refines the data structure into code for a particular programming language. One ADT can have several data structures, and one data structure can serve several ADTs. section 7.2
To define an ADT, make its interface a clear contract:
- Name the operations and their arguments and return values. section 7.10
- Specify each operation’s behavior and side effects, including changes to the collection. section 7.10
- Leave storage choices and performance guarantees to the data-structure design. section 7.2
A bag
A bag has insert(x) to add an element and iterate() to visit its elements. Duplicates are allowed, but iteration order is not guaranteed; searching and removal are not offered. That is a complete behavioral contract, even though it says nothing about whether the bag uses an array or a linked list. section 7.10 section 7.13
An array viewed at different levels
As an ADT, an array is an ordered sequence whose elements can be accessed by index. A data-structure definition can additionally require constant-time access. A language-level implementation must settle concrete questions such as memory layout. section 7.3
Table 7.1 Examples of abstraction versus implementation (view table figure)
| Abstraction (ADT) |
Implementation (DS) |
|---|---|
| Vehicle |
Car Truck Motorbike |
| Seat |
Chair Sofa Armchair Beanbag chair |
| List |
Dynamic array Linked list |
| Stack |
Dynamic array Linked list |
| Queue |
Dynamic array Linked list |
Compare the list, stack, and queue abstractions: each can be refined using a dynamic array or a linked list. section 7.2
