1.5 Implementing An ADT

Abstractions make problem solving easier, but programs require a concrete implementation in order to execute. Thus, after defining the ADT, we need to provide an implementation in an appropriate language. In our case, we will always use Python and class definitions, but any programming language could be used.

Given the definition of an abstract data type, how do we decide the best way to implement it? For simple abstract data types, there are a couple of questions that can be asked, the answers to which will help guide the implementation. First, given the ADT definition that represents some entity, what is an appropriate way to represent that entity? That is, what data do we need to store and manage to correctly implement the ADT? For example, suppose we are trying to implement an ADT for a six-sided die that can be rolled using a random number generator. What information do we need to represent the die? The die has six faces, but only one of them can be facing upwards. Thus, the top face can be represented using a number between 1 and 6. Next, for each piece of data needed to represent the ADT, what type of data should be stored? Should it be an integer, a floating-point, a string, a Boolean or some other user-defined type? For the die, the number representing the face value would best be represented as an integer since we need a whole number between 1 and 6. There can be multiple ways to implement an ADT, but no matter the implementation, it is important that all of the operations be implemented correctly and the ADT function as defined.