These are data types that allow us to separate the concern of the interface of a data type from the underlying implementation details. The common ADTs are stacks (LIFO) and queue (FIFO).
With ADTs we do not concern ourselves with how the data type has been implemented e.g. how the code manages memory. Rather, we simply use the functions/methods associated with the data type to interact with it.
Stacks and Queues
Stacks are LIFO (last in first out) like a stack of plates where the last plate added to the top of the stack is the first plate we must remove in order to access the other plates. The common operations are:
- Push (add a plate to the top of the stack)
- Pop (remove the plate at the top of the stack)
Queues are FIFO (first in first out) like a line at the bank. The first person in the line will be the first person allowed to enter the bank. The common operations are:
- Enqueue (add someone to the back of the line)
- Dequeue (remove the person at the front of the line)
Notice that the operations used to work with these data types do not involve any detail of the underlying memory being used to store the information for the various nodes (e.g. plates and persons).
We ask the code to run the operations without thinking about how the data type was implemented i.e. the code that manages the pointers and nodes in the underlying linked list.