ABSTRACT DATA TYPES

What is meant by Abstract data type (ADT)?

• Abstract Data Type (ADT) is a set of objects performing set of operations.
• Here the implementations of operations are independent.
• The operations performed on data are similar to mathematical operations.

Concept behind Abstract Data Type:

• The implementation of operations written on one part of the program can be used from the other part of that same program just by calling the specific function.
• If we want to make changes in the operation, it can be done easily by changing specific part of the function without disturbing rest of the program.
• There is no general rule defining which operations must be handled by an ADT. Its completely up to the designers view.
• Hence error handling and tie breaking can be easily handled by the programmer who designed.

Basic ADTs Most Used:

• List ADT
• Stack ADT
• Queue ADT 

List ADT:

• A list is a dynamic tuple of homogeneous elements with size n:
  A₀,A₁,A₂,.....A_N-1.
• The position of element A_k is 'k'.Here the positions ranges from 0 to N-1.
• We can also have empty list with size zero.
• Operations performed: insert list, delete list, find kth element, find position of A_k, Print list, empty list.
• Implementations: 1. Array implementation of list,
                               2. Linked list implementation of list.
• Applications: 1. Polynomial ADT,
                         2. Radix sort

Stack ADT:

•  Stack is a list where insertion and deletion takes place only at one end called Top.
• Basic idea behind stack is LIFO- Last In First Out . Hence stack lists are also called as LIFO lists.
• Operations Performed:
  1. Push - inserting an element
  2. Pop- deleting an element
  3. Top- returning an element to the top of the stack.
  4. Empty- make the stack empty.
• Implementations: 1. Array implementation of stack,
                               2. Linked list implementation of stack.
•  Applications: 1. Balancing Symbols
                          2. Postfix expressions, infix to postfix convertions
                          3. Function calls.

Queue ADT:

• Queue is a list where insertion takes place at one end and deletion takes place at the other end.
• Inserting end is rear and deleting end is front.
• Basic idea behind stack is FIFO- First In First Out . Hence queue lists are also called as FIFO lists.
• Operations Performed:
  1. Enqueue: Insertion
  2. Dequeue: Deletion
  3. Create Queue
  4, Dispose Queue
• Implementations: Array implementation.
• Applications: Graph theory.

Thus these are about What is Abstract Data Type? and the basic ADTs. We will see in detail about these ADTs in future posts.

Here is a Question for you....
           Is Linked list an ADT or is it a Data Structure??????????
Think over.....  For Answer search in my next post List ADT.