|
In computing, 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. The interface provides a constructor, which returns an abstract handle to new data, and several operations, which are functions accepting the abstract handle as an argument. RAM (Random Access Memory) Look up computing in Wiktionary, the free dictionary. ...
A data type is a constraint placed upon the interpretation of data in a type system in computer programming. ...
Look up Implementation in Wiktionary, the free dictionary. ...
Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ...
Computer programming (often shortened to programming or coding) is the process of writing, testing, and maintaining the source code of computer programs. ...
An interface defines the communication boundary between two entities, such as a piece of software, a hardware device, or a user. ...
In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ...
Examples
Abstract data types (ADT) typically seen in textbooks and implemented in programming languages (or their libraries) include: An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ...
In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ...
A container is a type of data structure. ...
In computer science, a deque (short for double-ended queue) is a data structure for which elements can be added to or removed from the front or back. ...
Look up list in Wiktionary, the free dictionary. ...
A multimap 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. ...
A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing...
In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. ...
In computer science, the set is a collection of certain values without any particular order. ...
Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
A simple example binary tree In computer science, a tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. ...
Separation of interface and implementation When realized in a computer program, the ADT is represented by an interface, which shields a corresponding implementation. Users of an ADT are concerned with the interface, but not the implementation, as the implementation can change in the future. (This supports the principle of information hiding, or protecting the program from design decisions that are subject to change.) In computer science, the principle of information hiding is the hiding of design decisions in a computer program that are most likely to change, thus protecting other parts of the program from change if the design decision is changed. ...
The strength of an ADT is that the implementation is hidden from the user. Only the interface is published. This means that the ADT can be implemented in various ways, but as long as it adheres to the interface, user programs are unaffected.
There is a distinction, although sometimes subtle, between the abstract data type and the data structure used in its implementation. For example, a List ADT can be represented using an array-based implementation or a linked-list implementation. A List is an abstract data type with well-defined operations (add element, remove element, etc.) while a linked-list is a pointer-based data structure that can be used to create a representation of a List. The linked-list implementation is so commonly used to represent a List ADT that the terms are interchanged in common use.
Similarly, a Binary Search Tree ADT can be represented in several ways: binary tree, AVL tree, red-black tree, array, etc. Regardless of the implementation, the Binary Search Tree always has the same operations (insert, remove, find, etc.)
Separating the interface from the implementation doesn't always mean the user is unaware of the implementation method, but rather that they can't depend on any of the implementation details. For example, an ADT can be created using a scripting language or one that can be decompiled (like C). Even though the user can discover the implementation method, the construct can still be called an ADT as long as any client program that conforms to the interface is unaffected if the implementation changes. C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...
In object-oriented parlance, an ADT is a class; an instance of an ADT or class is an object. Some languages include a constructor for declaring ADTs or classes. For example, C++ and Java provide a class constructor for this purpose. In object-oriented programming, a class is a programming language construct that is used to group related instance variables and methods. ...
In strictly mathematical branches of computer science the term object is used in a purely mathematical sense to refer to any thing. While this interpretation is useful in the discussion of abstract theory, it is not concrete enough to serve as a primitive datatype in the discussion of more concrete...
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. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
A binary tree, a simple type of branching linked 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. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ...
Look up Implementation in Wiktionary, the free dictionary. ...
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. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...
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.
Concrete examples
Rational numbers as an abstract data type Rational numbers (numbers that can be written in the form a/b where a and b are integers) cannot be represented natively in a computer. A Rational ADT could be defined as shown below. In mathematics, a rational number is a number which can be expressed as a ratio of two integers. ...
Construction: Create an instance of a rational number ADT using two integers, a and b, where a represents the numerator and b represents the denominator.
Operations: addition, subtraction, multiplication, division, exponentiation, comparison, simplify, conversion to a real (floating point) number.
To be a complete specification, any operation should be defined in terms of the data. For example, when multiplying two rational numbers a/b and c/d, the result is defined as ( a c ) / ( b d ). Typically, inputs, outputs, preconditions, postconditions, and assumptions for the ADT are specified as well.
Stack
Interface The interface for a Stack ADT, written in C-style notation, might be: Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...
long stack_create(); /* create new instance of a stack */ void stack_push(long stack, void *item); /* push an item on the stack */ void *stack_pop(long stack); /* get item from top of stack */ void stack_delete(long stack); /* delete the stack */
Usage This ADT could be used in the following manner: long stack; struct foo *f; stack = stack_create(); /* create a stack */ stack_push(stack, f); /* add foo structure to stack */ f = stack_pop(stack); /* get top structure from stack */
Implementation variants The above stack ADT could be initially implemented using an array, and then later changed to a linked list, without affecting any user code. The number of ways a given ADT can be implemented depends on the programming language. For example, the above example could be written in C using a struct and an accompanying set of data structures using arrays or linked lists to store the entries; however, since the constructor function returns an abstract handle, the actual implementation is hidden from the user.
See also In generic programming, a concept is a description of supported operations on a type, including syntax and semantics. ...
External links - Abstract data type in NIST Dictionary of Algorithms and Datayoipoip Structures
|
Feeds |
Contact