A type is a collection of values. For example, the boolean type consists of the values true and false. The integer type is also a simple type with no subparts.

A data type is a type together with a collection of operations to manipulate the type. For example, an integer variable is a member of the integer data type. Addition is an example of an operation on the integer data type.

An Abstract Data Type (ADT) is the specification of a data type within some programming language, independent of an implementation. The interface for the ADT is defined in terms of a type and a set of operations on that type. The behaviour of each operation is determined by its inputs and outputs. An ADT does not specify how the data type is implemented. These implementation details are hidden from the user of the ADT and protected from outside access, a concept referred to as Encapsulation.

A data structure is the implementation for an ADT. In an object-oriented language like Java, an ADT and its implementation together make up a class. Each operation associated with the ADT is implemented by a member, function or method. The variables that define the space required by a data item are referred to as data members. An object is an instance of a class, that is, something that is created and takes up storage during the execution of a computer program.

ADT Java - Abstract Data Type and Data Structure Explained — Fig. 2. Abstract Data Type and Data Structure Explained

2. Operations of ADT

The operations of an abstract data type are classified as follows:

Creators create new objects of the type. A creator may take an object as an argument, but not an object of the type being constructed.
Producers create new objects from old objects of the type. The concat method of String, for example, is a producer. It takes two strings and produces a new one representing their concatenation.
Observers take objects of the abstract type and return objects of a different type. The size method of List, for example, returns an int.
Mutators change objects. The add method of List, for example, mutates a list by adding an element to the end.

3. ADTs in Java

Java library has Abstract Data Types such as List, Stack, Queue, Set, Map as inbuilt interfaces which are being implemented using various data structures.

In Java, Abstract Data Types extend the Collections Interface which represents the data type. It is part of the Java Collections framework and is the root interface in the collection hierarchy. A collection represents a group of objects, known as its elements.

The JDK does not provide any direct implementations of this interface. It provides implementations of more specific sub interfaces like List, Set. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

ADT Java - Java Collections — Fig. 3. Java Collections

3.1 List ADT

List Abstract Data Type is a collection of elements that have a linear relationship with each other. A linear relationship means that, except for the first one, each element on the list has a unique successor. Also lists have a property intuitively called size, which is simply the number of elements on the list.

List is mutable. List is also an interface, which means that other classes provide the actual implementation of the data type. These classes include ArrayList which is implemented internally using Arrays and LinkedList which is implemented internally using LinkedList data structure.

The operations on List ADT can be classified like below with examples

Creators: java.util.ArrayList and java.util.LinkedList constructors, Collections.singletonList(T t).
Producers: Collections.unmodifiableList(List list).
Observers: size() method of java.util.ArrayList, get(int index) method of java.util.ArrayList.
Mutators: add(Object e), remove(int index), addAll(Collection c) methods of java.util.ArrayList.

Java library’s List interface specifies 25 different operations/methods and some of the methods are as follows

get(int index) – Returns an element at a particular index from the list.
add(E e) – Appends the specified element to the end of this list.
remove(Object o) – Remove the first occurrence of the specified element from the list.
remove(int index) – Removes the element at the specified index from the list.
size() – Returns number of elements of the list.
isEmpty() – Return true if the list is empty, else return false.

3.2 Stack ADT

Stack ADT is a collection with homogeneous data items (elements), in which all insertions and deletions occur at one end, called the top of the stack. A stack is a LIFO “Last In, First Out” structure. Analogy to Stack is a stack of plates.

Stacks are managed mainly using two functions like below

PUSH – places an element on top of the stack.
POP – removes an element from the stack.

In Java, Stack ADT class extends the Vector class which is a growable array of Objects and it can be accessed using integer index.

The operations on the stack ADT can be described like below

Creators: Constructor of java.util.Stack.
Producers: Vector(Collection c) method of Vector.
Observers: peek() method of java.util.Stack, isEmpty() method of java.util.Stack.
Mutators: push(E item) method of java.util.Stack, pop() method of java.util.Stack.

Java library provides the below following operations which can be performed on java.util.Stack

push(E e) – Inserts an element at the top of stack.
pop() – Removes an element from the top of the stack if it is not empty.
peek() – Returns the top element of stack without removing it.
size() – Returns the size of the stack.
isEmpty() – Returns true if the stack is empty, else it returns false.

3.3 Queue ADT

Queue ADT is a collection in which the elements of the same type are arranged sequentially. The operations can be performed at both ends with insertion being done at rear end deletion being done at the front end for a single ended queue. Theoretically, Queue is a FIFO “First In, First Out” structure.

Java data structures like java.util.LinkedList, java.util.concurrent.ArrayBlockingQueue implement Queue ADT using LinkedList and ArrayLists internally respectively.

The operations on the queue ADT can be described like below

Creators: Constructor of java.util.LinkedList.
Producers: Constructor method LinkedList(Collection c) of java.util.LinkedList.
Observers: peek() method of java.util.LinkedList.
Mutators: add(E item) method of java.util.LinkedList.

Java library provides the below following operations which can be performed on java.util.Queue

add(E e) – Queues an element at the end of queue.
remove() – Dequeues an element from the head of the queue.
peek() – Returns the element of the queue without removing it.
offer(E e) – Inserts the specified element into this queue if it is possible to do without violating capacity restrictions.
size() – Returns the size of the queue.

4. Which Java ADT to choose ?

In this section, we will discuss on the scenarios to choose between either of List, Stack and Queue ADT.

As List ADT is a collections of elements stored sequentially and can be accessed using their indices, it needs to be chosen in cases which involves sequential or indexed access or removal of elements. For example, various implementations of List ADT can be used to store data of a list of students in a sorted order for an ordered or indexed access or removal.

Since Stack is a Last In First data structure, the implementations of Stack ADT need to be chosen in scenarios where the most recently inserted elements need to be accessible first. One of the common example where this kind of LIFO data structure is required is the function call stack of every programming language where the most recent function in the stack needs to be executed first.

Queue is a First In First Out structure and data structures implementing Queue ADT need to be chosen in scenarios where the elements need to be accessed in their order of insertion i.e where fairness needs to be ensured. Example of one such scenario is request handling by web servers. Web servers facilitate fairness of request handling according to their order of arrival by maintaining an internal queue for the requests.

5. ADT Java Tutorial – Conclusion

In this article, we have understood what an Abstract Data Type is and its operations with suitable illustrations. We have also understood Abstract Data Types in Java and in the sections followed we have also understood in detail about List ADT, Stack ADT, Queue ADT with the operations and methods provided by them. Towards the end of the article, we have also discussed about the applicability of each of the discussed ADTs along with scenarios on when to use them.