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.
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.
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.
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.
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 */
This ADT could be used in the following manner:
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 */