Notation of Abstract Data Type(ADT)
An abstract data type could be defined as a mathematical model with a collection of operations defined on it. A simple example is the set of integers together with the operations of union, intersection defined on the set.
The ADT's are generalizations of primitive data type(integer, char etc) and they encapsulate a data type in the sense that the definition of the type and all operations on that type localized to one section of the program. They are treated as a primitive data type outside the section in which the ADT and its operations are defined.
An implementation of an ADT is the translation into statements of a programming language of the declaration that defines a variable to be of that ADT, plus a procedure in that language for each operation of that ADT. The implementation of the ADT chooses a data structure to represent the ADT.
A useful tool for specifying the logical properties of data type is the abstract data type. Fundamentally, a data type is a collection of values and a set of operations on those values. That collection and those operations form a mathematical construct that may be implemented using a particular hardware and software data structure. The term "abstract data type" refers to the basic mathematical concept that defines the data type.
In defining an abstract data type as mathamatical concept, we are not concerned with space or time efficinecy. Those are implementation issue. Infact, the defination of ADT is not concerned with implementaion detail at all. It may not even be possible to implement a particular ADT on a particular piece of hardware or using a particular software system. For example, we have already seen that an ADT integer is not universally implementable.
To illustrate the concept of an ADT and my specification method, consider the ADT RATIONAL which corresponds to the mathematical concept of a rational number. A rational number is a number that can be expressed as the quotient of two integers. The operations on rational numbers that, we define are the creation of a rational number from two integers, addition, multiplication and testing for equality. The following is an initial specification of this ADT.
/* Value defination */
abstract typedef <integer, integer> RATIONAL;
condition RATIONAL [1]!=0;
/*Operator defination*/
abstract RATIONAL makerational (a,b)
int a,b;
preconditon b!=0;
postcondition makerational [0] =a;
makerational [1] =b;
abstract RATIONAL add [a,b]
RATIONAL a,b;
postcondition add[1] = = a[1] * b[1]
add[0] = a[0]*b[1]+b[0]*a[1]
abstract RATIONAL mult [a, b]
RATIONAL a,b;
postcondition mult[0] = = a[0]*b[a]
mult[1] = = a[1]*b[1]
abstract equal (a,b)
RATIONAL a,b;
postcondition equal = = |a[0] * b[1] = = b[0] * a[1];
An ADT consists of two parts:-
1) Value definition
2) Operation definition
1) Value Definition:-
The value definition defines the collection of values for the ADT and consists of two parts:
1) Definition Clause
2) Condition Clause
For example, the value definition for the ADT RATIONAL states that a RATIONAL value consists of two integers, the second of which does not equal to 0.
The keyword abstract typedef introduces a value definitions and the keyword condition is used to specify any conditions on the newly defined data type. In this definition the condition specifies that the denominator may not be 0. The definition clause is required, but the condition may not be necessary for every ADT.
2) Operator Definition:-
Each operator is defined as an abstract junction with three parts.
1)Header
2)Optional Preconditions
3)Optional Postconditions
For example the operator definition of the ADT RATIONAL includes the operations of creation (makerational), addition (add) and multiplication (mult) as well as a test for equality (equal). Let us consider the specification for multiplication first, since, it is the simplest. It contains a header and post-conditions, but no pre-conditions.
abstract RATIONAL mult [a,b]
RATIONAL a,b;
postcondition mult[0] = a[0]*b[0]
mult[1] = a[1]*b[1]
The header of this definition is the first two lines, which are just like a C function header. The keyword abstract indicates that it is not a C function but an ADT operator definition.
The post-condition specifies, what the operation does. In a post-condition, the name of the function (in this case, mult) is used to denote the result of an operation. Thus, mult [0] represents numerator of result and mult 1 represents the denominator of the result. That is it specifies, what conditions become true after the operation is executed. In this example the post-condition specifies that the neumerator of the result of a rational multiplication equals integer product of numerators of the two inputs and the denominator equals th einteger product of two denominators.
List
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. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream. Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item
The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists.
Image of a List
Bag
A bag is a collection of objects, where you can keep adding objects to the bag, but you cannot remove them once added to the bag. So with a bag data structure, you can collect all the objects, and then iterate through them. You will bags normally when you program in Java.
Image of a Bag
Collection
A collection in the Java sense refers to any class that implements the Collection interface. A collection in a generic sense is just a group of objects.
Image of collections