abstract data structure

In computer science, an abstract data type (ADT) is a mathematical model for data types, 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. This mathematical model contrasts with ''data structures'', which are concrete representations of data, and are the point of view of an implementer, not a user. For example, a stack has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a list or an array. Another example is a set which stores values, without any particular order, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in".

ADTs are a theoretical concept, used in formal semantics and program verification and, less strictly, in the design and analysis of algorithms, data structures, and software systems. Most mainstream computer languages do not directly support formally specifying ADTs. However, various language features correspond to certain aspects of implementing ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract. For example, in modular programming, the module declares procedures that correspond to the ADT operations, often with comments that describe the constraints. This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs, but the module only informally defines an ADT. 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 engineering.

History

ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language. Algebraic specification was an important subject of research in CS around 1980 and almost a synonym for abstract data types at that time. It has a mathematical foundation in universal algebra.

Definition

Formally, an ADT is analogous to an algebraic structure in mathematics, consisting of a domain, a collection of operations, and a set of constraints the operations must satisfy. The domain is often defined implicitly, for example the free object over the set of ADT operations. The interface of the ADT typically refers only to the domain and 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, which are considered behavior. There are two main styles of formal specifications for behavior, axiomatic semantics and operational semantics.

Despite not being part of the interface, the constraints are still important to the definition of the ADT; for example a stack and a queue have similar add element/remove element interfaces, but it is the constraints that distinguish last-in-first-out from first-in-first-out behavior. The constraints do not consist only of equations such as but also logical formulas.

Operational semantics

In the spirit of imperative programming, an abstract data structure is conceived as an entity that is ''mutable''—meaning that there is a notion of time and the ADT may be in different states at different times. Operations then change the state of the ADT over time; 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. The constraints are typically specified in prose.

Auxiliary operations

Presentations of ADTs are often limited in scope to only key operations. More thorough presentations often specify auxiliary operations on ADTs, such as:
* (), that yields a new instance of the ADT;
* (''s'', ''t''), that tests whether two instances' states are equivalent in some sense;
* (''s''), that computes some standard hash function from the instance's state;
* (''s'') or (''s''), that produces a human-readable representation of the instance's state.
These names are illustrative and may vary between authors. In imperative-style ADT definitions, one often finds also:
* (''s''), that prepares a newly created instance ''s'' for further operations, or resets it to some "initial state";
* (''s'', ''t''), that puts instance ''s'' in a state equivalent to that of ''t'';
* (''t''), that performs ''s'' ← (), (''s'', ''t''), and returns ''s'';
* (''s'') or (''s''), that reclaims the memory and other resources used by ''s''.

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

Restricted types

The definition of an ADT often restricts the stored value(s) for its instances, to members of a specific set ''X'' called the ''range'' of those variables. For example, an abstract variable may be constrained to only store integers. As in programming languages, such restrictions may simplify the description and analysis of algorithms, and improve its readability.

Aliasing

In the operational style, it is often unclear how multiple instances are handled and if modifying one instance may affect others. A common style of defining ADTs writes the operations as if only one instance exists during the execution of the algorithm, and all operations are applied to that instance. For example, a stack may have operations (''x'') and (), 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 stack example below) to every operation that uses or modifies the implicit instance. Some ADTs cannot be meaningfully defined without allowing multiple instances, for example when a single operation takes two distinct instances of the ADT as parameters, such as a operation on sets or a operation on lists.

The multiple instance style is sometimes combined with an aliasing axiom, namely that the result of () is distinct from any instance already in use by the algorithm. Implementations of ADTs may still reuse memory and allow implementations of () to yield a previously created instance; however, defining that such an instance even is "reused" is difficult in the ADT formalism.

More generally, this axiom may be strengthened to exclude also partial aliasing with other instances, so that composite ADTs (such as trees or records) and reference-style ADTs (such as pointers) may be assumed to be completely disjoint. For example, when extending the definition of an abstract variable to include abstract records, operations upon a field ''F'' of a record variable ''R'', clearly involve ''F'', which is distinct from, but also a part of, ''R''. A partial aliasing axiom would state that changing a field of one record variable does not affect any other records.

Complexity analysis

Some authors also include the computational complexity ("cost") of each operation, both in terms of time (for computing operations) and space (for representing values), to aid in analysis of algorithms. For example, one may specify that each operation takes the same time and each value takes the same space regardless of the state of the ADT, or that there is a "size" of the ADT and the operations are linear, quadratic, etc. in the size of the ADT. Alexander Stepanov, designer of the C++ Standard Template Library, included complexity guarantees in the STL specification, arguing:

Other authors disagree, arguing that a stack ADT is the same whether it is implemented with a linked list or an array, despite the difference in operation costs, and that an ADT specification should be independent of implementation.

Examples

Abstract variable

An abstract variable may be regarded as the simplest non-trivial ADT, with the semantics of an imperative variable. It admits two operations, and . Operational definitions are often written in terms of abstract variables. In the axiomatic semantics, letting $V$ be the type of the abstract variable and $X$ be the type of its contents, is a function $V \to X$ and is a function of type $V \to X \to V$. The main constraint is that always returns the value ''x'' used in the most recent operation on the same variable ''V'', i.e. . We may also require that overwrites the value fully, .

In the operational semantics, (''V'') is a procedure that returns the current value in the location ''V'', and (''V'', ''x'') is a procedure with return type that stores the value ''x'' in the location ''V''. The constraints are described informally as that reads are consistent with writes. As in many programming languages, the operation (''V'', ''x'') is often written ''V'' ← ''x'' (or some similar notation), and (''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 (''V'',(''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 .

This definition does not say anything about the result of evaluating (''V'') when ''V'' is ''un-initialized'', that is, before performing any operation on ''V''. Fetching before storing can be disallowed, defined to have a certain result, or left unspecified. There are some algorithms whose efficiency depends on the assumption that such a is legal, and returns some arbitrary value in the variable's range.

Abstract stack

An abstract stack is a last-in-first-out structure, It is generally defined by three key operations: , that inserts a data item onto the stack; , that removes a data item from it; and or , that accesses a data item on top of the stack without removal. A complete abstract stack definition includes also a Boolean-valued function (''S'') and a () operation that returns an initial stack instance.

In the axiomatic semantics, letting $S$ be the type of stack states and $X$ be the type of values contained in the stack, these could have the types $push : S \to X \to S$, $pop : S \to (S,X)$, $top : S \to X$, $create : S$, and $empty : S \to \mathbb$. In the axiomatic semantics, creating the initial stack is a "trivial" operation, and always returns the same distinguished state. Therefore, it is often designated by a special symbol like Λ or "()". The operation predicate can then be written simply as $s = \Lambda$ or $s \neq \Lambda$.

The constraints are then , , () = T (a newly created stack is empty), ((''S'', ''x'')) = F (pushing something into a stack makes it non-empty). These axioms do not define the effect of (''s'') or (''s''), unless ''s'' is a stack state returned by a . Since leaves the stack non-empty, those two operations can be defined to be invalid when ''s'' = Λ. From these axioms (and the lack of side effects), it can be deduced that (Λ, ''x'') ≠ Λ. Also, (''s'', ''x'') = (''t'', ''y'') if and only if ''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 this case, it means that every stack is a ''finite'' sequence of values, that becomes the empty stack (Λ) after a finite number of s. By themselves, the axioms above do not exclude the existence of infinite stacks (that can be ped forever, each time yielding a different state) or circular stacks (that return to the same state after a finite number of s). In particular, they do not exclude states ''s'' such that (''s'') = ''s'' or (''s'', ''x'') = ''s'' for some ''x''. However, since one cannot obtain such stack states from the initial stack state with the given operations, they are assumed "not to exist".

In the operational definition of an abstract stack, (''S'', ''x'') returns nothing and (''S'') yields the value as the result but not the new state of the stack. There is then 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'' ← (''S'') restores ''S'' to the state it had before the (''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:
:

Unlike the axiomatic semantics, the operational semantics can suffer from aliasing. 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 .

Boom hierarchy

A more involved example is the Boom hierarchy of the binary tree, list, bag and set abstract data types. All these data types can be declared by three operations: ''null'', which constructs the empty container, ''single'', which constructs a container from a single element and ''append'', which combines two containers of the same type. The complete specification for the four data types can then be given by successively adding the following rules over these operations:
:

Access to the data can be specified by pattern-matching over the three operations, e.g. a ''member'' function for these containers by:
:
Care must be taken to ensure that the function is invariant under the relevant rules for the data type. Within each of the equivalence classes implied by the chosen subset of equations, it has to yield the same result for all of its members.

Common ADTs

Some common ADTs, which have proved useful in a great variety of applications, are

* Collection
* Container
* List
* String
* Set
* Multiset
* Map
* Multimap
* Graph
* Tree
* Stack
* Queue
* Priority queue
* Double-ended queue
* Double-ended priority queue

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases