What is the difference between abstract and concrete data structures?

Question

I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that

For dictionaries with very small numbers of bindings, it may make sense to implement the dictionary using an association list, a linked list of bindings. ...

The most frequently used general purpose implementation of an associative array is with a hash table: an array of bindings, together with a hash function that maps each possible key into an array index. ...

Dictionaries may also be stored in binary search trees or in data structures specialized to a particular type of keys such as radix trees, tries, Judy arrays, or van Emde Boas trees. ...

So, I think, my problem lies in that I don't know that associative array (i.e. map, or dictionary) is an abstract data type and hashing table is a concrete data structure, and different concrete data structures can be used to implement the same abstract data type.

My questions would be

• What is the difference and relation between abstract data structures and concrete data structures?

• What examples are for each of them (abstract and concrete data structures)? The more the better.

• Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

Answer 1

The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations described by the ADT (possibly with some probability of success in the case of randomized structures), but each concrete structure may make different guarantees of the running times of each operation. The choice of which concrete data structure to implement for a given ADT usually depends on the priorities of efficiency of each operation (including initializing the structure) and the complexity of implementing and maintaining the various data types. Some concrete data structures have excellent theoretical guarantees, but the overhead is such that a slightly less theoretically optimal data structure may be a better choice in practice.

There are far too many ADT and corresponding concrete structures to list in a single answer, but here are a few examples:

• A dictionary supports Find(x) queries. For an a key $x,ドル return the element in the dictionary with key $x,ドル if such an element exists. A dynamic dictionary also supports Insert(x) and Delete(x). Common implementations of a dictionary include different kinds of balanced binary search trees (e.g. red black tree) and various kinds of hash tables.

• In addition to Find an ADT may require support of successor(x) queries. That is, maintain a set of keys $S,ドル and given key $x,ドル find the smallest key $t \in S$ such that $s < t$. Concrete data structures which support the Successor ADT include various binary search trees, and more complicated structures such as an X-fast trie or van Emde Boas tree (if the keys are integers).

• A Priority Queue is an ADT that requires insert and delete-min operations (and sometimes other operations as well, such as find-min increase-key or delete-key). Data structures that implement the priority queue ADT include:

  1. an unsorted linked list, which has fast insert but slow delete-min.

  2. a sorted linked list which has fast delete-min but slow insert

  3. a binary search tree, which has logarithmic insert and delete-min, and $sort(n)$ initialization time.

  4. a binary heap which has logarithmic insert and delete-min, and linear time initialization.

  5. There are also other variants of heap implementations.

• An interval stabbing ADT maintains a set of intervals on the real line, and supports a stabbing(x) query, which returns the subset of intervals which contain (are stabbed by) the point $x$. Data structures that implement the stabbing query ADT include a Segment Tree and an Interval Tree.

Answer 2

Abstract data type describes what operations are available and what laws they obey. E.g. a dictionary allows you to store a value under a given key and to retrieve a value for a key, and promises that if you first store a value and then retrieve it with the same key, you will get the value you stored back. A stack has push and pop operations.

Concrete data type says how these operations are actually implemented.

• Tim: Thanks! Are there lists of which common data structure is which one, abstract or concrete?
• Alexey Romanov: Not a general list, but you may want to look at xlinux.nist.gov/dads