16.1 Abstract Data Types
An Abstract Data Type (ADT) is defined only by its operations, not by its implementation.
For example in Project 1A, we developed an ArrayDeque
and a LinkedListDeque
that had the same methods, but how those methods were written was very different. In this case, we say that ArrayDeque
and LinkedListDeque
are implementations of the Deque
ADT.
From this description, we see that ADT's and interfaces are somewhat related. Conceptually, Deque
is an interface for which ArrayDeque
and LinkedListDeque
are its implementations. In code, in order to express this relationship, we have the ArrayDeque
and LinkedListDeque
classes inherit from the Deque
interface.
Some commonly used ADT's are:
Stacks: Structures that support last-in first-out retrieval of elements
push(int x)
: puts x on the top of the stackint pop()
: takes the element on the top of the stack
Lists: an ordered set of elements
add(int i)
: adds an elementint get(int i)
: gets element at index i
Sets: an unordered set of unique elements (no repeats)
add(int i)
: adds an elementcontains(int i)
: returns a boolean for whether or not the set contains the value
Maps: set of key/value pairs
put(K key, V value)
: puts a key value pair into the mapV get(K key)
: gets the value corresponding to the key
Note: the bolded ADT's are a subinterfaces of a bigger overarching interface called Collections.
Below we show the relationships between the interfaces and classes. Interfaces are in white, classes are in blue.
ADT's allow us to make use of object oriented programming in an efficient and elegant way. For example, you saw in Project 1C how you can use an ArrayDeque or a LinkedListArrayDeque interchangeably because they are both part of the Deque ADT.
In the following chapters, we will work on defining some more ADT's and enumerating their different implementations.
Last updated