Breaking News

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

Data Structures - Abstract Data Types (ADT)

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

(a) What is Abstract Data Type (ADT)? 
(b) Give examples of commonly used ADTs.
(c) What are the advantages of ADTs?

(a) An abstract data type (ADT) is a logical description or a specification of components of the data and the operations that are allowed and it is independent of the implementation. An ADT is a user defined data type that are defined along with their operations.

An ADT consists of two parts:
1. Declaration of data
2. Declaration of operations

(b) Commonly used ADTs are:
Linked Lists,
Priority Queues,
Binary Trees,
Disjoint Sets,
Hash Tables,
Graphs etc.

(c) Advantages of ADTs are:

Encapsulation: The user need not know knowledge of implementing the ADT. Its implementation may be complex but it is be encapsulated in a simple interface while defining it.

Localization of change: Code that uses an ADT object do not require editing if the implementation of the ADT  changes.

Flexibility: Different implementations of an ADT may be more efficient in different situations thus increases the overall efficiency of the program.

Easy to understand and reusable code.

Question: Write down one dimensional array specifications as ADT.

Answer: eltype denotes type of element and ub is the upper bound.

abstract typedef <<eltype, ub>> ARRTYPE(ub, eltype);
condition type(ub) == int;

abstract eltype extract(a, i)  /* written as a[i] */
ARRTYPE(ub, eltype) a;
int i;
precondition 0 <= i < ub;
postcondition extract == a₁

abstract store(a, i, elt)
ARRTYPE (ub, eltype) a;
int i;
eltype elt;
precondition  0 <= i < ub;
postcondition a[i] == elt;

Question: Write down representation of a stack as ADT.


abstract typedef <<eltype>> STACK (eltype);

abstract empty(s)
STACK (eltype s)
postcondition (empty == len(s) == 0);

abstract eltype pop(s)
STACK (eltype) s;
precondition empty(s) == FALSE;
postcondition pop == first(s)
s == sub(s', 1, len(s') - 1);

abstract push (s, elt)
STACK (eltype) s;
eltype elt;
postcondition s == <elt> + s';

Question: Represent queue as Abstract Data Type (ADT).


abstract typedef <<eltype>> QUEUE (eltype);

abstract empty(q)
QUEUE (eltype) q;
postcondition empty == (len(q) == 0);

abstract eltype remove(q)
QUEUE (eltype) q;
precondition empty(q) == FALSE;
postcondition remove == first(q');
q == sub(q', 1, len(q') - 1);

abstract insert (q, elt)
QUEUE (eltype) q;
eltype elt;
postcondition q = q' + <elt>;

See also:
  - Abstract Data Type Notes by CSE Department IIT Kharagpur
  - Data Structure Notes by IIT Kgp