> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/16.-adts-and-bsts/16.1-abstract-data-types.md).

# 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 stack
  * `int pop()`: takes the element on the top of the stack
* **Lists**: an ordered set of elements
  * `add(int i)`: adds an element
  * `int get(int i)`: gets element at index i
* **Sets**: an unordered set of unique elements (no repeats)
  * `add(int i)`: adds an element
  * `contains(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 map
  * `V 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.

<figure><img src="/files/9QTo4XhhQPNCBkogFvMd" alt=""><figcaption><p>Common interfaces in Java and their implementations</p></figcaption></figure>

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.

{% embed url="<https://www.youtube.com/watch?v=aFOSePlOExw>" %}