Abstract data type

               An abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data.
Such a data type is abstract in the sense that it is independent of various concrete implementations. The definition can be mathematical, or it can be programmed as an interface. A first class ADT supports the creation of multiple instances of the ADT, and the interface normally provides a constructor, which returns an abstract handle to new data, and several operations, which are functions accepting the abstract handle as an argument.

              Abstract data types (ADT) typically seen in textbooks and implemented in programming languages (or their libraries) include:

Complex number, Container, Deque, List, Map, Multimap, Multiset, Priority queue
Queue, Set, Stack, String, and Tree.

            Abstract data structure

          An abstract data structure is an abstract storage for data defined in terms of the set of operations to be performed on data and computational complexity for performing these operations, regardless of the implementation in a concrete data structure.

         Selection of an abstract data structure is crucial in the design of efficient algorithms and in estimating their computational complexity, while selection of concrete data structures is important for efficient implementation of algorithms.

           This notion is very close to that of an abstract data type, used in the theory of programming languages. The names of many abstract data structures (and abstract data types) match the names of concrete data structures.

         Built-in abstract data types


           Because some ADTs are so common and useful in computer programs, some programming languages build implementations of ADTs into the language as native types or add them into their standard libraries. For instance, Perl arrays can be thought of as an implementation of the List or Deque ADTs and Perl hashes can be thought of in terms of Map or Table ADTs. The C++ Standard Library and Java libraries provide classes that implement the List, Stack, Queue, Map, Priority Queue, and String ADTs.