Developer

Transitioning into OOP: Abstract data types in Java

Ignorance is bliss, at least when it comes to knowing the internals of a particular operation. See how Java abstract data types provide you with a consistent interface while keeping the implementation details hidden.


In our previous article "Transitioning into OOP: Using complex data types in Java," we discussed reference data types, class types, interface types, and composite data types. In this article, we will continue to look at data types in Java but we'll introduce the concept of an abstract data type (ADT). We'll also examine some of the ADTs defined by Java by introducing the Java Collections Framework.

ADTs
An ADT is a data type defined only by the type of data stored and the operations that may be performed on concrete instances of the type. Developers access concrete instances of an ADT using only its operations, and they are unaware of how the operations are implemented within the internal structure of the data type.

In Java, presenting a set of operations without presenting the implementation details of each operation is commonly done using an interface. Remember that an interface defines a set of methods that a Java class must implement in order to fulfill its obligation or contract as a concrete instance of the interface.

Catch up on past articles covering the transition to OOP with Java


List, stack, and queue
The terms list, stack, and queue usually enter into conversations about ADTs. We are not going to go into much detail on these but we will talk about why they are spoken of as ADTs.

A list is a collection of finite elements arranged in a linear fashion that provides direct access to any of its elements. A stack is a last-in-first-out (LIFO) sequential list in which elements are added at the front of the list and removed from the front. A queue is a first-in-first-out (FIFO) sequential list in which elements are added at the rear of the list and elements are removed from the front.

The internal structure of a list, stack, or queue can be implemented in many ways. For example, we could use an ordered array or a linked list to implement each structure. The point is that no matter how you implement the internal structure of each type, the public interface remains unchanged. Thus, a list, stack, or queue presents an abstract model of the operations it performs but hides the details of how it implements them. This allows the underlying implementation to be changed or upgraded without changing the public interface.

Java Collections Framework
The Java 2 software development kit (SDK) provides a framework of new classes that support most of the common ADTs. These are known as the Java Collection classes, and they work together to form the Java Collections Framework. The Collections Framework provides a set of interfaces and classes for representing groups of data as an abstraction called a Collection.

The java.util.Collection interface is used to represent arbitrary groups of objects, known as elements. The interface exposes basic operations like adding, removing, and querying. The Collection interface also exposes an iterator method. The iterator method returns an instance of the java.util.Iterator interface. The Iterator interface exposes the methods hasNext, next, and remove. Using the Iteratorinterface methods, you can iterate over a Collection from beginning to end and safely remove elements that the iterator represents.

The java.util.AbstractCollection class is the foundation for all of the Collection Framework classes. The AbstractCollection class provides implementations for all the java.util.Collection interface's methods except for the iterator and size methods. These are implemented in each of the classes that extend java.util.AbstractCollection.

A class that implements an interface must provide implementations for all the interface methods. Since some of the interface methods in the Collections Framework are optional, there needs to be a way to notify callers when an optional method is not supported. When an optional method is called that has not been implemented by the target class, an UnsupportedOperationException is thrown. The UnsupportedOperationException class extends the RuntimeException class. This allows callers to call all Collection operations without placing each call within a try-catch block.

Lists
The List interface extends the Collection interface to define an ordered collection that permits duplicate elements. The List interface adds operations that take a numeric index to operate on elements of a Collection based on their position in the list. These operations include add, get, set, and remove.

The List interface also exposes the listIterator method. This method returns an instance of the java.util.ListIterator interface, which allows iterating through a list from front to back or from back to front. The java.util.ListIterator interface extends the java.util.Iterator interface. Thus, it supports adding or changing elements in the Collection it represents.

The following example demonstrates iterating backward through a list. To accomplish this, the ListIterator must be located one position beyond the end of the list at the start of the iteration. Since iterators are zero-based, this is done by passing the size of the list to the listIterator method.
ListIterator iter = aList.listIterator(aList.size());
while (iter.hasPrevious())
{
   System.out.println(iter.previous().toString());
}

The Collections Framework provides two concrete implementations of the List interface: LinkedList and ArrayList. Both implementations support random access. An ArrayList supports array-style operations with resizing supported. A LinkedList exposes methods that explicitly support adding, removing, and retrieving elements from the beginning and end of the list. Using these new methods, a developer can easily treat a LinkedList as a stack or a queue, as follows:
LinkedList   aQueue = new LinkedList(aCollection);
aQueue.addFirst(newElement);
Object   anElement = aQueue.removeLast();
 
LinkedList  aStack = new LinkedList(aCollection);
aStack.addFirst(newElement);
Object   anElement= aStack.removeFirst();

The snippet in Listing A demonstrates some common operations on implementations of the java.util.List interface using java.util.ArrayList and java.util.LinkedList. These operations include adding elements, retrieving elements randomly, and explicitly removing elements from the end of the list.

There is value in not knowing what is under the covers
ADTs provide a powerful means of separating the implementation of an object's operations from its public interface. This allows the implementation of an ADT to vary and evolve while keeping the public interface the same. The Java Collections Framework provides an extensive set of interfaces and implementations for representing groups of elements and for building useful ADTs.

In our next article, we will dig deeper into the Collections Framework to present additional classes, and we'll look at the searching and sorting capabilities of the Framework.

Editor's Picks

Free Newsletters, In your Inbox