LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 769

method to check whether the iterator has more elements when traversed in the backward
direction.
The next() method defined in the Iterator interface returns the next element in
the iterator, and the previous() method returns the previous element in the iterator.
The nextIndex() method returns the index of the next element in the iterator, and the
previousIndex() returns the index of the previous element in the iterator.
The AbstractList class provides a partial implementation for the List interface.
The AbstractSequentialList class extends AbstractList to provide support for
linked lists.

20.4.2 The ArrayList and LinkedList Classes
The ArrayList class and the LinkedList class are two concrete implementations of the
List interface. ArrayList stores elements in an array. The array is dynamically created. If
the capacity of the array is exceeded, a larger new array is created and all the elements from
the current array are copied to the new array. LinkedList stores elements in a linked list .
Which of the two classes you use depends on your specific needs. If you need to support
random access through an index without inserting or removing elements at the beginning
of the list, ArrayList offers the most efficient collection. If, however, your application
requires the insertion or deletion of elements at the beginning of the list, you should choose
LinkedList . A list can grow or shrink dynamically. Once it is created, an array is fixed. If
your application does not require the insertion or deletion of elements, an array is the most
efficient data structure.
ArrayList is a resizable-array implementation of the List interface. It also provides
methods for manipulating the size of the array used internally to store the list, as shown
in Figure 20.5. Each ArrayList instance has a capacity, which is the size of the array used
to store the elements in the list. It is always at least as large as the list size. As elements
are added to an ArrayList , its capacity grows automatically. An ArrayList does not
automatically shrink. You can use the trimToSize() method to reduce the array capac-
ity to the size of the list. An ArrayList can be constructed using its no-arg constructor,
ArrayList(Collection) , or ArrayList(initialCapacity) .

ArrayList vs. LinkedList

linked list

trimToSize()

java.util.AbstractList < E >

java.util.ArrayList<E>

+ArrayList()
+ArrayList(c: Collection<? extends E>)
+ArrayList(initialCapacity: int)
+trimToSize(): void

Creates an empty list with the default initial capacity.
Creates an array list from an existing collection.
Creates an empty list with the specified initial capacity.
Trims the capacity of this ArrayList instance to be
the list's current size.

F IGURE 20.5

ArrayList implements List using an array.

LinkedList is a linked list implementation of the List interface. In addition to imple-
menting the List interface, this class provides the methods for retrieving, inserting, and
removing elements from both ends of the list, as shown in Figure 20.6. A LinkedList can be
constructed using its no-arg constructor or LinkedList(Collection) .