What is an abstract data type (ADT), and what does its specification contain?
An ADT describes a data structure by what it does, not how: it specifies the data it stores, the operations on that data, and the error conditions of those operations, while leaving the implementation open.
An ADT specification has three parts:
- Data — what is stored (the attributes).
- Operations — the methods, with what each one does to the data.
- Error conditions — what counts as a misuse and how it is reported.
A simple stock-exchange system as an ADT:
- Data: buy and sell orders.
- Operations:
order buy(stock, shares, price),order sell(stock, shares, price),void cancel(order). - Errors: buying or selling a stock that does not exist; cancelling an order that does not exist.
Nothing in that description says whether orders sit in an array, a linked list or a database. That separation is the point: code that uses the ADT depends only on the operations, so the implementation can be swapped for a faster one without changing the callers.
Tip: Stack, Queue and Deque are ADTs. "Array-based stack" and "linked-list stack" are two implementations of the same ADT, with different performance and limits but the same operations.
Go deeper:
Abstract data type — the formal notion, with stack and queue as the standard examples.