Abstract Data Type in Data Structure

In this article, we have explained the concept of Abstract Data Type in Data Structure in depth along with code examples and theoretical examples of Data Structures. The best examples of Abstract Data Type come from C++ STL (Standard Template Library) and Java Collections.

Table of contents:

1. Introduction to Abstract Data Type (ADT)
2. Utility
3. Model of Abstract Data Type
4. Implementation of ADT in Java
5. ADT example with shape, rectangle
6. ADT example with interface
7. Widely Utilised ADTs
   7.1. List ADT
   7.2. Set ADT

Point	Abstract Data Type (ADT)
What is it?	An interface a set of similar data structures should conform to. This include member variables and functions. The exact implementation of the methods may vary.
Why needed?	Code convention, better code design, API compatible code
Why learn?	To be able to design better data structures.
Example	List is an Abstract Data Type (ADT) for data structures like Linked List, Array, Stack, Queue and more.
Subject	Algorithm and Data Structure 101

Introduction to Abstract Data Type (ADT)

An abstract data type is a representation of a data structure that simply offers the interface to which it must conform. The interface provides no explicit information about how something should be implemented or in which programming language it should be done.

To put it another way, abstract data types are entities that are data and operation specifications but lack implementation specifics. We know the data we're holding and the actions that may be performed on it in this scenario, but we don't know the implementation details. The lack of implementation details is due to the fact that each programming language employs a distinct implementation method. For example, a C data structure is implemented using structures, whereas a C++ data structure employs objects and classes.

Utility

Many commonly used ADTs are used to perform the following functions: - store a collection of elements, maybe organise the objects in a specified way and allow potentially limited access to the objects.Containers, collections, and container classes are common ADTs used for this purpose.

List (or sequence or vector), Set, Multi-set (or bag), Stack and Queue - Tree, Map are examples of commonly used ADTs with different iterations.

Model of Abstract Data Type

The definition of ADT simply specifies what operations must be executed but not how these operations will be carried out. It does not specify how data will be stored in memory or which algorithms will be utilised to carry out the operations. It is named "abstract" because it provides a view that is independent of implementation. Abstraction is the technique of delivering only the fundamentals while obscuring the details.
An ADT contains all of its data members in a single unit. Encapsulation is the process of integrating data and its component functions into a single entity.

The ADT model is depicted in the figure above. In the ADT model, there are two sorts of models: public function and private function. The ADT model also includes the data structures that we use in our program. First, encapsulation is performed in this paradigm, which means that all data is wrapped in a single unit.Then Abstraction is performed, which includes displaying the operations that can be performed on the data structure as well as the data structures that we use in a program.

Implementation of ADT in Java

In Java, ADT is implemented as an Interface. The interface keyword is used to declare an interface. It supports complete abstraction, which implies that all methods in an interface are declared with an empty body by default, and all fields are public, static, and final by default. A class that implements an interface must implement all of the interface's functions.

Consider some "real-life" examples of abstraction using an interface. Someone else defines the interface, which is subsequently implemented by someone else, and is finally utilised by another programmer who is not aware of the implementation specifics.

1. ADT example with shape, rectangle

//Interface declaration
interface Shapes{  
void draw();  
}  

//Implementation
class Rectangle implements Shapes{  
public void draw(){System.out.println("drawing rectangle");}  
}  
class Circle implements Shapes{  
public void draw(){System.out.println("drawing circle");}  
}  

//Using interface 
class Test1{  
public static void main(String args[]){  
Shapes s=new Circle();//Object may be provided by method e.g. getShapes()  
s.draw();  
}}  

O/P:

drawing circle

2. ADT example with interface

//Interface declaration
public interface A 
{ 
  void msg(); // No body. 
} 

public class B implements A 
{ 
    public void msg()
    { 
      System.out.println("Hello OpenGenus IQ"); 
    } 
 void show()
 { 
    System.out.println("Welcome"); 
  } 

public static void main(String[] args) 
{ 
   B b = new B(); 
    b.msg(); 
    b.show(); // A reference of interface is pointing to objects of class B. 
    
   A a = new B(); 
   a.msg(); 
// a.show(); //Compile time error
   }
 }

Note: Compile-time error because an interface reference can only call methods declared in it and implemented by the class that implements it. The method show() is not part of the interface. It belongs to class B. The compiler will generate a compile-time error if you call this method.It can only be invoked when a class B object reference is created.

O/P:

    Hello OpenGenus IQ
    Welcome
    Hello OpenGenus IQ

Widely Utilised ADTs

We will now elaborate on the implementation of abstraction in ADTs using the various interfaces of Java's collection framework as an example.

List ADT

The List Abstract Data Type is a data type that has similar components in sequential order. It is a collection of components with a linear relationship to one another. A linear relationship implies that each element of the list has a distinct successor.
List Interface of Java specifies about 25 operations that can be performed on the list. Following are some of the operations performed on the list:

• constructor:creates an empty list
• isEmpty:is the list empty
• size:returns the number of elements
• add(i,e):inserts an element e at position i
• remove(i):removes the element at position i
• remove(object):used to simply remove an object from the List
• get(i):returns the element at position i
• set(i,e):changes the element at position i to value e

Implementation

import java.util.*;
  
class iqOpenGenus {
  
    public static void main(String args[])
    {
        List<String> al = new ArrayList<>();
  
        // Adding elements to object of List interface
        al.add("Open");
        al.add("IQ");
        al.add(1, "Genus");
        // Print all the elements
        System.out.println(al);
        
        System.out.println();
        
        
        // Changing an element at a position
        al.add(1, "IQ");
        System.out.println("Original ArrayList " + al);
        // Using set() to update element at 1st index
        al.set(1, "Genus");
        // Print and display the updated List
        System.out.println("Updated ArrayList " + al);
        
        System.out.println();
        
        
        //Removing an Element from the List
        System.out.println("Original ArrayList " + al);
        al.remove(1);
        System.out.println("After Index Removal " + al);
        al.remove("IQ");
        System.out.println("After Object Removal " + al);
        
        System.out.println();
        
        
        //Iterating the Elements in an ArrayList
        al.add("IQ");
        al.add(1, "Genus");
        for (int i = 0; i < al.size(); i++) {
            System.out.print(al.get(i) + " ");
        }
        System.out.println();
        for (String str : al)
        System.out.print(str + " ");
    }
}

O/P:

[Open, Genus, IQ]

Original ArrayList [Open, IQ, IQ]
Updated ArrayList [Open, Genus, IQ]

Original ArrayList [Open, Genus, IQ]
After the Index Removal [Open, IQ]
After the Object Removal [Open]

Open Genus IQ

Open Genus IQ

Further, Java provides various implementations of the List interface:

• ArrayList: Dynamic arrays are provided through an ArrayList class defined in the collection framework.
• Vector: Vector is a collection framework implementation that implements a growable array of things.
• Stack: Stack is a collection framework class that extends the vector class models and implements the Stack data structure.
• LinkedList: LinkedList is a class in the collection framework that implements the linked list data structure .

import java.io.*;
import java.util.*;
  
class listExample {
    public static void main(String[] args)
    {
        // Size
        int n = 5;
        
        
        System.out.println("ArrayList:")
        // ArrayList with size n
        List<Integer> arrli = new ArrayList<Integer>(n);
        // Appending new elements
        // at the end
        for (int i = 1; i <= n; i++)
            arrli.add(i);
        // Printing
        System.out.println(arrli);
        // Remove element at index 3
        arrli.remove(3);
        // Display
        System.out.println(arrli);
        // Printing elements
        for (int i = 0; i < arrli.size(); i++)
            System.out.print(arrli.get(i) + " ");
            
            
       
        System.out.println("Vector:")
        // Vector with initial size n
        List<Integer> v = new Vector<Integer>(n);
        // Appending new elements
        // at the end
        for (int i = 1; i <= n; i++)
            v.add(i);
        // Printing
        System.out.println(v);
        // Remove element at index 3
        v.remove(3);
        // Display
        System.out.println(v);
        // Printing elements
        for (int i = 0; i < v.size(); i++)
            System.out.print(v.get(i) + " ");
            
            
        
        System.out.println("Stack:")
        // Declaring a stack
        List<Integer> s = new Stack<Integer>();
        // Appending new elements
        // at the end
        for (int i = 1; i <= n; i++)
            s.add(i);
        // Printing
        System.out.println(s);
        // Remove element at index 3
        s.remove(3);
        // Display
        System.out.println(s);
        // Printing elements
        for (int i = 0; i < s.size(); i++)
        System.out.print(s.get(i) + " ");    
        
        
        
        System.out.println("LinkedList:")
        //LinkedList with initial size n
        List<Integer> ll = new LinkedList<Integer>();
        // Appending new elements
        // at the end
        for (int i = 1; i <= n; i++)
            ll.add(i);
        // Printing
        System.out.println(ll);
        // Remove element at index 3
        ll.remove(3);
        // Display
        System.out.println(ll);
        // Print elements one by one
        for (int i = 0; i < ll.size(); i++)
        System.out.print(ll.get(i) + " ");
    }
}

O/P:

    ArrayList:
    [1, 2, 3, 4, 5]
    [1, 2, 3, 5]
    1 2 3 5

    Vector:
    [1, 2, 3, 4, 5]
    [1, 2, 3, 5]
    1 2 3 5
    
    Stack:
    [1, 2, 3, 4, 5]
    [1, 2, 3, 5]
    1 2 3 5 
    
    LinkedList:
    [1, 2, 3, 4, 5]
    [1, 2, 3, 5]
    1 2 3 5

Set ADT

A Set is a Collection with no duplicate elements. It is a representation of the mathematical set abstraction. The Set interface comprises only methods inherited from Collection and then limits the addition of duplicate elements.
Various methods(operations) declared by set can be summarized as follows:

• add( ): Adds an object to the collection
• clear( ): Removes all objects from the collection
• contains( ): Returns true if a specified object is an element within the collection
• isEmpty( ): Returns true if the collection has no elements
• iterator( ): Returns an Iterator object for the collection, which may be used to retrieve an object
• remove( ): Removes a specified object from the collection
• size( ): Returns the number of elements in the collection

Implementation

import java.util.*;
public class SetDem {

  public static void main(String args[]) { 
      int count[] = {3,2,1,6,20};
      Set<Integer> set = new HashSet<Integer>();
      try {
         for(int i = 0; i < 5; i++) {
            set.add(count[i]);
         }
         System.out.println(set);

         TreeSet sortedSet = new TreeSet<Integer>(set);
         System.out.println("The list in sorted order is:");
         System.out.println(sortedSet);

         System.out.println("The First element of the set is: "+ (Integer)sortedSet.first());
         System.out.println("The last element of the set is: "+ (Integer)sortedSet.last());
      }
      catch(Exception e) {}
   }
} 

O/P:

[3,2,1,6,20] 
The sorted list is: [1, 2, 3, 6, 20] 
The First element of the set is: 1 
The last element of the set is: 20

Further, Java provides three general-purpose implementations of Sets:

• HashSet: the set is supported by a hash map.
• TreeSet: the set is supported by a tree.
• LinkedHashSet: employs a linked list as a collision management mechanism in the hash map that serves as the set's basis.

    import java.io.*;
import java.util.*;
public class SetExample{
    public static void main(String[] args) 
      { 
        //set implementation using HashSet
        Set<Integer> s = new HashSet<Integer>();
        s.add(3);
        s.add(2);
        s.add(1);
        System.out.println("Set Implementation Using HashSet :");
        System.out.println(s);
        
        // set implementation using LinkedHashSet
        LinkedHashSet<Integer> ls = new LinkedHashSet<Integer>();
        ls.add(3);
        ls.add(2);
        ls.add(1);
        System.out.println("Set Implementation Using LinkedHashSet :");
        System.out.println(ls);
        
       // set implementation using treeset 
        Set<Integer> ts = new TreeSet<Integer>();
        ts.add(3);
        ts.add(20);
        ts.add(12);
        System.out.println("Set Implementation Using TreeSet :");
        System.out.println(ts); 
      }
    }

O/P:

Set Implementation Using HashSet :
[3, 2, 1]
Set Implementation Using LinkedHashSet :
[3, 2, 1]
Set Implementation Using TreeSet :
[3, 12, 20]

Read more about working with Set in Java

With this article at OpenGenus, you must have the complete idea of Abstract Data Type in Data Structures.