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

ArrayLists behave like Vectors without synchronization and therefore execute faster than Vectors because ArrayLists do not have the overhead of thread synchronization.

Software Engineering Observation 19.3

LinkedLists can be used to create stacks, queues, trees and deques (double-ended queues, pronounced "decks"). The collections framework provides implementations of some of these data structures.

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)

 1 // Fig. 19.3: CollectionTest.java
 2 // Using the Collection interface.
 3 import java.util.List;
 4 import java.util.ArrayList;
 5 import java.util.Collection;
 6 import java.util.Iterator;
 7
 8 public class CollectionTest
 9 {
10 private static final String[] colors =
11 { "MAGENTA", "RED", "WHITE", "BLUE", "CYAN" };
12 private static final String[] removeColors =
13 { "RED", "WHITE", "BLUE" };
14
15 // create ArrayList, add Colors to it and manipulate it
16 public CollectionTest()
17 {
18 List< String > list = new ArrayList< String >(); 
19 List< String > removeList = new ArrayList< String >();
20
21 // add elements in colors array to list
22 for ( String color : colors )
23 list.add( color );
24
25 // add elements in removeColors to removeList
26 for ( String color : removeColors )
27 removeList.add( color );
28
29 System.out.println( "ArrayList: " );
30
31 // output list contents
32 for ( int count = 0; count < list.size(); count++ )
33 System.out.printf( "%s ", list.get( count ) );
34
35 // remove colors contained in removeList
36 removeColors( list, removeList );
37
38 System.out.println( "

ArrayList after calling removeColors: " );
39
40 // output list contents
41 for ( String color : list )
42 System.out.printf( "%s ", color );
43 } // end CollectionTest constructor
44
45 // remove colors specified in collection2 from collection1
46 private void removeColors(
47 Collection< String > collection1, Collection< String > collection2 )
48 {
49 // get iterator
50 Iterator< String > iterator = collection1.iterator();
51
52 // loop while collection has items
53 while ( iterator.hasNext() )
54
55 if ( collection2.contains( iterator.next() ) )
56 iterator.remove(); // remove current Color
57 } // end method removeColors
58
59 public static void main( String args[] )
60 {
61 new CollectionTest();
62 } // end main
63 } // end class CollectionTest

 

ArrayList:
MAGENTA RED WHITE BLUE CYAN

ArrayList after calling removeColors:
MAGENTA CYAN

 

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

If a collection is modified by one of its methods after an iterator is created for that collection, the iterator immediately becomes invalidany operations performed with the iterator after this point throw ConcurrentModificationExceptions. For this reason, iterators are said to be "fail fast."

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)

 1 // Fig. 19.4: ListTest.java
 2 // Using LinkLists.
 3 import java.util.List;
 4 import java.util.LinkedList;
 5 import java.util.ListIterator;
 6
 7 public class ListTest
 8 {
 9 private static final String colors[] = { "black", "yellow",
10 "green", "blue", "violet", "silver" };
11 private static final String colors2[] = { "gold", "white",
12 "brown", "blue", "gray", "silver" };
13
14 // set up and manipulate LinkedList objects
15 public ListTest()
16 {
17 List< String > list1 = new LinkedList< String >();
18 List< String > list2 = new LinkedList< String >();
19
20 // add elements to list link
21 for ( String color : colors )
22 list1.add( color );
23
24 // add elements to list link2
25 for ( String color : colors2 )
26 list2.add( color );
27
28 list1.addAll( list2 ); // concatenate lists
29 list2 = null; // release resources
30 printList( list1 ); // print list1 elements
31
32 convertToUppercaseStrings( list1 ); // convert to upper case string
33 printList( list1 ); // print list1 elements
34
35 System.out.print( "
Deleting elements 4 to 6..." );
36 removeItems( list1, 4, 7 ); // remove items 4-7 from list
37 printList( list1 ); // print list1 elements
38 printReversedList( list1 ); // print list in reverse order
39 } // end ListTest constructor
40
41 // output List contents
42 public void printList( List< String > list )
43 {
44 System.out.println( "
list: " );
45
46 for ( String color : list )
47 System.out.printf( "%s ", color );
48
49 System.out.println();
50 } // end method printList
51
52 // locate String objects and convert to uppercase
53 private void convertToUppercaseStrings( List< String > list )
54 {
55 ListIterator< String > iterator = list.listIterator();
56
57 while ( iterator.hasNext() )
58 {
59 String color = iterator.next(); // get item 
60 iterator.set( color.toUpperCase() ); // convert to upper case
61 } // end while
62 } // end method convertToUppercaseStrings
63
64 // obtain sublist and use clear method to delete sublist items
65 private void removeItems( List< String > list, int start, int end )
66 {
67 list.subList( start, end ).clear();  // remove items
68 } // end method removeItems
69
70 // print reversed list
71 private void printReversedList( List< String > list )
72 {
73 ListIterator< String > iterator = list.listIterator( list.size() );
74
75 System.out.println( "
Reversed List:" );
76
77 // print list in reverse order
78 while ( iterator.hasPrevious() )
79 System.out.printf( "%s ", iterator.previous() );
80 } // end method printReversedList
81
82 public static void main( String args[] )
83 {
84 new ListTest();
85 } // end main
86 } // end class ListTest

 

list:
black yellow green blue violet silver gold white brown blue gray silver

list:
BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY SILVER

Deleting elements 4 to 6...
list:
BLACK YELLOW GREEN BLUE WHITE BROWN BLUE GRAY SILVER

Reversed List:
SILVER GRAY BLUE BROWN WHITE BLUE GREEN YELLOW BLACK

 

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)

 1 // Fig. 19.5: UsingToArray.java
 2 // Using method toArray.
 3 import java.util.LinkedList;
 4 import java.util.Arrays;
 5
 6 public class UsingToArray
 7 {
 8 // constructor creates LinkedList, adds elements and converts to array
 9 public UsingToArray()
10 {
11 String colors[] = { "black", "blue", "yellow" };
12
13 LinkedList< String > links = 
14  new LinkedList< String >( Arrays.asList( colors ) );
15
16 links.addLast( "red" ); // add as last item 
17 links.add( "pink" ); // add to the end 
18 links.add( 3, "green" ); // add at 3rd index 
19 links.addFirst( "cyan" ); // add as first item
20
21 // get LinkedList elements as an array 
22 colors = links.toArray( new String[ links.size() ] );
23
24 System.out.println( "colors: " );
25
26 for ( String color : colors )
27 System.out.println( color );
28 } // end UsingToArray constructor
29
30 public static void main( String args[] )
31 {
32 new UsingToArray();
33 } // end main
34 } // end class UsingToArray

 

colors:
cyan
black
blue
yellow
green
red
pink

 

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

Passing an array that contains data to toArray can cause logic errors. If the number of elements in the array is smaller than the number of elements in the list on which toArray is called, a new array is allocated to store the list's elementswithout preserving the array argument's elements. If the number of elements in the array is greater than the number of elements in the list, the elements of the array (starting at index zero) are overwritten with the list's elements. Array elements that are not overwritten retain their values.

 

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

Inserting an element into a Vector whose current size is less than its capacity is a relatively fast operation.

Performance Tip 19.3

Inserting an element into a Vector that needs to grow larger to accommodate the new element is a relatively slow operation.

Performance Tip 19.4

The default capacity increment doubles the size of the Vector. This may seem a waste of storage, but it is actually an efficient way for many Vectors to grow quickly to be "about the right size." This operation is much more efficient than growing the Vector each time by only as much space as it takes to hold a single element. The disadvantage is that the Vector might occupy more space than it requires. This is a classic example of the spacetime trade-off.

Performance Tip 19.5

If storage is at a premium, use Vector method trimToSize to trim a Vector's capacity to the Vector's exact size. This operation optimizes a Vector's use of storage. However, adding another element to the Vector will force the Vector to grow dynamically (again, a relatively slow operation)trimming leaves no room for growth.

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)

 1 // Fig. 19.6: VectorTest.java
 2 // Using the Vector class.
 3 import java.util.Vector; 
 4 import java.util.NoSuchElementException;
 5
 6 public class VectorTest
 7 {
 8 private static final String colors[] = { "red", "white", "blue" };
 9
10 public VectorTest()
11 {
12 Vector< String > vector = new Vector< String >();
13 printVector( vector ); // print vector
14
15 // add elements to the vector
16 for ( String color : colors )
17 vector.add( color );
18
19 printVector( vector ); // print vector
20
21 // output the first and last elements
22 try
23 {
24 System.out.printf( "First element: %s
", vector.firstElement());
25 System.out.printf( "Last element: %s
", vector.lastElement() );
26 } // end try
27 // catch exception if vector is empty
28 catch ( NoSuchElementException exception )
29 {
30 exception.printStackTrace();
31 } // end catch
32
33 // does vector contain "red"?
34 if ( vector.contains( "red" ) )
35 System.out.printf( "
"red" found at index %d

",
36 vector.indexOf( "red" ) );
37 else
38 System.out.println( "
"red" not found
" );
39
40 vector.remove( "red" ); // remove the string "red"
41 System.out.println( ""red" has been removed" );
42 printVector( vector ); // print vector
43
44 // does vector contain "red" after remove operation?
45 if ( vector.contains( "red" ) )
46 System.out.printf(
47 ""red" found at index %d
", vector.indexOf( "red" ) );
48 else
49 System.out.println( ""red" not found" );
50
51 // print the size and capacity of vector
52 System.out.printf( "
Size: %d
Capacity: %d
", vector.size(),
53 vector.capacity() );
54 } // end Vector constructor
55
56 private void printVector( Vector< String > vectorToOutput )
57 {
58 if ( vectorToOutput.isEmpty() )
59 System.out.print( "vector is empty" ); // vectorToOutput is empty
60 else // iterate through the elements
61 {
62 System.out.print( "vector contains: " );
63
64 // output elements
65 for ( String element : vectorToOutput )
66 System.out.printf( "%s ", element );
67 } // end else
68
69 System.out.println( "
" );
70 } // end method printVector
71
72 public static void main( String args[] )
73 {
74 new VectorTest(); // create object and call its constructor
75 } // end main
76 } // end class VectorTest

 

vector is empty

vector contains: red white blue

First element: red
Last element: blue

"red" found at index 0

"red" has been removed
vector contains: white blue

"red" not found

Size: 2
Capacity: 10

 

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

Without overriding method equals, the program performs comparisons using operator == to determine whether two references refer to the same object in memory.

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

Vector methods contains and indexOf perform linear searches of a Vector's contents. These searches are inefficient for large Vectors. If a program frequently searches for elements in a collection, consider using one of the Java Collection API's Map implementations (Section 19.10), which provide high-speed searching capabilities.

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.