Data Structures and the Java Collections Framework, Third Edition

CHAPTER 6

Array-Based Lists

We begin this chapter by introducing the Java Collection Framework's List interface, which extends the Collection interface by providing some index-related methods. For example, there is a get method that returns the element at a given index. In any List object, that is, in any instance of a class that implements the List interface, the elements are stored in sequence, according to an index. For example, a List object pets might have the elements arranged as follows: ''dog'', ''cat'', ''iguana'', "gerbil". Here ''dog" is at index 0, and "gerbil" is at index 3.

The main focus of this chapter is the user's view of the ArrayList class. We start by investigating the method specifications. We then briefly turn to the developer's view: The Java Collection Framework's ArrayList class implements the List interface with an underlying array that allows constant-time access of any element from its index. We finish up the chapter with an application in the area of public-key cryptography.

As with all of the other collection classes in the Java Collections Framework, the ArrayList class is parameterized, and the element class is the type parameter, so it would be more appropriate to refer to the class as ArrayList<E>. When a user creates an instance of the ArrayList<E> class, the user specifies the element type that will replace the type parameter E. For example, to create an empty ArrayList object whose elements must be of type (reference to) String, we write ...