In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, an abstract data type (ADT) is a
mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used in the natural sciences (such as physics, ...
for
data type
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
s. An abstract data type is defined by its behavior (
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
) from the point of view of a ''
user
Ancient Egyptian roles
* User (ancient Egyptian official), an ancient Egyptian nomarch (governor) of the Eighth Dynasty
* Useramen, an ancient Egyptian vizier also called "User"
Other uses
* User (computing), a person (or software) using an ...
'', of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s, which are concrete representations of data, and are the point of view of an implementer, not a user.
Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
in mathematics. What is meant by "behaviour" 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
Axiomatic semantics is an approach based on mathematical logic for proving the correctness of computer programs. It is closely related to Hoare logic.
Axiomatic semantics define the meaning of a command in a program by describing its effect on ass ...
and
operational semantics
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execu ...
of an
abstract machine, respectively. Some authors also include the
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
("cost"), both in terms of time (for computing operations) and space (for representing values). In practice, many common data types are not ADTs, as the abstraction is not perfect, and users must be aware of issues like
arithmetic overflow that are due to the representation. For example, integers are often stored as fixed-width values (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.
ADTs are a theoretical concept, in computer science, used in the design and analysis of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s,
data structures
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
, and
software systems
A software system is a system of intercommunicating components based on software forming part of a computer system (a combination of hardware and software). It "consists of a number of separate programs, configuration files, which are used to ...
, and do not correspond to specific features of
computer languages—mainstream computer languages do not directly support formally specified ADTs. However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include
abstract types,
opaque data type
In computer science, an opaque data type is a data type whose concrete data structure is not defined in an interface. This enforces information hiding, since its values can only be manipulated by calling subroutines that have access to the missing ...
s,
protocols
Protocol may refer to:
Sociology and politics
* Protocol (politics), a formal agreement between nation states
* Protocol (diplomacy), the etiquette of diplomacy and affairs of state
* Etiquette, a code of personal behavior
Science and technology
...
, and
design by contract. ADTs were first proposed by
Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the
CLU language.
Abstract data types
For example,
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s are an ADT, defined as the values ..., −2, −1, 0, 1, 2, ..., and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc., which behave according to familiar mathematics (with care for
integer division
Division is one of the four basic operations of arithmetic, the ways that numbers are combined to make new numbers. The other operations are addition, subtraction, and multiplication.
At an elementary level the division of two natural numbers ...
), independently of how the integers are represented by the computer. Explicitly, "behavior" includes obeying various axioms (associativity and commutativity of addition, etc.), and preconditions on operations (cannot divide by zero). Typically integers are represented in a data structure as
binary number
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
s, most often as
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
, but might be
binary-coded decimal
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for ...
or in
ones' complement
The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sing ...
, but for most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.
An ADT consists not only of operations but also of a domain of values, and of constraints on the defined operations. An "interface" typically refers only to the operations, and perhaps some of the constraints on the operations, such as pre-conditions and post-conditions; but not to other constraints such as relations between the operations.
For example, an abstract
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
, 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. An abstract
queue __NOTOC__
Queue () may refer to:
* Queue area, or queue, a line or area where people wait for goods or services
Arts, entertainment, and media
*''ACM Queue'', a computer magazine
* The Queue (Sorokin novel), ''The Queue'' (Sorokin novel), a 198 ...
, 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. If these were the entire definitions, there would be no way of differentiating these two data types and their very different expected ordering behavior. Thus, a constraint is introduced that for a stack specifies that each pop always returns (and removes) the most recently pushed item that has not been popped yet, and for a queue (in contrast) specifies that pop operates on the least recently pushed item.
When
analyzing the efficiency of algorithms, one may also specify that all operations take the same time no matter how many data items have been pushed into the stack, and that the stack uses a constant amount of storage for each element. However, time bounds are not always considered part of the definition of an ADT.
Introduction
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 system
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
s of programming languages. However, an ADT may be
implemented by specific
data type
In computer science and computer programming, a data type (or simply type) is a set of possible values and a set of allowed operations on it. A data type tells the compiler or interpreter how the programmer intends to use the data. Most progra ...
s or
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s, in many ways and in many programming languages; or described in a
formal specification language. ADTs are often implemented as
modules
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a sy ...
: the module's
interface
Interface or interfacing may refer to:
Academic journals
* ''Interface'' (journal), by the Electrochemical Society
* ''Interface, Journal of Applied Linguistics'', now merged with ''ITL International Journal of Applied Linguistics''
* '' Inte ...
declares procedures that correspond to the ADT operations, sometimes with
comments that describe the constraints. This
information hiding
In computer science, information hiding is the principle of segregation of the ''design decisions'' in a computer program that are most likely to change, thus protecting other parts of the program from extensive modification if the design decisio ...
strategy allows the implementation of the module to be changed without disturbing the
client programs.
The term abstract data type can also be regarded as a generalized approach of a number of
algebraic structures
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
, such as lattices, groups, and rings. The notion of abstract data types is related to the concept of
data abstraction
In software engineering and computer science, abstraction is:
* The process of removing or generalizing physical, spatial, or temporal details or attributes in the study of objects or systems to focus attention on details of greater importance ...
, important in
object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pr ...
and
design by contract methodologies for
software development
Software development is the process of conceiving, specifying, designing, programming, documenting, testing, and bug fixing involved in creating and maintaining applications, frameworks, or other software components. Software development invol ...
.
Defining an abstract data type
An abstract data type is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.
There are no standard conventions for defining them. A broad division may be drawn between "imperative" (or "operational") and "functional" (or "axiomatic") definition styles.
Imperative-style definition
In the theory of
imperative programming
In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program c ...
languages, an abstract data structure is conceived as an entity that is ''mutable''—meaning that it may be in different ''states'' at different times. Some operations may change the state of the ADT; therefore, the order in which operations are evaluated is important, and the same operation on the same entities may have different effects if executed at different times. This is analogous to the instructions of a computer, or the commands and procedures of an imperative language. To underscore this view it is customary to say that the operations are ''executed'' or ''applied'', rather than ''evaluated'', similar to the imperative style often used when describing abstract algorithms. (See
The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
by
Donald Knuth for more details).
Abstract variable
Imperative-style definitions of ADT often depend on the concept of an ''abstract variable'', which may be regarded as the simplest non-trivial ADT. An abstract variable ''V'' is a mutable entity that admits two operations:
*
store(''V'', ''x'') where ''x'' is a ''value'' of unspecified nature;
*
fetch(''V''), that yields a value,
with the constraint that
*
fetch(''V'') always returns the value ''x'' used in the most recent
store(''V'', ''x'') operation on the same variable ''V''.
Fetching before storing can be disallowed, defined to have a certain result, or (less desirably), leave the behavior unspecified.
As in many programming languages, the operation
store(''V'', ''x'') is often written ''V'' ← ''x'' (or some similar notation), and
fetch(''V'') is implied whenever a variable ''V'' is used in a context where a value is required. Thus, for example, ''V'' ← ''V'' + 1 is commonly understood to be a shorthand for
store(''V'',
fetch(''V'') + 1).
In this definition, it is implicitly assumed that names are always distinct: storing a value into a variable ''U'' has no effect on the state of a distinct variable ''V''. To make this assumption explicit, one could add the constraint that
* if ''U'' and ''V'' are distinct variables, the sequence is equivalent to .
More generally, ADT definitions often assume that any operation that changes the state of one ADT instance has no effect on the state of any other instance of the same ADT, unless the ADT axioms define certain instances as connected (see
aliased) in a specific way. The most common such connections include:
* Aliasing, in which two or more names refer to the exact same data object.
* Composition, in which an ADT is defined to contain instances of (the same or other) ADTs.
* Reference, in which an ADT is defined to refer to instance of (the same or other) ADTs.
For example, when extending the definition of an abstract variable to include abstract
records
A record, recording or records may refer to:
An item or collection of data Computing
* Record (computer science), a data structure
** Record, or row (database), a set of fields in a database related to one entity
** Boot sector or boot record, ...
, operations upon a field ''F'' of a record variable ''R'', clearly involve ''F'', which is distinct from, but also a part of, ''R''.
The definition of an ADT may restrict the stored value(s) for its instances, to members of a specific set ''X'' called the ''range'' of those variables. For example, an ADT for an aggregate such as a Stack or Queue, may constrain all items in the queue to be integers, or at least to all be of a single type (see
homogeneity
Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
). As in programming languages, such restrictions may simplify the description and
analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...
, and improve its readability.
Note that this definition does not imply anything about the result of evaluating
fetch(''V'') when ''V'' is ''un-initialized'', that is, before performing any
store operation on ''V''. An algorithm that does so may be considered invalid, either (a) because the ADT prohibits such an operation, or (b) simply because its effect is not defined by the ADT. However, there are some important algorithms whose efficiency strongly depends on the assumption that such a
fetch is legal, and returns some arbitrary value in the variable's range.)
Instance creation
Some algorithms need to create new instances of some ADT (such as new variables, or new stacks). To describe such algorithms, one usually includes in the ADT definition a
create() operation that yields an instance of the ADT, usually with axioms equivalent to
* the result of
create() is distinct from any instance already in use by the algorithm.
This axiom may be strengthened to exclude also partial aliasing with other instances. For practical use, such as axiom may still allow implementations of
create() to yield a previously created instance that has become inaccessible to the program; however, defining that such an instance even is "the same" is difficult, especially in the abstract (though even a re-used block of memory is only "the same object" in certain senses).
Example: abstract stack (imperative)
As another example, an imperative-style definition of an abstract stack could specify that the state of a stack ''S'' can be modified only by the operations
*
push(''S'', ''x''), where ''x'' is some ''value'' of unspecified nature;
*
pop(''S''), that yields a value as a result,
with the constraint that
* For any value ''x'' and any abstract variable ''V'', the sequence of operations is equivalent to ''V'' ← ''x''.
Since the assignment ''V'' ← ''x'', by definition, cannot change the state of ''S'', this condition implies that ''V'' ←
pop(''S'') restores ''S'' to the state it had before the
push(''S'', ''x''). From this condition and from the properties of abstract variables, it follows, for example, that the sequence
:
where ''x'', ''y'', and ''z'' are any values, and ''U'', ''V'', ''W'' are pairwise distinct variables, is equivalent to
:
Here it is implicitly assumed that operations on a stack instance do not modify the state of any other ADT instance, including other stacks; that is,
* For any values ''x'', ''y'', and any distinct stacks ''S'' and ''T'', the sequence is equivalent to .
An abstract stack definition usually includes also a
Boolean
Any kind of logic, function, expression, or theory based on the work of George Boole is considered Boolean.
Related to this, "Boolean" may refer to:
* Boolean data type, a form of data with only two possible values (usually "true" and "false" ...
-valued function
empty(''S'') and a
create() operation that returns a stack instance, with axioms equivalent to
*
create() ≠ ''S'' for any prior stack ''S'' (a newly created stack is distinct from all previous stacks);
*
empty(
create()) (a newly created stack is empty);
*
not empty(
push(''S'', ''x'')) (pushing something into a stack makes it non-empty).
Single-instance style
Sometimes an ADT is defined as if only one instance of it existed during the execution of the algorithm, and all operations were applied to that instance, which is not explicitly notated. For example, the abstract stack above could have been defined with operations
push(''x'') and
pop(), that operate on ''the'' only existing stack. ADT definitions in this style can be easily rewritten to admit multiple coexisting instances of the ADT, by adding an explicit instance parameter (like ''S'' in the previous example) to every operation that uses or modifies the implicit instance.
On the other hand, some ADTs cannot be meaningfully defined without assuming multiple instances. This is the case when a single operation takes two distinct instances of the ADT as parameters. For an example, consider augmenting the definition of the abstract stack with an operation
compare(''S'', ''T'') that checks whether the stacks ''S'' and ''T'' contain the same items in the same order.
Functional-style definition
Another way to define an ADT, closer to the spirit of
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
, is to consider each state of the structure as a separate entity. In this view, any operation that modifies the ADT is modelled as a
mathematical function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
that takes the old state as an argument and returns the new state as part of the result. Unlike the imperative operations, these functions have no
side effect
In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
s. Therefore, the order in which they are evaluated is immaterial, and the same operation applied to the same arguments (including the same input states) will always return the same results (and output states).
In the functional view, in particular, there is no way (or need) to define an "abstract variable" with the semantics of imperative variables (namely, with
fetch and
store operations). Instead of storing values into variables, one passes them as arguments to functions.
Example: abstract stack (functional)
For example, a complete functional-style definition of an abstract stack could use the three operations:
*
push: takes a stack state and an arbitrary value, returns a stack state;
*
top: takes a stack state, returns a value;
*
pop: takes a stack state, returns a stack state.
In a functional-style definition there is no need for a
create operation. Indeed, there is no notion of "stack instance". The stack states can be thought of as being potential states of a single stack structure, and two-stack states that contain the same values in the same order are considered to be identical states. This view actually mirrors the behavior of some concrete implementations, such as
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
s with
hash cons In computer science, particularly in functional programming, hash consing is a technique used to share values that are structurally equal. The term ''hash consing'' originates from implementations of Lisp that attempt to reuse cons cells that have ...
.
Instead of
create(), a functional-style definition of an abstract stack may assume the existence of a special stack state, the ''empty stack'', designated by a special symbol like Λ or "()"; or define a
bottom() operation that takes no arguments and returns this special stack state. Note that the axioms imply that
*
push(Λ, ''x'') ≠ Λ.
In a functional-style definition of a stack one does not need an
empty predicate: instead, one can test whether a stack is empty by testing whether it is equal to Λ.
Note that these axioms do not define the effect of
top(''s'') or
pop(''s''), unless ''s'' is a stack state returned by a
push. Since
push leaves the stack non-empty, those two operations are undefined (hence invalid) when ''s'' = Λ. On the other hand, the axioms (and the lack of side effects) imply that
push(''s'', ''x'') =
push(''t'', ''y'')
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
''x'' = ''y'' and ''s'' = ''t''.
As in some other branches of mathematics, it is customary to assume also that the stack states are only those whose existence can be proved from the axioms in a finite number of steps. In the abstract stack example above, this rule means that every stack is a ''finite'' sequence of values, that becomes the empty stack (Λ) after a finite number of
pops. By themselves, the axioms above do not exclude the existence of infinite stacks (that can be
popped forever, each time yielding a different state) or circular stacks (that return to the same state after a finite number of
pops). In particular, they do not exclude states ''s'' such that
pop(''s'') = ''s'' or
push(''s'', ''x'') = ''s'' for some ''x''. However, since one cannot obtain such stack states with the given operations, they are assumed "not to exist".
Whether to include complexity
Aside from the behavior in terms of axioms, it is also possible to include, in the definition of an ADT operation, their
algorithmic complexity
Algorithmic may refer to:
*Algorithm, step-by-step instructions for a calculation
**Algorithmic art, art made by an algorithm
**Algorithmic composition, music made by an algorithm
** Algorithmic trading, trading decisions made by an algorithm
**Alg ...
.
Alexander Stepanov, designer of the C++
Standard Template Library
The Standard Template Library (STL) is a Library (computer science), software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components ...
, included complexity guarantees in the STL specification, arguing:
Advantages of abstract data typing
Encapsulation
Abstraction provides a promise that any implementation of the ADT has certain properties and abilities; knowing these is all that is required to make use of an ADT object.it make to used with Data type in programming language
Perimitive and non perimitive data type.
Localization of change
Code that uses an ADT object will not need to be edited if the implementation of the ADT is changed. Since any changes to the implementation must still comply with the interface, and since code using an ADT object may only refer to properties and abilities specified in the interface, changes may be made to the implementation without requiring any changes in code where the ADT is used.
Flexibility
Different implementations of the ADT, having all the same properties and abilities, are equivalent and may be used somewhat interchangeably in code that uses the ADT. This gives a great deal of flexibility when using ADT objects in different situations. For example, different implementations of the ADT may be more efficient in different situations; it is possible to use each in the situation where they are preferable, thus increasing overall efficiency.
Typical operations
Some operations that are often specified for ADTs (possibly under other names) are
*
compare(''s'', ''t''), that tests whether two instances' states are equivalent in some sense;
*
hash(''s''), that computes some standard
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
from the instance's state;
*
print(''s'') or
show(''s''), that produces a human-readable representation of the instance's state.
In imperative-style ADT definitions, one often finds also
*
create(), that yields a new instance of the ADT;
*
initialize(''s''), that prepares a newly created instance ''s'' for further operations, or resets it to some "initial state";
*
copy(''s'', ''t''), that puts instance ''s'' in a state equivalent to that of ''t'';
*
clone(''t''), that performs ''s'' ←
create(),
copy(''s'', ''t''), and returns ''s'';
*
free(''s'') or
destroy(''s''), that reclaims the memory and other resources used by ''s''.
The
free operation is not normally relevant or meaningful, since ADTs are theoretical entities that do not "use memory". However, it may be necessary when one needs to analyze the storage used by an algorithm that uses the ADT. In that case, one needs additional axioms that specify how much memory each ADT instance uses, as a function of its state, and how much of it is returned to the pool by
free.
Examples
Some common ADTs, which have proved useful in a great variety of applications, are
*
Collection
Collection or Collections may refer to:
* Cash collection, the function of an accounts receivable department
* Collection (church), money donated by the congregation during a church service
* Collection agency, agency to collect cash
* Collectio ...
*
Container
*
List
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
*
String
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
*
Set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
*
Multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
*
Map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
*
Multimap
In computer science, a multimap (sometimes also multihash, multidict or multidictionary) 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. Both m ...
*
Graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
*
Tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
*
Stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
*
Queue __NOTOC__
Queue () may refer to:
* Queue area, or queue, a line or area where people wait for goods or services
Arts, entertainment, and media
*''ACM Queue'', a computer magazine
* The Queue (Sorokin novel), ''The Queue'' (Sorokin novel), a 198 ...
*
Priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
*
Double-ended queue
*
Double-ended priority queue
In computer science, a double-ended priority queue (DEPQ)[abstract graphical data type
An abstract graphical data type (AGDT) is an extension of an abstract data type for computer graphics. AGDTs provide the advantages of the ADTs with facilities to build graphical objects in a structured way. Formally, an AGDT may be defined as a "c ...](_blank)
(AGDT). It was introduced by
Nadia Magnenat Thalmann
Nadia Magnenat Thalmann is a computer graphics scientist and robotician and is the founder and head of MIRALab at the University of Geneva. She has chaired the Institute for Media Innovation at Nanyang Technological University (NTU), Singapore ...
, and
Daniel Thalmann
Prof. Daniel Thalmann is a Swiss and Canadian computer scientist and a pioneer in Virtual humans. He is currently Honorary Professor at EPFL, Switzerland and Director of Research Development at MIRALab Sarl in Geneva, Switzerland.
Biography
A ...
. AGDTs provide the advantages of ADTs with facilities to build graphical objects in a structured way.
Implementation
Implementing an ADT means providing one
procedure or function for each abstract operation. The ADT instances are represented by some concrete
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
that is manipulated by those procedures, according to the ADT's specifications.
Usually, there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented by a
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
or by an
array.
In order to prevent clients from depending on the implementation, an ADT is often packaged as an ''
opaque data type
In computer science, an opaque data type is a data type whose concrete data structure is not defined in an interface. This enforces information hiding, since its values can only be manipulated by calling subroutines that have access to the missing ...
'' in one or more
modules
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a sy ...
, whose interface contains only the signature (number and types of the parameters and results) of the operations. The implementation of the module—namely, the bodies of the procedures and the concrete data structure used—can then be hidden from most clients of the module. This makes it possible to change the implementation without affecting the clients. If the implementation is exposed, it is known instead as a ''transparent data type.''
When implementing an ADT, each instance (in imperative-style definitions) or each state (in functional-style definitions) is usually represented by a
handle
A handle is a part of, or attachment to, an object that allows it to be grasped and manipulated by hand. The design of each type of handle involves substantial ergonomic issues, even where these are dealt with intuitively or by following tra ...
of some sort.
[, definition 4.4.]
Modern object-oriented languages, such as
C++ and
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
, support a form of abstract data types. When a class is used as a type, it is an abstract type that refers to a hidden representation. In this model, an ADT is typically implemented as a
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
, and each instance of the ADT is usually an
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ai ...
of that class. The module's interface typically declares the constructors as ordinary procedures, and most of the other ADT operations as
methods
Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to:
*Scien ...
of that class. However, such an approach does not easily encapsulate multiple representational variants found in an ADT. It also can undermine the extensibility of object-oriented programs. In a pure object-oriented program that uses interfaces as types, types refer to behaviours, not representations.
Example: implementation of the abstract stack
As an example, here is an implementation of the abstract stack above in the
C programming language
''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...
.
Imperative-style interface
An imperative-style interface might be:
typedef struct stack_Rep stack_Rep; // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T; // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item; // type: value stored in stack instance (arbitrary address)
stack_T stack_create(void); // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s); // removes the top item from the stack and returns it
bool stack_empty(stack_T s); // checks whether stack is empty
This interface could be used in the following manner:
#include // includes the stack interface
stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x); // adds the address of x at the top of the stack
void* y = stack_pop(s); // removes the address of x from the stack and returns it
if (stack_empty(s)) // does something if stack is empty
This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether the stack state ''s'' continues to exist after a call ''x'' ←
pop(''s'').
In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and the array size).
Functional-style interface
Functional-style ADT definitions are more appropriate for functional programming languages, and vice versa. However, one can provide a functional-style interface even in an imperative language like C. For example:
typedef struct stack_Rep stack_Rep; // type: stack state representation (opaque record)
typedef stack_Rep* stack_T; // type: handle to a stack state (opaque pointer)
typedef void* stack_Item; // type: value of a stack state (arbitrary address)
stack_T stack_empty(void); // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s); // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s); // returns the top item of the stack state
ADT libraries
Many modern programming languages, such as C++ and Java, come with standard libraries that implement several common ADTs, such as those listed above.
Built-in abstract data types
The specification of some programming languages is intentionally vague about the representation of certain built-in data types, defining only the operations that can be done on them. Therefore, those types can be viewed as "built-in ADTs". Examples are the arrays in many scripting languages, such as
Awk
AWK (''awk'') is a domain-specific language designed for text processing and typically used as a data extraction and reporting tool. Like sed and grep, it is a filter, and is a standard feature of most Unix-like operating systems.
The AWK langu ...
,
Lua
Lua or LUA may refer to:
Science and technology
* Lua (programming language)
* Latvia University of Agriculture
* Last universal ancestor, in evolution
Ethnicity and language
* Lua people, of Laos
* Lawa people, of Thailand sometimes referred t ...
, and
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
, which can be regarded as an implementation of the abstract list.
See also
*
Concept (generic programming)
*
Formal methods
In computer science, formal methods are mathematically rigorous techniques for the specification, development, and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the expec ...
*
Functional specification
A functional specification (also, ''functional spec'', ''specs'', ''functional specifications document (FSD)'', ''functional requirements specification'') in systems engineering and software development is a document that specifies the functio ...
*
Generalized algebraic data type In functional programming, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type) is a generalization of parametric algebraic data types.
Overview
In a GADT, the product co ...
*
Initial algebra
In mathematics, an initial algebra is an initial object in the category of -algebras for a given endofunctor . This initiality provides a general framework for induction and recursion.
Examples
Functor
Consider the endofunctor sending t ...
*
Liskov substitution principle
The Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called strong behavioral subtyping, that was initially introduced by Barbara Liskov in a 1988 conference keynote address titled ''Data abstraction and h ...
*
Type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
* ''
Walls and Mirrors
''Walls And Mirrors'' is a computer science textbook, for undergraduates taking a second computer science course (typically on the subject of data structures and algorithms), originally written by Paul Helman and Robert Veroff. The book attempts t ...
''
Notes
Citations
References
*
*
Further reading
*
External links
*
Abstract data typein
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
Dictionary of Algorithms and Data Structures
{{DEFAULTSORT:Abstract Data Type
Data types
Type theory