Abstract data type

abstract data typesabstract data structureabstractabstract data type (ADT)abstract descriptionabstract typeabstract typesADTdata abstractiondata types
In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.wikipedia
166 Related Articles

Data structure

data structuresstructurestructures
This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
Data structures serve as the basis for abstract data types (ADT).

Design by contract

contractscontractdesign contract
However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract. The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and design by contract methodologies for software development.
It prescribes that software designers should define formal, precise and verifiable interface specifications for software components, which extend the ordinary definition of abstract data types with preconditions, postconditions and invariants.

CLU (programming language)

CLUCLU languageCLU programming language
ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language.
Key contributions include abstract data types, call-by-sharing, iterators, multiple return values (a form of parallel assignment), type-safe parameterized types, and type-safe variant types.

Stack (abstract data type)

stackLIFOstacks
For example, an abstract stack, which is a last-in-first-out structure, could be defined by three operations: push, that inserts a data item onto the stack; pop, that removes a data item from it; and peek or top, that accesses a data item on top of the stack without removal.

Opaque data type

opaqueopaque data structureopaque object
However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract.
Opaque data types are frequently used to implement abstract data types.

Abstract machine

abstract computerabstract computer modelcomputational models
What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively.
Abstract data types can be specified in terms of their operational semantics on an abstract machine.

Queue (abstract data type)

queuequeuesFIFO queues
An abstract queue, which is a first-in-first-out structure, would also have three operations: enqueue, that inserts a data item into the queue; dequeue, that removes the first data item from it; and front, that accesses and serves the first data item in the queue.
Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes.

Data type

typedatatypetypes
In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.
Any type that does not specify an implementation is an abstract data type.

Object-oriented programming

object-orientedobject orientedobject-oriented programming language
The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and design by contract methodologies for software development.
This feature is known as dynamic dispatch, and distinguishes an object from an abstract data type (or module), which has a fixed (static) implementation of the operations for all instances.

Linked list

singly linked listlinked listsdynamic list
This view actually mirrors the behavior of some concrete implementations, such as linked lists with hash cons. Thus, for example, an abstract stack can be implemented by a linked list or by an array.
They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis.

List (abstract data type)

listlistsList (computing)
In computer science, a list or sequence is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once.

Set (abstract data type)

setsetsset data structure
In computer science, a set is an abstract data type that can store unique values, without any particular order.

Associative array

mapdictionariesdictionary
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

Abstract graphical data type

Abstract Graphical Data Types
An extension of ADT for computer graphics was proposed in 1979: an abstract graphical data type (AGDT).
An abstract graphical data type (AGDT) is an extension of an abstract data type for computer graphics.

Tree (data structure)

treetree data structuretrees
In computer science, a tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Container (abstract data type)

containercollection classcontainers
In computer science, a container is a class, a data structure, or an abstract data type (ADT) whose instances are collections of other objects.

Priority queue

priority queuingPriority queuesmin-priority queue
In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.

Graph (abstract data type)

graphgraphsGraph (data structure)
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics; specifically, the field of graph theory.

Double-ended queue

dequedequesdequeues
In computer science, a double-ended queue (abbreviated to deque, pronounced deck ) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Interface (computing)

interfaceinterfacescomputer interface
ADTs are often implemented as modules: the module's interface declares procedures that correspond to the ADT operations, sometimes with comments that describe the constraints.
In some object-oriented languages, especially those without full multiple inheritance, the term interface is used to define an abstract type that contains no data but defines behaviours as method signatures.

Multimap

more than one
In computer science, a multimap (sometimes also multihash or multidict) is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key.

Type system

dynamicstatictype checking
Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the type systems of programming languages.
Existential types are frequently used in connection with record types to represent modules and abstract data types, due to their ability to separate implementation from interface.

Array data structure

arrayarraysvector
Thus, for example, an abstract stack can be implemented by a linked list or by an array.
The term is also used, especially in the description of algorithms, to mean associative array or "abstract array", a theoretical computer science model (an abstract data type or ADT) intended to capture the essential properties of arrays.

Abstraction (computer science)

abstractiondata abstractionabstract
The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and design by contract methodologies for software development.
For example, one could define an abstract data type called lookup table which uniquely associates keys with values, and in which values may be retrieved by specifying their corresponding keys.

Object (computer science)

objectobjectsdata object
In this model an ADT is typically implemented as a class, and each instance of the ADT is usually an object of that class.
Object-orientation is simply the logical extension of older techniques such as structured programming and abstract data types.