So far, when we have needed to store a list of values, we have used a vector (or the ArrayList that we built). Those structures are a particular way to store a sequence of items in memory. They allocate an array and use that array to store the items. Then it gives us an interface to work with those items in a particular way (push_back, size, etc...).
Most of the time, when we are using the structure, all we care about is what we can do with the data. We don’t care how the data is stored or how the operations are implemented. As long as a push_back adds an item to the end of the list, we don’t care how it does that. This idea is known as an abstract data type (ADT).
An abstract data type (ADT) describes what operations are allowed on that data, but not how the data is stored or how the operations are implemented. For example, a list ADT might define operations like:
add(item) — Add an item to the list (like push_back)
The list ADT does not say anything about how the list is stored or how those operations are implemented. It just says what operations are available and what they do.
An ArrayList is one way to implement a list ADT. The particular implementation will affect the performance of various operations. We already know that in an ArrayList it is much easier to add an item to the end of the list than it is to insert an item at the front of the list. (Which is why std::vector doesn’t provide a push_front.)
If we use a different technology to implement the list ADT, we can get different performance characteristics. In the coming sections, we will explore implementing a list without using an array. A different implementation will often offer different performance trade-offs.
The advantage of defining and using an abstract data type is that we can change the implementation without changing the code that uses it. Code that relies on a “list” can easily switch from using an ArrayList to some other implementation. For lists in particular, there is no one best implementation. Different implementations have different performance trade-offs, and the best choice depends on how the list will be used. Thinking in terms of the list ADT allows us to write code that can more easily switch between different implementations.
