Abstract data types

Abstract data types #

An abstract data type (ADT) is an interface to access and manipulate a collection of elements.

For instance, a queue is an ADT that mimics the behavior of a “first come first served” queue (e.g. a waiting line at a post office). This interface typically exposes three methods:

  • one that checks whether the queue is empty,
  • one that takes as input an element and adds it to the end of the queue,
  • one that removes the first element of the queue and returns it.

An ADT may have several implementations. For instance, a queue may be implemented as an array or as a linked list (among others). Each implementation may have advantages and drawbacks (in terms of performance, memory footprint, parallelization opportunities, etc.) for different tasks (reading, writing, etc.).

A data structure (e.g. an array, a linked list, a hash table, etc.) is not an ADT, but a (concrete) way to store a collection of elements (values, objects, etc.) in memory. A data structure can be used to implement one or several ADT(s).

Some ADTs correspond to basic mathematical objects (set, tuple, function, etc.), and are therefore easy to understand and manipulate. They allow you to easily write code that is correct, but may be inefficient if you do not have a good understanding of underlying (concrete) data structure.

Another benefit of ADTs is that they can make your code significantly easier to read (thus requiring less documentation). For instance, if your program manipulates a collection of objects without duplicates and whose order is irrelevant, then you can simply use the Java interface Set, which is self-explanatory.

in Java #

Parameterized types #

An ADT in Java is usually a parameterized type, meaning that it has one or several types as parameter(s).

For instance, a set of strings in Java has type Set<String>.

Note. In Java, a primitive type (like int or bool) cannot be used as a type parameter, but a boxed type (like Integer or Boolean) can. For instance, the type Set<Integer> is valid.

The interface Collection #

In Java, many ADTs and data structures extend or implement the interface Collection (the only exception in this chapter is Map).

Among others, the interface Collection specifies the following methods (if E is the type of the elements in the collection):

  • int size()
  • boolean add(E e)
  • boolean contains(Object o)
  • boolean isEmpty()
  • boolean remove(E e),
  • etc.

Warning. Some of these methods are so-called “optional operations”, meaning that they may not be available for some implementations of Collection.

Like an array, a collection can be iterated over, for instance with a “foreach”-like loop:

for (E element: myCollection){
      ...
}

Another way to iterate over a collection consists in using an iterator.

Warning. Some collections (e.g. some implementations of the subinterface Set) do not offer any guarantee on the order of their elements!

External libraries #

Some external libraries provide additional implementations of Java’s ADTs.

For instance, Java has 19 native implementations of the ADT Map (e.g. HashMap,TreeMap, etc.). But Guava provides additional ones, like ImmutableMap, HashBiMap, etc.