Intro to Abstract Data Types
Before we dive into Abstract data types (ADTs) let’s consider the meaning of abstraction. Abstraction is the quality of dealing with ideas rather than events. This is not only useful for programming, but it occurs in our daily lives without us even realizing it.
To put things into perspective, let's consider a common scenario of daily life where abstraction occurs such as eating at a restaurant. While dining at a restaurant we aren’t too concerned about how an order is prepared, we mainly care for the result. The complexity of our order is abstracted away by the kitchen, and we interface with the kitchen via the chefs and waiters. We aren’t focusing much of our energy on what occurs in the kitchen because all we care about is receiving the order we placed.
Abstract data types are not so different than the restaurant dining scenario since they are used to describe the interface by which data must adhere to. An interface is simply an abstract class whose behavior is defined by a set of rules or operations, but not it’s implementation. The user of the ADT does not need to know how the data type is implemented, and only requires knowledge of what the data type can do from an implementation-independent view.
Below are some examples of ADTs and for each, I’ve included some corresponding Data Structures (DS) or implementations for those who may have some prior knowledge on the topic or may want to look into specific details:
List ADT
The List ADT is an ordered collection of items of no particular order. Each item in the List has a position, starting from position zero. A simple representation of a List is shown below:
Keep in mind this is a basic representation of a List. The data is generally stored in key sequences comprised of a head structure consisting of count, pointers, and addresses of functions used to compare the data within the List. A DS implementation of a List ADT may be a Dynamic Array or a Linked List.
Stack ADT
A Stack is similar to a stack of objects in real life: books, cookies, plates; where objects from the stack are either placed or removed directly from the top, not the middle or end. This is known as LIFO ordering or Last In First Out. Therefore the Stack ADT is a linear data structure that supports insertion or deletion from the top of the stack.
As you may already be able to tell, the two main operations of a Stack are Push and Pop. A commonplace of this in action is on a browser’s navigation stack. While a new webpage is displaying, the address of the current page is pushed into a stack. The address of the previous page can be popped out of the stack.
Queue ADT
The Queue ADT is similar to the Stack ADT as they are both linear data structures. However, unlike the Stack ADT, Queues support insertion or deletion from either end of the sequence. So the key takeaway here is that operations take place at both ends.
You may think of a Queue similar to queues or lines in real life: enqueue items from the front, dequeued items from the back. The idea is to serve the person in the front rather than service people in the back. This is known as FIFO ordering or First In First Out, or other words “First come first served.”
A DS implementation of a Queue ADT may be a Linked List based Queue, an Array-based Queue, or a Stack-based Queue.
Map ADT
A Map ADT models a searchable collection of key-value mappings in which a unique key is mapped to a value. The main operations of a Map are: insert, find, delete.
Due to the ‘shape’ of its interface, a map is often referred to as a dictionary and we may think of this ADT as a dictionary in real life. A word is sought out as a ‘key’ and the corresponding definition as its ‘value’.
Since every value is mapped to a unique key, a key and a value are required to insert new mappings. However, we only need the key to find or remove mappings.
A DS implementation of a Map ADT may be a Tree-Map, Hash Map/Hash Table.
Conclusion
The goal of this article was to briefly describe the abstraction and implementation of data types. Before providing examples of ADTs, I mentioned how dealing with abstraction in computer science is not too different than dealing with abstractions in daily life. I would like to go over one more example of such using an ATM for the scenario, so we have another point of reference on the matter.
When we visit an ATM we are interfacing with, or interacting with, a screen with some form of input such as a touch screen or a TTS service. As a user of the ATM, we don’t place a high emphasis on the actual implementation and design of the ATM. We simply rely on the front end to guide us through basic banking functions such as reviewing banking data and making deposits or withdrawals. The front end creates the interface for the ATM, and the ATM abstracts away the process. Can you think of any examples of abstraction in your daily life? Let me know in the comments.
I hope you enjoyed reading and that I could have helped someone understand abstraction even a tiny bit. Special thanks to the references, I’ve used for this post, below. These references are also where I’ve obtained all the images used in this post. I plan to get more in-depth for each of the data structures with coding examples in upcoming posts. Cheers!
References
