I am currently learning about Abstract Data Types (ADTs), but I do not get the concept at all. Could someone please explain to me what this actually is? Also, what are collection, bag, and List ADTs? In simple terms?
"ADT" can also refer to an "algebraic data type", that is one made up of products and sums, and is a more well-defined concept (as evidenced by the currently 16 answers on the dup question linked).
Commented Apr 14, 2017 at 16:55Abstract Data Type(ADT) is a data type, where only behavior is defined but not implementation.
Opposite of ADT is Concrete Data Type (CDT), where it contains an implementation of ADT.
Examples:
List, Map, Queue, Set, Stack, Table, Tree, and Vector are ADTs. Each of these ADTs has many implementations i.e. CDT. The container is a high-level ADT of above all ADTs.
Real life example:
book is Abstract (Telephone Book is an implementation)
Abstract Data Type (ADT) may be associated with encapsulation characteristics and deals with both data and operations. Sorry, why are we defining abstract data type in terms of Algebra? Abstract Data Type is a programming concept; please define it in terms of programming. We can have private and public parts in an abstract data type. The abstract data type should not be defined in terms of implementation. The word 'abstract' means not clear; an example is abstract art. Arrays are not abstract Data Type (why?) in Java because they do not define their operations. @Premraj
Commented Dec 27, 2023 at 16:04Sorry in the above comment, I meant array and not arrays. Arrays is a buit-in Java class and hence an abstract data type.
Commented Dec 27, 2023 at 16:22 When you say Table is a Data Type - you mean tables as if SQL tables? Commented Aug 24 at 21:16The Abstact data type Wikipedia article has a lot to say.
In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations.
In slightly more concrete terms, you can take Java's List interface as an example. The interface doesn't explicitly define any behavior at all because there is no concrete List class. The interface only defines a set of methods that other classes (e.g. ArrayList and LinkedList ) must implement in order to be considered a List .
A collection is another abstract data type. In the case of Java's Collection interface, it's even more abstract than List , since
The List interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of the iterator , add , remove , equals , and hashCode methods.
A bag is also known as a multiset.
In mathematics, the notion of multiset (or bag) is a generalization of the notion of set in which members are allowed to appear more than once. For example, there is a unique set that contains the elements a and b and no others, but there are many multisets with this property, such as the multiset that contains two copies of a and one of b or the multiset that contains three copies of both a and b.
In Java, a Bag would be a collection that implements a very simple interface. You only need to be able to add items to a bag, check its size, and iterate over the items it contains. See Bag.java for an example implementation (from Sedgewick & Wayne's Algorithms 4th edition).
answered Aug 6, 2012 at 2:33 Bill the Lizard Bill the Lizard 404k 210 210 gold badges 572 572 silver badges 888 888 bronze badgesAn 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 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
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.
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.
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
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.
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.
