Lists

The List interface extends the Collection interface and defines a collection for storing elements in a sequential order. To create a list, use one of its two concrete classes: ArrayList or LinkedList.

We used ArrayList to test the methods in the Collection interface in the preceding sections. Now we will examine ArrayList in more depth. We will also introduce another useful list, LinkedList, in this section.

The Common Methods in the List Interface

ArrayList and LinkedList are defined under the List interface. The List interface extends Collection to define an ordered collection with duplicates allowed. The List interface adds position-oriented operations, as well as a new list iterator that enables the user to traverse the list bidirectionally. The methods introduced in the List interface are shown in Figure below.

The add(index, element) method is used to insert an element at a specified index, and the addAll(index, collection) method to insert a collection of elements at a specified index. The remove(index) method is used to remove an element at the specified index from the list. A new element can be set at the specified index using the set(index, element) method.

The indexOf(element) method is used to obtain the index of the specified element’s first occurrence in the list, and the lastIndexOf(element) method to obtain the index of its last occurrence. A sublist can be obtained by using the subList(fromIndex, toIndex) method.

The listIterator() or listIterator(startIndex) method returns an instance of ListIterator. The ListIterator interface extends the Iterator interface to add bidirectional traversal of the list. The methods in ListIterator are listed in Figure below.

The add(element) method inserts the specified element into the list. The element is inserted immediately before the next element that would be returned by the next() method defined in the Iterator interface, if any, and after the element that would be returned by the previous() method, if any. If the list doesn’t contain any elements, the new element becomes the sole element in the list. The set(element) method can be used to replace the last element returned by the next method or the previous method with the specified element.

The hasNext() method defined in the Iterator interface is used to check whether the iterator has more elements when traversed in the forward direction, and the hasPrevious() 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.

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 below. 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 capacity to the size of the list. An ArrayList can be constructed using its no-arg constructor, ArrayList(Collection), or ArrayList(initialCapacity).

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

The code below gives a program that creates an array list filled with numbers and inserts new elements into specified locations in the list. The example also creates a linked list from the array list and inserts and removes elements from the list. Finally, the example traverses the
list forward and backward.

A list of integers in the array list:
[10, 1, 2, 30, 3, 1, 4]
Display the linked list forward:
green 10 red 1 2 30 3 1
Display the linked list backward:
1 3 30 2 1 red 10 green

A list can hold identical elements. Integer 1 is stored twice in the list (lines 8, 11). ArrayList and LinkedList operate similarly. The critical difference between them pertains to internal implementation, which affects their performance. ArrayList is efficient for retrieving elements and LinkedList is efficient for inserting and removing elements at the beginning of the list. Both have the same performance for inserting and removing elements in the middle or at the end of the list.

The get(i) method is available for a linked list, but it is a time-consuming operation. Do not use it to traverse all the elements in a list as shown in (a). Instead you should use an iterator as shown in (b). Note that a foreach loop uses an iterator implicitly.

Java provides the static asList method for creating a list from a variable-length list of arguments. Thus you can use the following code to create a list of strings and a list of integers:

List<String> list1 = Arrays.asList("red", "green", "blue");
List<Integer> list2 = Arrays.asList(10, 20, 30, 40, 50);