Abstract Data Types (ADT)

WHAT IS ADT?

Abstract Data Type (ADT) is a mathematical model for data types where a data type is defined by its behavior from the user point of view of the data. In order to organize data, we use Abstract Data Types (ADT). 

An Abstract Data Type may also defined as a class of objects whose logical behavior is defined by a set of values and a set of operations. 

ADTs were first proposed by Barbara Liskov and Stephen N Zilles in 1974.

ANALOGY WITH ALGEBRAIC STRUCTURES

Abstract Data Type is analogous with Algebraic Structures in Mathematics. An Algebraic Structure on a set A is a collection of operations on A. The set A within this structure is called an Algebra.

E.g., 'A+B' is defined as A+(B*C)

When we compare, the data structure can be referred to the set A. The finitary operations done on set A can be referred to the operations done on Abstract Data Types. Examples of Algebraic structures are Groups, rings, fields, lattices, vector spaces, modules and algebras.

FEATURES OF ABSTRACT DATA TYPES

  1. ADT refers to axiomatic semantics and operational semantics of an abstract model. The computational complexity is measured in terms of time and space. Many common datatypes are not ADTs, as the abstraction is not perfect.
  2. ADTs are theoretical concepts in computer science. They are used for analyzing and designing Algorithms, Data Structures and Software Systems. They are not specific to computer languages. For example, ADTs can be implemented irrespective of any OOP (Object Oriented Programming) language, 
EXAMPLES OF ADT

 1. Integers

  • Integers are the best example for Abstract Data Types (ADT).
  • Integers are defined by the set of values and operations.
  • ADT = { Values set, Operations Set}
  • Consider the Integers, ...., -2, -1, 0, 1, 2, ...... The values are well defined for Integers. The set of operations on Integers are Addition, Subtraction, Multiplication, Division, Greater than, lesser than etc.,
  • In the same way, in computer science we use Binary digits 0 and 1 as Integers. In addition to arithmetic operations, we do n's complement and (n-1)'s complement of those numbers.
  • The user is abstracted from the concrete choice of representation and can simply use the data as data types.
2. Stack

  • An Abstract Stack is a Last-in-First-out (LIFO) structure. It is defined by three operations:
    • Push: Inserts a data item onto the stack
    • Pop: Removes a data item from it
    • Peek or Top: Accesses a data item on top of the stack without removal

3. Queues

  • An abstract queue is a First-in-First-out (FIFO) structure. It is defined by three operations:
    • Enqueue: Inserts a data item into the queue
    • Dequeue: Removes the first data item from it.
    • Front: Accesses and serves the first data item in the queue.

DATA ABSTRACTION IN ADT

  • ADTs are purely theoretical concepts used to simplify the description of complex algorithms, to classify and evaluate data structures and to formally describe the type systems of Programming languages.
  • ADTs are implemented as modules. The module's interface declares procedures that correspond to the ADT operations. This information hiding allows the implementation of the module to be changed without disturbing the client programs.
  • The notion of ADT is related to the concept of Data abstraction and design by contract methodologies for Software Development.

WHY ADT IS USED?

  • Complex implementation is encapsulated in a simple manner: Abstraction assures that ADT has certain properties and abilities. Hence a developer need to make use of that ADT object. The developer need not have any technical knowledge of how the implementation works to use the ADT. 
  • Localized change: Code that uses an ADT object will not need to be edited if the ADT implementation is changed. Since any changes to the implementation must still comply with the interface, changes may be made to the implementation without requiring any changes in code where the ADT is used.
  • Flexible: Different implementations of the ADT, having all the same properties and abilities are equivalent. It is possible to use each in the situation where they are preferable, thus making it more flexible.
ADT OPERATIONS

  1. compare( ): tests whether two instances are equivalent
  2. hash( ): performs the hashing function
  3. print( )
  4. create( )
  5. free( )
COMMON ADTS

  1. Array: An array is stored so that the position of each element can be computed from its index position.
  2. Container: Container store objects in an organized way that follows specific access rules. The size of the container depends on the number of objects it contains.
  3. List: A list is a sequence of data structures which are connected through links. Each link is connected with another item. It can have repeated values.
  4. Set: Set can store certain values without any particular order and no repeated values.
  5. Multiset: A set which allows repeated values is called Multiset.
  6. Map: It is also known as associative array or symbol table. It consists of a collection of key-value pairs.
  7. Multimap: It is an associative array in which more than one value may be associated with and returned for a given key.
  8. Graph: It consists of  finite set of vertices and edges.
  9. Stack
  10. Queue
In the next blog, we shall discuss about List ADT.

Comments

Post a Comment

Popular posts from this blog

Generations of Computer

Image
The computer has seen five generations till now. According to Moore's law,   the number of transistors per square inch on integrated circuits had doubled every year since their invention. He also  predicts that this trend will continue into the foreseeable future. Human kind was overwhelmed with the tremendous speed of innovation in terms of technology, hardware, software, memory etc., in each generation.  Let us discuss in detail about the five generations of computers below: UNIVAC 494 First Generation - Vacuum Tubes: Example:  The UNIVAC and ENIAC are the best examples of first generation computers. UNIVAC (Universal Automatic Computer) was the first commercial computer developed in United States by Presper Eckert and John Mauchly. ENIAC (Electronic Numerical Integrator and Calculator) is an earliest electronic general purpose computer which is Turing complete. It can able to solve a large class of numerical problems through reprogramming. E...
Read more

Introduction to Computers

Image
'Foundations of Computing' blog thread gives the fundamental knowledge about Computers and Logical Computation required for Computer Science students.  In this blog, let us discuss about the basics of Computers. COMPUTER A computer is an electronic device that takes input, processes it according to stored instructions and produces results as output. ETYMOLOGY The word 'Computer' was used in 1613 in a book ' The Yong Mans Gleanings ' by Richard Braithwait. He mentioned in his book as follows 'I have read the truest computer of Times and the best Arithmetician that reduces days into a short number'. This term is used to refer a person who carried out calculations or computations. The word continued with the same meaning until 20th century.  BASIC FUNCTIONALITY Any Digital computer carries out the following functions: Take Data or Instructions as Input Stores the data/instructions in its memory and uses them a...
Read more

Evolution of Computing Hardware

Image
Computing hardware is a platform for Information processing. In this blog, let us discuss on how the modern computers have been evolved. It's quite interesting, when we read the history of computing hardware. Software performance and capability increases exponentially. In order to compensate the growth of Software, hardware need to be improved for every 60 days. This statement is suggested by Moore. Let us walk through the detailed evolution of computing hardware from time to time in this blog I. FINGER COUNTING The Greco-Roman author Plutarch, in his lives, mentions finger counting as being used in Persia in the 1st century AD, so the source of the system ma lie in Iran. Thr practice was later used widely in medieval Islamic lands. II. TALLY STICK A tally stick was an ancient memory aid device used to record and document numbers, quantities or even messages.  There are two kinds of Tally Stick. They are Single Tally: The single tally stick was an el...
Read more