What is ADT? (Abstract Data Type)

I am currently studying about Abstract Data Types (ADT's) but I don't get the concept at all. Can someone please explain to me what this actually is? Also what is collection, bag, and List ADT? in simple terms?

Abstract 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:
Array, 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)

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

A truly abstract data type describes the properties of its instances without commitment to their representation or particular operations. For example the abstract (mathematical) type Integer is a discrete, unlimited, linearly ordered set of instances. A concrete type gives a specific representation for instances and implements a specific set of operations.

Actually Abstract Data Types is:

• Concepts or theoretical model that defines a data type logically
• Specifies set of data and set of operations that can be performed on that data
• Does not mention anything about how operations will be implemented
• "Existing as an idea but not having a physical idea"

For example, lets see specifications of some Abstract Data Types,

1. List Abstract Data Type: initialize(), get(), insert(), remove(), etc.

2. Stack Abstract Data Type: push(), pop(), peek(), isEmpty(), isNull(), etc.

3. Queue Abstract Data Type: enqueue(), dequeue(), size(), peek(), etc.

One of the simplest explanation given on Brilliant's wiki:

> Abstract data types, commonly abbreviated ADTs, are a way of > classifying data structures based on how they are used and the > behaviors they provide. They do not specify how the data structure > must be implemented or laid out in memory, but simply provide a > minimal expected interface and set of behaviors. For example, a stack > is an abstract data type that specifies a linear data structure with > LIFO (last in, first out) behavior. Stacks are commonly implemented > using arrays or linked lists, but a needlessly complicated > implementation using a binary search tree is still a valid > implementation. To be clear, it is incorrect to say that stacks are > arrays or vice versa. An array can be used as a stack. Likewise, a > stack can be implemented using an array. > > Since abstract data types don't specify an implementation, this means > it's also incorrect to talk about the time complexity of a given > abstract data type. An associative array may or may not have O(1) > average search times. An associative array that is implemented by a > hash table does have O(1) average search times. > > Example for ADT: List - can be implemented using Array and LinkedList, Queue, Deque, Stack, Associative array, Set.

https://brilliant.org/wiki/abstract-data-types/?subtopic=types-and-data-structures&chapter=abstract-data-types

#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

ADT are a set of data values and associated operations that are precisely independent of any paticular implementaition. The strength of an ADT is implementaion is hidden from the user.only interface is declared .This means that the ADT is various ways

Abstract Data type is a mathematical module that includes data with various operations. Implementation details are hidden and that's why it is called abstract. Abstraction allowed you to organise the complexity of the task by focusing on logical properties of data and actions.

In programming languages, a type is some data and the associated operations. An ADT is a user defined data aggregate and the operations over these data and is characterized by encapsulation, the data and operations are represented, or at list declared, in a single syntactic unit, and information hiding, only the relevant operations are visible for the user of the ADT, the ADT interface, in the same way that a normal data type in the programming language. It's an abstraction because the internal representation of the data and implementation of the operations are of no concern to the ADT user.

> Before defining abstract data types, let us considers the different > view of system-defined data types. We all know that by default all > primitive data types (int, float, etc.) support basic operations such > as addition and subtraction. The system provides the implementations > for the primitive data types. For user-defined data types, we also > need to define operations. The implementation for these operations can > be done when we want to actually use them. That means in general, > user-defined data types are defined along with their operations. > > To simplify the process of solving problems, we combine the data > structures with their operations and we call this "Abstract Data > Type". (ADT's). > > Commonly used ADT'S include: Linked List, Stacks, Queues, Binary Tree, > Dictionaries, Disjoint Sets (Union and find), Hash Tables and many > others. > > ADT's consist of two types: > > 1. Declaration of data. > > 2. Declaration of operation.

Simply Abstract Data Type is nothing but a set of operation and set of data is used for storing some other data efficiently in the machine. There is no need of any perticular type declaration. It just require a implementation of ADT.

To solve problems we combine the data structure with their operations. An ADT consists of two parts:

1. Declaration of Data.
2. Declaration of Operation.

Commonly used ADT's are Linked Lists, Stacks, Queues, Priority Queues, Trees etc. While defining ADTs we don't need to worry about implementation detals. They come into picture only when we want to use them.

Abstract data type are like user defined data type on which we can perform functions without knowing what is there inside the datatype and how the operations are performed on them . As the information is not exposed its abstracted. eg. List,Array, Stack, Queue. On Stack we can perform functions like Push, Pop but we are not sure how its being implemented behind the curtains.

ADT is a set of objects and operations, no where in an ADT’s definitions is there any mention of how the set of operations is implemented. Programmers who use collections only need to know how to instantiate and access data in some pre-determined manner, without concerns for the details of the collections implementations. In other words, from a user’s perspective, a collection is an abstraction, and for this reason, in computer science, some collections are referred to as abstract data types (ADTs). The user is only concern with learning its interface, or the set of operations its performs...more

Abstract data type is the collection of values and any kind of operation on these values. For example, since String is not a primitive data type, we can include it in abstract data types.

in a simple word: An abstract data type is a collection of data and operations that work on that data. The operations both describe the data to the rest of the program and allow the rest of the program to change the data. The word “data” in “abstract data type” is used loosely. An ADT might be a graphics window with all the operations that affect it, a file and file operations, an insurance-rates table and the operations on it, or something else.

from code complete 2 book

ADT is a data type in which collection of data and operation works on that data . It focuses on more the concept than implementation.. It's up to you which language you use to make it visible on the earth Example: Stack is an ADT while the Array is not Stack is ADT because we can implement it by many languages, Python c c++ java and many more , while Array is built in data type

An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and the operations that are allowed without regard to how they will be implemented. This means that we are concerned only with what the data is representing and not with how it will eventually be constructed.

https://runestone.academy/runestone/books/published/pythonds/Introduction/WhyStudyDataStructuresandAbstractDataTypes.html

Abstractions give you only information(service information) but not implementation. For eg: When you go to withdraw money from an ATM machine, you just know one thing i.e put your ATM card to the machine, click the withdraw option, enter the amount and your money is out if there is money. This is only what you know about ATM machines. But do you know how you are receiving money?? What business logic is going on behind? Which database is being called? Which server at which location is being invoked?? No, you only know is service information i.e you can withdraw money. This is an abstraction.

Similarly, ADT gives you an overview of data types: what they are / can be stored and what operations you can perform on those data types. But it doesn’t provide how to implement that. This is ADT. It only defines the logical form of your data types.

Another analogy is : In a car or bike, you only know when you press the brake your vehicle will stop. But do you know how the bike stops when you press the brake??? No, means implementation detail is being hidden. You only know what brake does when you press but don’t know how it does.

An abstract data type( ADT) is an abstraction of a data structure that provides only the interface to which the data structure must adhere. The interface does not give any specific details about how something should be implemented or in what programming language. enter image description here

The term data type is as the type of data which a particular variable can hold - it may be an integer, a character, a float, or any range of simple data storage representation. However, when we build an object oriented system, we use other data types, known as abstract data type, which represents more realistic entities.

E.g.: We might be interested in representing a 'bank account' data type, which describe how all bank account are handled in a program. Abstraction is about reducing complexity, ignoring unnecessary details.