Article source: Internet Author: PaleSting/CSDN
In this article, we will look at data types in Java, but we will introduce the concept of abstract data types (ADT). We will also learn about some of the ADTs defined by Java by introducing the Java Collections Framework.
ADT
An ADT is defined only by the data type it holds and the operations that may be performed on this data type. Developers can only access the properties of ADT through the operation methods of ADT, and they will not know how the various operations inside this data type are implemented.
In Java, we often use an interface to provide a set of operations without revealing the details of the implementation of these operations. Remember that an interface defines a set of methods and a Java class must implement this set in order to satisfy its mandatory conditions or implement an instance of the interface.
Linear tables, stacks and queues
When we talk about ADT, we often talk about linear lists, stacks and queues. We won't discuss the details of these data structures, but we will discuss why they are called ADTs.
A linear list is a collection of finite elements arranged in a linear fashion and providing direct access to its elements. A stack is a last-in-first-out (LIFO) ordered linear list. Elements are added to and removed from the head of the stack. A queue is a first-in-first-out ordered linear list, elements are added from the end of the queue and taken from the head of the queue.
The internal structures of linear lists, stacks and queues can be implemented in many ways. For example, we could use an ordered array or a linked list to implement each structure. The key point is that no matter how you implement its internal structure, its external interface will always remain the same. This allows you to modify or upgrade the underlying implementation without changing the public interface.
Java collection architecture
The Java 2 Software Development Kit (SDK) provides new classes to support most commonly used ADTs. These classes are called Java collection classes (similar to the collection classes in MFC), and they work together to form the Java collection architecture. This collection architecture provides a set of interfaces and classes that represent data as so-called collection abstract data.
The java.util.Collection interface is used to represent any group of objects, that is, elements. This interface provides basic operations such as add, delete, and query. The Collection interface also provides an iterator method. The iterator method returns an instance of the java.util.Iterator interface. The Iterator interface provides hasNext, next, and remove methods. Using the methods provided by the Iterator interface, you can loop through the instances in a Collection object from beginning to end and safely delete the element represented by the iterator (cursor).
java.util.AbstractCollection is the basis for all collection architecture classes. The AbstractCollection class provides implementations of all methods in the java.util.Collection interface except the iterator and size methods. These two exception methods are implemented by all subclasses that inherit java.util.AbstractCollection.
A class that implements an interface must provide implementation of all interface methods. Because some interface methods in the collection architecture are optional, there must be a way to notify the caller that a certain method is not implemented. When an optional method is implemented and this method is not implemented, an UnsupportedOperationException is thrown. The UnsupportedOperationException class inherits the RuntimeException class. This allows the caller to call all collection operations without putting each call in a try-catch pair.
List linear table
The List interface inherits the Collection interface and defines an ordered collection that allows identical elements to exist. The List interface also adds methods that use a numeric index value to operate on the elements in the Collection based on the element's position in the linear list. These operations include add, get, set and remove.
The List interface also provides the listIterator method. This method returns an instance of the java.util.ListIterator interface, which allows you to traverse a linear list from beginning to end or from end to end. java.util.ListIterator inherits the java.util.Iterator interface. Therefore, it supports the addition and modification of elements in the Collection it represents.
The following example demonstrates how to traverse the elements of a list from back to front. To accomplish this, the ListIterator must be positioned after the last element of the list before traversal begins.
ListIterator iter = aList.listIterator(aList.size());
while (iter.hasPrevious())
System.out.println(iter.previous().toString());
}
The collection architecture provides two implementations of the List interface: LinkedList (linked list) and ArrayList (array list, that is, static list). Both implementations support random access to their elements. An ArrayList instance supports array-style operations and supports array resize operations. An instance of LinkedList provides explicit support for adding, removing, and providing elements at the beginning and end of the list. Using these new methods, a programmer can simply use a LinedList as a stack or 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 code snippet in Table A demonstrates some common operations on implementation instances of the java.util.List interface using java.util.ArrayList and java.util.LinkedList. These operations include adding elements, randomly accessing elements, and explicitly removing elements from the end of the list.
Knowing what is happening and not knowing why is of great benefit
ADT provides a powerful tool for separating the operations in an object's public interface from its concrete implementation. This allows an ADT implementation to change and evolve while keeping its public interface unchanged. The Java collection architecture provides a large number of interfaces and implementations that represent collections of basic elements and can be used to create useful ADTs.