12.1 Lists
Once an array is created, its length cannot be changed. This inflexibility can be a significant drawback when the amount of data to be stored in an array is not known a priori. In Java, the structures known as lists alleviate this shortcoming. Lists are collections that maintain their elements in order and can contain duplicates. The order of elements in a list is positional order, and individual elements can be accessed according to their position in the list. Each element, therefore, has a position in the list. A zero-based index can be used to access the element at the position designated by the index value, analogous to accessing elements in an array. However, unlike in an array, the position of an element in a list can change as elements are inserted or deleted from the list—that is, as the list changes dynamically.
Sorting implies ordering the elements in a collection according to some ranking criteria, usually based on the values of the elements. However, elements is an ArrayList are maintained in the order they are inserted in the list, known as the insertion order. The elements in such a list are therefore ordered, but they are not sorted, as it is not the values of the elements that determine their ranking in the list. Thus ordering does not necessarily imply sorting.
Overview of the Java Collections Framework
The Collection<E> interface in the java.util package (also known as the Java Collections Framework) defines the general operations that a collection should provide (see Figure 12.1). Note that the Collection<E> interface extends the Iterable<E> interface, so all collections in this framework can be traversed using the for(:) loop. Other subinterfaces in the Java Collections Framework augment this interface to provide specific operations for particular kinds of collections. The java.util.List<E> interface extends the java.util.Collection<E> interface with the operations necessary to maintain the collection as a list. In addition to the operations inherited from the java.util.Collection<E> interface, the java.util.List<E> interface defines operations that work specifically on lists: position-based access of the list elements, searching in a list, operations on parts of a list (called open range-view operations), and creation of customized iterators to iterate over a list. For methods used in this chapter, we will indicate which interface they are defined in. The impatient reader can refer to Chapter 15, p. 781, at any time for more details on these interfaces.
Figure 12.1 Partial ArrayList Inheritance Hierarchy
The generic class java.util.ArrayList<E> implements the java.util.List<E> interface. The type parameter E represents the type of the element in the list. Use of a generic type requires a concrete reference type to be substituted for the type parameter E. For example, the parameterized class ArrayList<String> is an ArrayList of String, where the type parameter T is substituted with the concrete class String.
The ArrayList<E> class is a dynamically resizable implementation of the List<E> interface using arrays (also known as dynamic arrays), providing fast random access (i.e., position-based access in constant time) and fast list traversal—very much like using an ordinary array. The ArrayList<E> class is not thread-safe; that is, its integrity can be jeopardized by concurrent access. The Java Collections Framework provides other implementations of the List<E> interface, but in most cases the ArrayList<E> implementation is the overall best choice for implementing lists.
Leave a Reply