What is an Abstract Data Type in Java?
We know that a data type signifies the type and space taken by the data used in
programs. An Abstract Data Type is a special data type that is defined by a set
of values and a set of operations on that type.
The implementation details of these data types are totally invisible to the
users. It does not specify how the data stores in the memory area and what
algorithms are useful for implementing the operations on the data.
We call these data types as “abstract” because these are independent of any
implementation. We can use these data types and perform different operations with
them, but we do not know how these operations are working internally.
An Abstract Data Type in Java is useful in the implementation of data structures.
Java library provides various Abstract Data Types such as List, Stack, Queue, Set,
Map as inbuilt interfaces that we implement using various data structures.
Types and Operations of Java Abstract Data Types
We can classify the Abstract data types either as built-in or user-defined or
as mutable or immutable.
If an Abstract Data Type is mutable then we can change the objects of its type and if
it is immutable then we can’t change its object.
For example, the Date class is mutable because we can call its setMonth() method
and observe the change with the getMonth() operation. But String is immutable
because its operations do not change the existing objects but create new String
objects.
Operations
There are following types of operations of an abstract type:
Creators: Creators create new objects of the type. It may take an object as an
argument.
Producers: Producers create new objects from old objects of the type. For
example, the concat() method of the String is a producer that takes two strings
and produces a new String representing their concatenation.
Observers: Observers take the objects of the abstract type and return objects of
a different type. For example, the size() method of the List returns an int.
Mutators: Mutators change objects. For example, the add() method of List
changes a list by adding an element to the end.
Java Abstract Data Type Examples
Below are some examples of abstract data types, along with some of their
operations and the types.
1. int is a primitive integer type of Java. int is immutable, so it has no mutators. Its
operations are:
creators: The numeric literals 0, 1, 2, 3,…
producers: Arithmetic operators +, -, ×, ÷
observers: Comparison operators ==, !=, <, >
mutators: None (it’s immutable)
2. The list is an interface of Java List. The list is mutable. Its operations are:
creators: ArrayList and LinkedList constructors, Collections.singletonList
producers: Collections.unmodifiableList
observers: size, get
mutators: add, remove, addAll, Collections.sort
3. A string is Java’s string type. The string is immutable. Its operations are:
creators: String constructors
producers: concat, substring, toUpperCase
observers: length, charAt
mutators: none (it’s immutable)
List of Java Abstract Data Type
Now, Let’s start exploring different Java Abstract Data Types in Java:
1. List ADT
The List Abstract Data Type is a type of list that contains similar elements in
sequential order. The list ADT is a collection of elements that have a linear
relationship with each other. A linear relationship means that each element of the list
has a unique successor.
The List ADT is an interface, that is, other classes give the actual implementation of
the data type. For example, Array Data Structure internally implements
the ArrayList class while the List Data Structure internally implements
the LinkedList class.
The List interface of Java library specifies 25 different operations/methods.
Following are some of the operations that we can perform on the list:
get(int index): Returns an element at the specified index from the list.
insert(): Inserts an element at any position.
remove(): Removes the first occurrence of any element from a list.
removeAt(): Removes the element at a predefined area from a non-empty list.
Replace(): Replaces an element by another element.
size(): Returns the number of elements of the list.
isEmpty(): Returns true if the list is empty, else returns false.
isFull(): Returns true if the list is full, else returns false.
2. Stack ADT
A stack is a LIFO (“Last In, First Out”) data structure that contains similar elements
arranged in an ordered sequence. All the operations in stack take place at the top of
the stack.
Stack ADT is a collection of homogeneous data items (elements), in which all
insertions and deletions occur at one end, called the top of the stack.
In Stack ADT Implementation, there is a pointer to the data, instead of storing the
data at each node.
The program allocates the memory for the data and passes the address to the
stack ADT.
The start node and the data nodes encapsulate together in the ADT. Only the
pointer to the stack is visible to the calling function.
The stack head structure also contains a pointer to the top of the stack and also
the count of the number of entries currently in the stack.
The below diagram shows the whole structure of the Stack ADT:
We can perform the following operations on the stack –
push(): It inserts an element at the top of the stack if the stack is not full.
pop(): It removes or pops an element from the top of the stack if the stack is not
empty.
peep(): Returns the top element of the stack without removing it.
size(): Returns the size of the stack.
isEmpty(): If the stack is empty it returns true, else it returns false.
isFull(): If the stack is full it returns true, else it returns false.
3. Queue ADT
A Queue is a FIFO (“First In, First Out”) data structure that contains similar types of
elements arranged sequentially. We can perform the operations on a queue at both
ends; insertion takes place at rear end deletion takes place at the front end.
Queue ADT is a collection in which the arrangement of the elements of the same
type is in a sequential manner.
The design of the Queue abstract data type (ADT) is the same as the basic
design of the Stack ADT.
Each node of the queue contains a void pointer to the data and a link pointer to
the next element of the queue. The program allocates the memory for storing the
data.
Operations performed on the queue are as follows:
enqueue(): It inserts or adds an element at the end of the queue.
dequeue(): Removes an element from the front side of the queue.
peek(): Returns the starting element of the queue without removing it.
size(): This function returns the number of elements in the queue.
isEmpty(): If the queue is empty, it returns true, otherwise it returns false.
isFull(): If the queue is full, it returns true, otherwise it returns false.
Designing an Abstract Data Type in Java
To design an abstract data type we have to choose good operations and determine
how they should behave. Here are a few rules for designing an ADT.
It’s better to combine simple and few operations in powerful ways, rather than a
lot of complex operations.
Each operation in an Abstract Data Type should have a clear purpose and should
have a logical behavior rather than a range of special cases. All the special cases
would make operation difficult to understand and use.
The set of operations should be adequate so that there are enough kinds of
computations that users likely want to do.
The type may be either generic, for example, a graph, a list or a set, or it may be
domain-specific for example, an employee database, a street map, a phone
book, etc. But there should not be a combination of generic and domain-specific
features.
Which Java Abstract Data Type to choose?
Now after having brief knowledge of Java Abstract Data Types, we will discuss the
scenarios to choose between either of List, Stack or Queue ADT.
List ADT is a collection of elements and stores them sequentially and which we can
access using their indices. We can opt for this ADT in cases that involve indexed or
sequential access or removal of elements.
For example, we can use various implementations of List ADT to store data of a list
of employees in sorted order for sequential access or removal.
A Stack is a Last In First out data structure, and thus we can use implementations
of Stack ADT in scenarios where we need to firstly access the most recently
inserted elements.
For example, the function call stack of every programming language has the
common requirement of this kind of LIFO data structure where there is a need to
execute the most recent function in the stack.
The queue is a First In First Out data structure and we can choose the Queue
ADT in scenarios where we need to access the elements in their order of insertion.
For example, one such scenario is request handling by web servers. Web servers
make it possible to ensure the fairness of request handling according to their order of
arrival by maintaining an internal queue for the requests.
Invariant?
A property that does not change after certain transformations. Example: the
side lengths of a triangle don't change when the triangle is rotated.
Finding invariants helps us understand the things we are dealing with.
An invariant is any logical rule that must be obeyed throughout the execution
of your program that can be communicated to a human, but not to your
compiler.
Concrete Sate Space:
The concrete state space is the set of all possible concrete values a
specific data representation can have.
For any array a, concrete state space may be {12}; {12, 35}; {12, 45, 65} etc.
Concrete Invariant:
A condition that must be true over all valid concrete representations.
For any array a, concrete invariant may be “index < a.length ∧ 0 <=index”.
Abstraction function
It maps valid concrete values into abstract values.
Maps set of possible concrete values {120K}; {35K}; {65K} into abstract value
get Salary.
Note: Operations in OOP are the member functions in a class.
Encapsulation
In object-oriented computer programming (OOP) languages, the notion of encapsulation (or
OOP Encapsulation) refers to the bundling of data, along with the methods that operate on
that data, into a single unit.
Abstraction Encapsulation
Abstraction in Object Oriented Programming
Encapsulation solves it implementation level.
solves the issues at the design level.
Abstraction in Programming is about hiding
Encapsulation means binding the code and data into a
unwanted details while showing most essential
single unit.
information.
Encapsulation means hiding the internal details or
Data Abstraction in Java allows focussing on
mechanics of how an object does something for
what the information object must contain
security reasons.
Polymorphism
INHERITANCE POLYMORPHISM
Inheritance is one in which a new
class is created (derived class) that Whereas polymorphism is that which can
1.
inherits the features from the already be defined in multiple forms.
existing class(Base class).
Whereas it is basically applied to functions
2. It is basically applied to classes.
or methods.
Inheritance supports the concept of Polymorphism allows the object to decide
3. reusability and reduces code length in which form of the function to implement at
object-oriented programming. compile-time (overloading) as well as run-
INHERITANCE POLYMORPHISM
time (overriding).
Inheritance can be single, hybrid, Whereas it can be compiled-time
4. multiple, hierarchical and multilevel polymorphism (overload) as well as run-
inheritance. time polymorphism (overriding).
5. It is used in pattern designing. While it is also used in pattern designing.
Iterator Pattern
Iterator Pattern is a relatively simple and frequently used design pattern. There are a lot of
data structures/collections available in every language. Each collection must provide an
iterator that lets it iterate through its objects. However while doing so it should make sure
that it does not expose its implementation. Suppose we are building an application that
requires us to maintain a list of notifications. Eventually, some part of your code will require
to iterate over all notifications. If we implemented your collection of notifications as array you
would iterate over them as:
// If a simple array is used to store notifications
for (int i = 0; i < notificationList.length; i++)
Notification notification = notificationList[i]);
// If ArrayList is Java is used, then we would iterate
// over them as:
for (int i = 0; i < notificationList.size(); i++)
Notification notification = (Notification)notificationList.get(i);
And if it were some other collection like set, tree etc. way of iterating would change slightly.
Now, what if we build an iterator that provides a generic way of iterating over a collection
independent of its type.
// Create an iterator
Iterator iterator = notificationList.createIterator();
// It wouldn’t matter if list is Array or ArrayList or
// anything else.
while (iterator.hasNext())
{
Notification notification = iterator.next());
}
Iterator pattern lets us do just that. Formally it is defined as below: The iterator pattern
provides a way to access the elements of an aggregate object without exposing its
underlying representation.
MVC Design Pattern
The Model View Controller (MVC) design pattern specifies that an application consist of a
data model, presentation information, and control information. The pattern requires that each
of these be separated into different objects.
MVC is more of an architectural pattern, but not for complete application. MVC mostly
relates to the UI / interaction layer of an application. You’re still going to need business logic
layer, maybe some service layer and data access layer.
UML Diagram MVC Design Pattern
Design components
The Model contains only the pure application data, it contains no logic describing how to
present the data to a user.
The View presents the model’s data to the user. The view knows how to access the
model’s data, but it does not know what this data means or what the user can do to
manipulate it.
The Controller exists between the view and the model. It listens to events triggered by
the view (or another external source) and executes the appropriate reaction to these
events. In most cases, the reaction is to call a method on the model. Since the view and
the model are connected through a notification mechanism, the result of this action is
then automatically reflected in the view.
Let’s see an example of MVC Design Pattern.
class Student
{
private String rollNo;
private String name;
public String getRollNo()
{
return rollNo;
}
public void setRollNo(String rollNo)
{
this.rollNo = rollNo;
}
public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
}
class StudentView
{
public void printStudentDetails(String studentName, String
studentRollNo)
{
System.out.println("Student: ");
System.out.println("Name: " + studentName);
System.out.println("Roll No: " + studentRollNo);
}
}
class StudentController
{
private Student model;
private StudentView view;
public StudentController(Student model, StudentView view)
{
this.model = model;
this.view = view;
}
public void setStudentName(String name)
{
model.setName(name);
}
public String getStudentName()
{
return model.getName();
}
public void setStudentRollNo(String rollNo)
{
model.setRollNo(rollNo);
}
public String getStudentRollNo()
{
return model.getRollNo();
}
public void updateView()
{
view.printStudentDetails(model.getName(), model.getRollNo());
}
}
class MVCPattern
{
public static void main(String[] args)
{
Student model = retriveStudentFromDatabase();
StudentView view = new StudentView();
StudentController controller = new StudentController(model, view);
controller.updateView();
controller.setStudentName("Vikram Sharma");
controller.updateView();
}
private static Student retriveStudentFromDatabase()
{
Student student = new Student();
student.setName("Lokesh Sharma");
student.setRollNo("15UCS157");
return student;
}
}
Output:
Student:
Name: Lokesh Sharma
Roll No: 15UCS157
Student:
Name: Vikram Sharma
Roll No: 15UCS157
Advantages
Multiple developers can work simultaneously on the model, controller and views.
MVC enables logical grouping of related actions on a controller together. The views for a
specific model are also grouped together.
Models can have multiple views.
Disadvantages
The framework navigation can be complex because it introduces new layers of
abstraction and requires users to adapt to the decomposition criteria of MVC.
Knowledge on multiple technologies becomes the norm. Developers using MVC need to
be skilled in multiple technologies.
