- \n
- Defining an ADT by considering their characteristics<\/li>\n
- Understanding the algebraic form through which an ADT is defined<\/li>\n
- Common ADTs such as Queue, List, Stack, and Tree<\/li>\n
- Implementing ADTs as Data Structures<\/li>\n
- Custom implementation of a Queue in Python<\/li>\n
- Comparing ADTs to Objects<\/li>\n<\/ul>\n
Introduction<\/h2>\n
ADTs are among the most foundational concepts of computer science and have a wide range of applications. They describe the what<\/em> of a program’s functionality and leave the how<\/em> of it all up to developers. In seeking the definition of an abstract data type we can consider each part of the term as follows:<\/p>\n
- \n
- Abstract:<\/strong> Conceptual rather than concrete<\/li>\n
- Data:\u00a0<\/strong>Information formatted for use by a computer<\/li>\n
- Type:<\/strong> A category of objects with shared characteristics<\/li>\n<\/ul>\n
The terms\u00a0Data\u00a0<\/em>and\u00a0Type<\/em> are immediately recognized as related as their use as\u00a0Data Type<\/em> is common among all programming languages. This term is used to describe integers, booleans, floating-point values, and similar built-in features of most modern programming languages. Given this; let us borrow the following definition of abstract data type (Dale, 1996):<\/p>\n
A class of objects whose logical behavior is defined by a set of values and a set of operations.<\/em><\/p>\n
Abstract data types are almost poetically simplistic but can be difficult to grasp without some contrast to other concepts. In this article, we’ll consider the common characteristics of ADTs, how they are defined, implemented, and some examples of a custom implementation. Through this process, the underlying concepts of ADTs should become clearer.<\/p>\n
Characteristics of ADTs<\/h2>\n
ADTs are contrasted by Data Types (DT) such as Integers, Booleans, and Chars. These structures are characterized by their representation of values without operations. A key feature in defining ADTs is their abstraction<\/em> of operational details from users and developers.<\/p>\n
- \n
- Encapsulates a Data Type and<\/em> set of operations to manipulate the Type<\/li>\n
- Operations are only defined by inputs and outputs<\/li>\n
- Operation details are hidden from the user through encapsulation<\/li>\n
- Theoretical in nature<\/li>\n
- Define\u00a0what<\/em> is getting done not\u00a0how<\/em> it is getting done<\/li>\n
- Allows internal implementation details to change without<\/li>\n<\/ul>\n
An ADT may provide a complex implementation of a basic function of which a developer would be allowed access to the function without necessitating an awareness of its underlying logic.<\/p>\n
ADT Operation Types<\/h2>\n
![\"adt](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/1957\/adt-operation-type-categories-1-1024x576.jpg\" "\\"adt-operation-type-categories\\"")
<\/a>ADTs provide operations that are defined logically during implementation and can be categorized in one of a few limited broader groupings. (click to enlarge)<\/figcaption><\/figure>\n Abstract Data Types define necessary operations for implementation. These operations fall into three primary categories\u2014and several less common ones. These categories may be referred to by several names depending on context, language, or the mood of a developer on a particular day. Such categories include the following (Nell, 2010):<\/p>\n
- \n
- Constructors<\/strong> – Initializes an instance of an ADT<\/li>\n
- Transformers<\/strong> – Changes the state of an ADT (a.k.a.\u00a0mutator<\/em>)<\/li>\n
- Observers<\/strong> – Allows read-only access to ADT values without changing ADT State. a.k.a.\u00a0accessors<\/em>.<\/li>\n
- Destructor<\/strong> – Clears the State of an ADT before freeing of memory space<\/li>\n
- Iterator\u00a0<\/strong>– Allows the processing of ADT components in a one-by-one fashion.<\/li>\n<\/ul>\n
These are by no means an exhaustive list of possible operation types for ADTs. These are, however, quite common. It is also worth noting that ADT operators can fall into multiple categories. For example, an operator that merges two existing lists would be both a constructor and an observer (Thalmann, 1979.)<\/p>\n
ADT Creation<\/h2>\n
With all this talk of ADTs, one might begin to wonder how to create one. Perhaps the best way to discern between ADTs, Data Structures, Objects, and varying implementations is to consider the syntax by which they are created.<\/p>\n
The abstraction of ADTs is clearest when examining the syntax\u2014often expressed in algebraic form. Consider the following logical definition of a Queue ADT using algebraic syntax that describes the Signature<\/strong> and the Axioms<\/strong> (Dale, 1996):<\/p>\n
Queue<Item>\r\n\r\nSignature:\r\n isEmpty : Queue -> bool\r\n frontOf : Queue -> Item\r\n empty : -> Queue\r\n add : Queue -> Queue\r\n pop : Queue x Elem -> Queue\r\n\r\nAxioms:\r\n isEmpty(empty) = true\r\n isEmpty(enq(q, x)) = false\r\n frontOf(enq(q, x)) =\r\n if isEmpty(q) the x\r\n else frontOf(q);\r\n pop(add(q, x)) = \r\n if isEmpty(q) empty\r\n else add(pop(q), x);<\/pre>\n
The conceptual nature of ADTs is clear here\u2014no common programming language can do anything with this other than throw a syntax error. Between the name, signature, and axioms, however\u2014a developer can implement a language-specific Data Structure in accord with the Queue ADT expressed above.<\/p>\n
ADT Examples<\/h2>\n
![\"common](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/1957\/common-abstract-data-types-1-1024x576.jpg\" "\\"common-abstract-data-types\\"")
Common data structures implementing ADTs included Queues, Stacks, Lists, Trees, Linked Lists, and Hash Maps<\/figcaption><\/figure>\n Abstract Data Types can be difficult to grasp initially because\u2014well, they’re so\u00a0abstract<\/em>. They come in many forms intended for many purposes and some ADT implementation may differ ever-so-slightly that one can hardly discern them as separate Data Structure types.<\/p>\n
To make the collective ADT waters even muddier\u2014there are sub-categories of ADTs such as AGDTs where specific application contrasts them from broader concepts (Thalmann, 1979.) Some common ADTs that are implanted in the standard libraries of many modern programming languages include the following:<\/p>\n
- \n
- List<\/li>\n
- Stack<\/li>\n
- Queue<\/li>\n
- DeQue<\/li>\n
- Set<\/li>\n
- Graph<\/li>\n<\/ul>\n
These are by no means an exhaustive list and ADT types and implementations can easily number into the dozens<\/em>, if not hundreds<\/em>\u2014being separated only by slight nuances. To get a better feel for how an ADT becomes a Data Structure through implementation, let’s consider how we might go about implementing the Queue ADT outlined above in conceptual algebraic form.<\/p>\n
ADT Implementations<\/h2>\n
![\"queue](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/1957\/queue-implementation-1024x576.jpg\" "\\"queue-implementation\\"")
The Python Queue class is an example of a Data Structure that is an implementation of the Queue Abstract Data Type. Java Queues, C++ Queues, or any other such implementation would qualify as well.<\/figcaption><\/figure>\n An ADT is a concept that does not reveal the inner workings or make demands about how these workings are implemented. For example, a Queue is an ADT in concept only though the Java Queue is considered a Data Structure\u2014a.k.a. an implementation<\/em> of an ADT.<\/p>\n
Early computer languages only provided built-in data types. The constructs, such as an int, char, and double allowed developers to create routines that generated desired output by utilizing these features. In many cases, these routines involved an excess of syntax and complex logical flow.<\/p>\n
ADTs brought developers the ability to define their own data structures based on what was deemed convenient to their use case. This helped reduce syntax, increase extensibility, and provide a framework for the development of modern software engineering practices such as SOLID<\/a>.<\/p>\n
Custom Queue ADT Implementation<\/h2>\n
Queue objects can also provide removal access for the last object similar to Stacks. Through such usage, a Queue is considered a First-In-First-Out (FIFO)<\/strong> design. Other variations of the Queue include such ADTs as the Double-Ended Queue (DeQue) where items can be removed from the beginning or end of the contained collection. Let’s take a look at how the Queue ADT from above would be implemented in Python.<\/p>\n
from typing import Any, NoReturn\r\n\r\n\r\nclass Queue:\r\n\r\n def __init__(self):\r\n self._items = []\r\n\r\n def add(self, item: Any) -> NoReturn:\r\n \"\"\"Adds an item to the back of the queue\"\"\"\r\n self._items.append(item)\r\n\r\n def pop(self) -> Any:\r\n \"\"\"Removes the first item of the queue\"\"\"\r\n return self._items.pop(0)\r\n\r\n def isEmpty(self) -> bool:\r\n \"\"\"Checks if any items are in the queue\"\"\"\r\n return len(self._items) == 0\r\n\r\n def __str__(self):\r\n return str(self._items)\r\n\r\n\r\nif __name__ == '__main__':\r\n\r\n # Create a new Queue object\r\n q = Queue()\r\n\r\n # Have some items\r\n people = ['bob', 'alice', 'pat']\r\n\r\n # View starting queue\r\n print(\"Initial Queue:\", q)\r\n\r\n # Add everyone to the queue\r\n for person in people:\r\n\r\n print(\"\\tAdding:\", person)\r\n q.add(person)\r\n\r\n # View full queue\r\n print(\"Filled Queue:\", q)\r\n\r\n # Remove People, one-by-one\r\n while not q.isEmpty():\r\n\r\n next_person = q.pop()\r\n\r\n print(\"\\tNext Person:\", next_person)\r\n\r\n # Print resulting queue\r\n print(\"Final Queue:\", q)\r\n\r\n\r\n# Results\r\nInitial Queue: []\r\n Adding: bob\r\n Adding: alice\r\n Adding: pat\r\nFilled Queue: ['bob', 'alice', 'pat']\r\n Next Person: bob\r\n Next Person: alice\r\n Next Person: pat\r\nFinal Queue: []\r\n<\/pre>\n
- Transformers<\/strong> – Changes the state of an ADT (a.k.a.\u00a0mutator<\/em>)<\/li>\n
- Data:\u00a0<\/strong>Information formatted for use by a computer<\/li>\n
- Abstract:<\/strong> Conceptual rather than concrete<\/li>\n
![\"adt](\"https:\/\/www.alpharithms.com\/wp-content\/uploads\/1957\/adt-operation-type-categories-1.jpg\" "\\"adt-operation-type-categories\\"")
<\/a>