What is ADT Abstract Data Type

Question

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

User · Answer

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

User · Answer

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 amp chapter abstract-data-types

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  lt integer  integer gt  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

User · Answer

To solve problems we combine the data structure with their operations  An ADT consists of two parts    Declaration of Data  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  quot Existing as an idea but not having a physical idea quot   For example  lets see specifications of some Abstract Data Types   List Abstract Data Type  initialize    get    insert    remove    etc  Stack Abstract Data Type  push    pop    peek    isEmpty    isNull    etc  Queue Abstract Data Type  enqueue    dequeue    size    peek    etc

User · Answer

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

[language-agnostic] What is ADT? (Abstract Data Type)

Examples related to language-agnostic

Examples related to terminology

Examples related to abstract-data-type