In our last articles, we discussed the different Data Structures in Java. In this article, we will learn the Abstract Data Type in Java which specify the Data structures. We will cover various Abstract Data Types such as List ADT, Stack ADT, and Queue ADT in detail.
So let’s begin with an introduction to Abstract Data Type (ADT).
Before that, it is recommended for you to take a quick revision of Data Types in Java to clear your basics with Techvidvan.
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.
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.
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.
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.
WAIT! It’s the right time to get familiar with the concept of Data Structure in Java with Techvidvan.
Types and Operations of Java Abstract Data Type
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)
Check out the different types of Operators in Java with Techvidvan.
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)
Get familiar with the Methods of Java Strings in detail with Techvidvan.
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.
Summary
That was all about Java Abstract Data Types. In this Java tutorial, we learned the basic concept of Java Abstract Data Type (ADT) and the types of Abstract Data Types in Java: List ADT, Stack ADT, and Queue ADT.
We discussed these Abstract Data Types in detail, along with their methods. In the end, we also discussed which Abstract Data Type we should choose while working with real-time applications.
Enhance your knowledge and get to know – What really differentiates an Abstract Class and Interface in Java?
Thank you for reading our article. Do share our article on Social Media.
Happy Learning 🙂