Abstract Data Type (ADT)

 Abstract Data Types :-  ADT

Introduction to Abstract Data Type :

In our previous topics Queue and Stack while reading we came across a term called ADT. 

In this topic we will learn about Abstract Data types (ADT), but before learning about we will do a quick recap of the data types that are given to us. Data types such as int, float, long, double, etc. Are know as primitive data types , We can perform some basic operations with them such as addition , subtraction, division, multiplication, etc.

                           There are also some derived data type like String and char that we help to store alphanumeric sequence of characters and store characters respectively. 

Now there may a situation when we need a all the capabilities of these data types so in stead of declaring a bunch of data ( which might cause a huge wastage of space), we can create a data type that has all the capabilities of these data types and can be used to simplify the problem of declaring of multiple data types; these data types are called user-defined data types.

There are some different types of user-defined data types in c language:

1. Structure.
2. Union
3. Enum
4. typedef

Similarly there are user-defined data types in java to :

1. Classes
2. Interfaces

So in order to simplify the process of problem solving we create the data structures [like stack, queue, trees, graphs, etc. using array and linked list] using these user-defined data types along with specific operations, such type of data structures that are not built-in are called Abstract data types (ADT)

Definition:-  

In this photo we can see a team, So in real world we can say that a team working for a company is an ADT while the main program is the company that assigns work to them.

Abstract data types (ADT) is a type (or class) for objects which has a set of defined values and specific operations. 

Now a point to notice is that in the definition of abstract data types it doesn't explain how the data would be allocated in the memory or how much memory is actually need. Further more it does not say anything about how the specific operations are going to be implemented which is why the word abstract is used; as it hides all the information or knowledge on its implementation.

Now focusing on the word abstraction,  it means to provide only the essentials and hiding the details from the users.

                                Now we would present a small flowchart on ADT :

So the user just needs to know what a data type can do and not how it works , presenting ADT as a black box which hides the inner info and design of the data type but shows only its result(output). 

Mainly we will name three ADTs namely List ADT, Stack ADT, Queue ADT.

1. List ADT : 

The Linked list is a linear data structure, in which the elements are not stored in a contiguous memory location. The elements in a Linked list are linked using pointer variables. Linked list consists of nodes , each node has two parts (i) A data part (ii) pointer part 

The data part in the node of the linked list stores the value or elements given by the user and pointer part in the node of the Linked list contains the address of the next node. 

The list ADT functions are mentioned below:

• Create() - creates an entire linked list by asking the number of nodes and values to be inserted from the user.
• Insert Beg() - adds a node at the beginning of the list along with value and the address to next node.
• Insert End() - adds a node at the end of the linked list with the value but with a Null address pointer.
• Insert Any() - adds a node at any position in the list.
• Remove Beg() - removes a node at the beginning of the list 
• Remove End() - removes a node at the end of the list.
• Remove Any() - removes a node at any position in the list.
• Count() - return the total number of nodes present in the list.
• Is Empty() - returns true if list is empty, otherwise returns false.

2. Stack ADT :

Stack is a linear data structure which follows lifo method ( Last In First Out). In stack there is only one end for inserting data and deleting data . Inserting Data is called push operation,

Deleting or removing data is called pop operation.  Displaying the stack is called peep operation. 

Stack contains only one pointer variable called top pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the top of the stack.

•  In stack ADT implementation instead of storing the data in the nodes itself we store the address of the stored data using a pointer called top.
• The program allocates memory for  the data and the address is passed to the stack ADT.
• The head node and the data nodes are encapsulated in the ADT. The calling function can only see the pointer to  the stack .
• The functions of Stack ADT are mentioned below:
• Push () - inserts an element at one end of the stack called top.
• Peek () - displays all the elements present in the stack.
• Pop () - removes element at the top of stack.
• IsEmpty() - returns true if the stack is empty otherwise returns false. Used to check Underflow condition in the stack.
• IsFull() - returns true if the stack is full otherwise returns false. Used to check Overflow condition in stack.

3. Queue ADT : 

Queue is a linear data structure which follows FIFO ( First In First Out) methodology (i.e. the element that is stored at the first will leave at first). Unlike stack queue has two ways , one for inserting data and other one for deleting data. 

In queue inserting data is called Enqueue and deleting data is called dequeue.

• The queue abstract data type (ADT) follows the basic design of the stack abstract data type.
• Where each node has a void pointer to the data and the link pointer to the next element in the queue. 
• The program allocates memory for storing the data. 
• Enqueue() - insert an element at the end of the queue using a pointer variable called rear.
• dequeue() - removes and returns the first element of the queue using a pointer variable called front , if the queue is not empty.
• Display() - prints all the elements present in the queue. 
• IsEmpty() - returns true if the queue is empty otherwise returns false. Used to check Underflow condition in the queue.
• IsFull() - returns true if the queue is full otherwise returns false. Used to check Overflow condition in queue.

Features of ADT :

1. Abstraction - the user does not knows the implementation of the data structure.
2. Robust code : ADT makes the entire error free and easy to understand thus making the code robust.
3. Conceptualization: ADT gives us a better concept of the real world applications.