6: ADTs in the Java Libraries: Stacks, Queues, Deques#
In Computing, we simulate almost everything, building up abstractions using our primitives (and then further abstractions using past abstractions). A Java library is simply a pre-written Java class that puts together data and methods in a meaningful way. A library is often an abstract data type (ADT), which is simply a collection of data (representation) and the operations on that data. The official Java libraries have been thoroughly tested, so when we use them, we are already starting at a higher level of programming.
However, we should never use them “blindly” – we must be aware of the space and time complexities of the algorithms in cases where these might be important to our own run-time or space usage.
Most of the time, we do not need to know the exact implementation details. For example, we don’t need to know whether the data uses an array or a linked list, or whether there is a size field for a collection. If we know the complexity, we can guess the implementation. For example, if size can be obtained in \(θ(1)\) then likely there is an explicit field; if size can be obtained in \(θ(n)\) then likely there is a sequential search happening. When a data type is packaged up, available where we do not need to know the exact implementation, this is called encapsulation. We simply declare something of the data type and use the public methods that are available, without thinking much about the underlying particulars[1].
The Work Of Generations
We are fortunate in Computing that we have decades of work that is available for our use via libraries, AKA data structures or ADTs. We do not often need to start a project completely from scratch. It is still important to know some of the inner workings of these data structures.