24.9. Thread Synchronization
22.5. Lists
A set stores nonduplicate elements. To allow duplicate elements to be stored in a collection, you need to use a list. A list can not only store duplicate elements, but also allows the user to specify where they are stored. The user can access elements by an index. 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 bi-directionally. The new methods in the List interface are shown in Figure 22.9.
Figure 22.9. The List interface stores elements in sequence, permitting duplicates.
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 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 first occurrence of the specified element in the list, and the lastIndexOf(element) method to obtain the index of the last occurrence of the specified element in the list. 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 bi-directional traversal of the list. The methods in ListIterator are listed in Figure 22.10.
Figure 22.10. ListIterator enables traversal of a list bi-directionally.
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 contains no 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.
22.5.1. The ArrayList and LinkedList Classes
The ArrayList class (introduced in §9.9, "The Array List 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, create a larger new array and copy all the elements from the current array 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 except at the end, ArrayList offers the most efficient collection. If, however, your application requires the insertion or deletion of elements anywhere in the list, you should choose LinkedList . A list can grow or shrink dynamically. An array is fixed once it is created. 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. In addition to implementing the List interface, this class provides methods for manipulating the size of the array that is used internally to store the list, as shown in Figure 22.11. Each ArrayList instance has a capacity. The capacity 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(intialCapacity) .
Figure 22.11. ArrayList implements List using an array.
(This item is displayed on page 724 in the print version)
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 22.12. A LinkedList can be constructed using its no-arg constructor or LinkedList(Collection) .
Figure 22.12. LinkedList provides methods for adding and inserting elements at both ends of the list.
Listing 22.6 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. The output of the program is shown in Figure 22.13.
Figure 22.13. The program uses an array list and linked lists.
(This item is displayed on page 726 in the print version)
Listing 22.6. TestArrayAndLinkedList.java
(This item is displayed on pages 725 - 726 in the print version)
1 import java.util.*; 2 3 public class TestArrayAndLinkedList { 4 public static void main(String[] args) { 5 List<Integer> arrayList = new ArrayList<Integer>(); 6 arrayList.add( 1 ); // 1 is autoboxed to new Integer(1) 7 arrayList.add( 2 ); 8 arrayList.add( 3 ); 9 arrayList.add( 1 ); 10 arrayList.add( 4 ); 11 arrayList.add( , 10 ); 12 arrayList.add( 3 , 30 ); 13 14 System.out.println( "A list of integers in the array list:" ); 15 System.out.println(arrayList); 16 17 LinkedList<Object> linkedList = new LinkedList<Object>(arrayList); 18 linkedList.add( 1 , "red" ); 19 linkedList.removeLast(); 20 linkedList.addFirst( "green" ); 21 22 System.out.println( "Display the linked list forward:" ); 23 ListIterator listIterator = linkedList.listIterator(); 24 while (listIterator.hasNext()) { 25 System.out.print(listIterator.next() + " " ); 26 } 27 System.out.println(); 28 29 System.out.println( "Display the linked list backward:" ); 30 listIterator = linkedList.listIterator(linkedList.size()); 31 while (listIterator.hasPrevious()) { 32 System.out.print(listIterator.previous() + " " ); 33 } 34 } 35 } |
A list can hold identical elements. Integer 1 is stored twice in the list (lines 6, 9). ArrayList and LinkedList are operated similarly. The critical difference between them pertains to internal implementation, which affects their performance. ArrayList is efficient for retrieving elements, and for inserting and removing elements from the end of the list. LinkedList is efficient for inserting and removing elements anywhere in the list.
Tip
| | Java provides the static asList method for creating a list from a variable-length argument list of a generic type. Thus you can use the following code to create a list of strings: List<String> list = Arrays.asList( "red" , "green" , "blue" ); |
EAN: N/A
Pages: 503