Lists

A List (sometimes called a sequence) is an ordered Collection that can contain duplicate elements. Like array indices, List indices are zero based (i.e., the first element's index is zero). In addition to the methods inherited from Collection, List provides methods for manipulating elements via their indices, manipulating a specified range of elements, searching for elements and getting a ListIterator to access the elements.

Interface List is implemented by several classes, including classes ArrayList, LinkedList and Vector. Autoboxing occurs when you add primitive-type values to objects of these classes, because they store only references to objects. Class ArrayList and Vector are resizable-array implementations of List. Class LinkedList is a linked-list implementation of interface List.

Class ArrayList's behavior and capabilities are similar to those of class Vector. The primary difference between Vector and ArrayList is that objects of class Vector are synchronized by default, whereas objects of class ArrayList are not. Also, class Vector is from Java 1.0, before the collections framework was added to Java. As such, Vector has several methods that are not part of interface List and are not implemented in class ArrayList, but perform identical tasks. For example, Vector methods addElement and add both append an element to a Vector, but only method add is specified in interface List and implemented by ArrayList. Unsynchronized collections provide better performance than synchronized ones. For this reason, ArrayList is typically preferred over Vector in programs that do not share a collection among threads.

Performance Tip 19.1

Software Engineering Observation 19.3

The following three subsections demonstrate the List and Collection capabilities with several examples. Section 19.5.1 focuses on removing elements from an ArrayList with an Iterator. Section 19.5.2 focuses on ListIterator and several List- and LinkedList-specific methods. Section 19.5.3 introduces more List methods and several Vector-specific methods.

19.5.1. ArrayList and Iterator

Figure 19.3 uses an ArrayList to demonstrate several Collection interface capabilities. The program places two Color arrays in ArrayLists and uses an Iterator to remove elements in the second ArrayList collection from the first ArrayList collection.

Figure 19.3. Collection interface demonstrated via an ArrayList object.

(This item is displayed on pages 912 - 913 in the print version)

Lines 1013 declare and initialize two String array variables, which are declared final, so they always refer to these arrays. Recall that it is good programing practice to declare constants with keywords static and final. Lines 1819 create ArrayList objects and assign their references to variables list and removeList, respectively. These two lists store String objects. Note that ArrayList is a generic class in J2SE 5.0, so we are able to specify a type argument (String in this case) to indicate the type of the elements in each list. Both list and removeList are collections of Strings. Lines 2223 populate list with Strings stored in array colors, and lines 2627 populate removelist with Strings stored in array removeColors using List method add. Lines 3233 output each element of list. Line 32 calls List method size to get the number of ArrayList elements. Line 33 uses List method get to retrieve individual element values. Lines 3233 could have used the enhanced for statement. Line 36 calls method removeColors (lines 4657), passing list and removeList as arguments. Method removeColors deletes Strings specified in removeList from the list collection. Lines 4142 print list's elements after removeColors removes the String objects specified in removeList from the list.

Method removeColors declares two Collection parameters (line 47) that allow any Collections containing strings to be passed as arguments to this method. The method accesses the elements of the first Collection (collection1) via an Iterator. Line 50 calls Collection method iterator to get an Iterator for the Collection. Note that interfaces Collection and Iterator are generic types. The loop-continuation condition (line 53) calls Iterator method hasNext to determine whether the Collection contains more elements. Method hasNext returns TRue if another element exists and false otherwise.

The if condition in line 55 calls Iterator method next to obtain a reference to the next element, then uses method contains of the second Collection (collection2) to determine whether collection2 contains the element returned by next. If so, line 56 calls Iterator method remove to remove the element from the Collection collection1.

Common Programming Error 19.2

19.5.2. LinkedList

Figure 19.4 demonstrates operations on LinkedLists. The program creates two LinkedLists that contain Strings. The elements of one List are added to the other. Then all the Strings are converted to uppercase, and a range of elements is deleted.

Figure 19.4. Lists and ListIterators.

(This item is displayed on pages 914 - 915 in the print version)

Lines 1718 create LinkedLists list1 and list2 of type String. Note that LinkedList is a generic class that has one type parameter for which we specify the type argument String in this example. Lines 2126 call List method add to append elements from arrays colors and colors2 to the end of list1 and list2, respectively.

Line 28 calls List method addAll to append all elements of list2 to the end of list1. Line 29 sets list2 to null, so the LinkedList to which list2 referred can be garbage collected. Line 30 calls method printList (lines 4250) to output list list1's contents. Line 32 calls method convertToUppercaseStrings (lines 5362) to convert each String element to uppercase, then line 33 calls printList again to display the modified Strings. Line 36 calls method removeItems (lines 6568) to remove the elements starting at index 4 up to, but not including, index 7 of the list. Line 38 calls method printReversedList (lines 7180) to print the list in reverse order.

Method convertToUppercaseStrings (lines 5362) changes lowercase String elements in its List argument to uppercase Strings. Line 55 calls List method listIterator to get a bidirectional iterator (i.e., an iterator that can traverse a List backward or forward) for the List. Note that ListIterator is a generic class. In this example, the ListIterator contains String objects, because method listIterator is called on a List of Strings. The while condition (line 57) calls method hasNext to determine whether the List contains another element. Line 59 gets the next String in the List. Line 60 calls String method toUpperCase to get an uppercase version of the String and calls ListIterator method set to replace the current String to which iterator refers with the String returned by method toUpperCase. Like method toUpperCase, String method toLowerCase returns a lowercase version of the String.

Method removeItems (lines 6568) removes a range of items from the list. Line 67 calls List method subList to obtain a portion of the List (called a sublist). The sublist is simply another view into the List on which subList is called. Method subList takes two argumentsthe beginning and the ending index for the sublist. The ending index is not part of the range of the sublist. In this example, we pass (in line 36) 4 for the beginning index and 7 for the ending index to subList. The sublist returned is the set of elements with indices 4 tHRough 6. Next, the program calls List method clear on the sublist to remove the elements of the sublist from the List. Any changes made to a sublist are also made to the original List.

Method printReversedList (lines 7180) prints the list backward. Line 73 calls List method listIterator with one argument that specifies the starting position (in our case, the last element in the list) to get a bidirectional iterator for the list. List method size returns the number of items in the List. The while condition (line 78) calls method hasPrevious to determine whether there are more elements while traversing the list backward. Line 79 gets the previous element from the list and outputs it to the standard output stream.

An important feature of the collections framework is the ability to manipulate the elements of one collection type (such as a set) through a different collection type (such as a list), regardless of the collection's internal implementation. The set of public methods through which collections are manipulated is called a view.

Class Arrays provides static method asList to view an array as a List collection (which encapsulates behavior similar to that of the linked lists created in Chapter 17). A List view allows the programmer to manipulate the array as if it were a list. This is useful for adding the elements in an array to a collection (e.g., a LinkedList) and for sorting array elements. The next example demonstrates how to create a LinkedList with a List view of an array, because we cannot pass the array to a LinkedList constructor. Sorting array elements with a List view is demonstrated in Fig. 19.9. Any modifications made through the List view change the array, and any modifications made to the array change the List view. The only operation permitted on the view returned by asList is set, which changes the value of the view and the backing array. Any other attempts to change the view (such as adding or removing elements) result in an UnsupportedOperationException.

Figure 19.5 uses method asList to view an array as a List collection and uses method toArray of a List to get an array from a LinkedList collection. The program calls method asList to create a List view of an array, which is then used for creating a LinkedList object, adds a series of strings to a LinkedList and calls method toArray to obtain an array containing references to the strings. Notice that the instantiation of LinkedList (line 13) indicates that LinkedList is a generic class that accepts one type argumentString, in this example.

Figure 19.5. List method toArray.

(This item is displayed on pages 917 - 918 in the print version)

Lines 1314 construct a LinkedList of Strings containing the elements of array colors and assigns the LinkedList reference to links. Note the use of Arrays method asList to return a view of the array as a List, then initialize the LinkedList with the List. Line 16 calls LinkedList method addLast to add "red" to the end of links. Lines 1718 call LinkedList method add to add "pink" as the last element and "green" as the element at index 3 (i.e., the fourth element). Note that method addLast (line 16) is identical in function to method add (line 17). Line 19 calls LinkedList method addFirst to add "cyan" as the new first item in the LinkedList. The add operations are permitted because they operate on the LinkedList object, not the view returned by asList. [Note: When "cyan" is added as the first element, "green" becomes the fifth element in the LinkedList.]

Line 22 calls List method toArray to get a String array from links. The array is a copy of the list's elementsmodifying the contents of the array does not modify the list. The array passed to method toArray is of the same type that you would like method toArray to return. If the number of elements in the array is greater than or equal to the number of elements in the LinkedList, toArray copies the list's elements into its array argument and returns that array. If the LinkedList has more elements than the number of elements in the array passed to toArray, toArray allocates a new array of the same type it receives as an argument, copies the list's elements into the new array and returns the new array.

Common Programming Error 19.3

19.5.3. Vector

Like ArrayList, class Vector provides the capabilities of array-like data structures that can resize themselves dynamically. Recall that class ArrayList's behavior and capabilities are similar to those of class Vector, except that ArrayLists do not provide synchronization by default. We cover class Vector here primarily because it is the superclass of class Stack, which is presented in Section 19.7.

At any time, a Vector contains a number of elements that is less than or equal to its capacity. The capacity is the space that has been reserved for the Vector's elements. If a Vector requires additional capacity, it grows by a capacity increment that you specify or by a default capacity increment. If you do not specify a capacity increment or specify one that is less than or equal to zero, the system will double the size of a Vector each time additional capacity is needed.

Performance Tip 19.2

Performance Tip 19.3

Performance Tip 19.4

Performance Tip 19.5

Figure 19.6 demonstrates class Vector and several of its methods. For complete information on class Vector, please visit java.sun.com/j2se/5.0/docs/api/java/util/Vector.html.

Figure 19.6. Vector class of package java.util.

(This item is displayed on pages 919 - 921 in the print version)

The application's constructor creates a Vector (line 13) of type String with an initial capacity of 10 elements and capacity increment of zero (the defaults for a Vector). Note that Vector is a generic class, which takes one argument that specifies the type of the elements stored in the Vector. A capacity increment of zero indicates that this Vector will double in size each time it needs to grow to accommodate more elements. Class Vector provides three other constructors. The constructor that takes one integer argument creates an empty Vector with the initial capacity specified by that argument. The constructor that takes two arguments creates a Vector with the initial capacity specified by the first argument and the capacity increment specified by the second argument. Each time the Vector needs to grow, it will add space for the specified number of elements in the capacity increment. The constructor that takes a Collection creates a copy of a collection's elements and stores them in the Vector.

Line 18 calls Vector method add to add objects (Strings in this program) to the end of the Vector. If necessary, the Vector increases its capacity to accommodate the new element. Class Vector also provides a method add that takes two arguments. This method takes an object and an integer and inserts the object at the specified index in the Vector. Method set will replace the element at a specified position in the Vector with a specified element. Method insertElementAt provides the same functionality as the method add that takes two arguments, except that the order of the parameters is reversed.

Line 25 calls Vector method firstElement to return a reference to the first element in the Vector. Line 26 calls Vector method lastElement to return a reference to the last element in the Vector. Each of these methods throws a NoSuchElementException if there are no elements in the Vector when the method is called.

Line 35 calls Vector method contains to determine whether the Vector contains "red". The method returns true if its argument is in the Vectorotherwise, the method returns false. Method contains uses Object method equals to determine whether the search key is equal to one of the Vector's elements. Many classes override method equals to perform the comparisons in a manner specific to those classes. For example, class String declares equals to compare the individual characters in the two Strings being compared. If method equals is not overridden, the original version of method equals inherited from class Object is used.

Common Programming Error 19.4

Line 37 calls Vector method indexOf to determine the index of the first location in the Vector that contains the argument. The method returns 1 if the argument is not found in the Vector. An overloaded version of this method takes a second argument specifying the index in the Vector at which the search should begin.

Performance Tip 19.6

Line 41 calls Vector method remove to remove the first occurrence of its argument from the Vector. The method returns true if it finds the element in the Vector; otherwise, the method returns false. If the element is removed, all elements after that element in the Vector shift one position toward the beginning of the Vector to fill in the position of the removed element. Class Vector also provides method removeAllElements to remove every element from a Vector and method removeElementAt to remove the element at a specified index.

Lines 5354 use Vector methods size and capacity to determine the number of elements currently in the Vector and the number of elements that can be stored in the Vector without allocating more memory, respectively.

Line 59 calls Vector method isEmpty to determine whether the Vector is empty. The method returns TRue if there are no elements in the Vector; otherwise, the method returns false. Lines 6667 use the enhanced for statement to print out all elements in the vector.

Among the methods introduced in Fig. 19.6, firstElement, lastElement and capacity can be used only with Vector. Other methods (e.g., add, contains, indexOf, remove, size and isEmpty) are declared by List, which means that they can be used by any class that implements List, such as Vector.