What is the difference between abstract and concrete data structures?

2018-03-13 17:10:30

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

  • 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.

    2018-03-13 17:53:35
  • 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.

    2018-03-13 18:46:10