|
|
Start of Tutorial > Start of Trail > Start of Lesson |
Search
Feedback Form |
AListis an ordered
Collection(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from
Collection, theListinterface includes operations for:
- Positional Access: manipulate elements based on their numerical position in the list.
- Search: search for a specified object in the list and return its numerical position.
- List Iteration: extend
Iteratorsemantics to take advantage of the list's sequential nature.- Range-view: perform arbitrary range operations on the list.
The
Listinterface is shown below:The JDK contains two general-purposepublic interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, Collection c); // Optional // Search int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator listIterator(); ListIterator listIterator(int index); // Range-view List subList(int from, int to); }Listimplementations.ArrayList, which is generally the best-performing implementation, and
LinkedListwhich offers better performance under certain circumstances. Also,
Vectorhas been retrofitted to implementList. For more information on implementations, see the Implementations lesson.
If you've usedVector, you're already familiar with the general flavor of
List. (Of course,Listis an interface, whileVectoris a concrete implementation.)Listfixes several minor API deficiencies inVector. For starters, commonly usedVectoroperations such aselementAtandsetElementAthave been given much shorter names. When you consider that these two operations are theListanalogue of square brackets for arrays, it becomes apparent that shorter names are highly desirable. Consider the following assignment statement:a[i] = a[j].times(a[k]);TheVectorequivalent is:v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);TheListequivalent is:v.set(i, v.get(j).times(v.get(k)));You may already have noticed that thesetmethod, which replacessetElementAt, reverses the order of the arguments so that they match the corresponding array operation. Consider this assignment statement:beatle[5] = "Billy Preston";TheVectorequivalent is:beatle.setElementAt("Billy Preston", 5);TheListequivalent is:beatle.set(5, "Billy Preston");For consistency's sake, theadd(int, Object)method, which replacesinsertElementAt(Object, int), also reverses the order of the arguments.The various range operations in
Vector(indexOf,lastIndexOf(setSize) have been replaced by a single range-view operation (subList), which is far more powerful and consistent.
The operations inherited fromCollectionall do about what you'd expect them to do, assuming you're already familiar with them fromCollection. If you're not familiar with them, now would be a good time to read the lesson on theCollectioninterface. Theremoveoperation always removes the first occurrence of the specified element from the list. TheaddandaddAlloperations always append the new element(s) to the end of the list. Thus, the following idiom concatenates one list to another:Here's a non-destructive form of this idiom, which produces a thirdlist1.addAll(list2);Listconsisting of the second list appended to the first:Note that the idiom, in its non-destructive form, takes advantage ofList list3 = new ArrayList(list1); list3.addAll(list2);ArrayList's standardCollectionconstructor.Like the
Setinterface,
Liststrengthens the requirements on theequalsandhashCodemethods so that twoListobjects can be compared for logical equality without regard to their implementation classes. TwoListobjects are equal if they contain the same elements in the same order.
The basic positional access operations (get,set,addandremove) behave just like their longer-named counterparts inVector(elementAt,setElementAt,insertElementAtandremoveElementAt) with one noteworthy exception. Thesetandremoveoperations return the old value that is being overwritten or removed; theVectorcounterparts (setElementAtandremoveElementAt) return nothing (void). The search operationsindexOfandlastIndexOfbehave exactly like the identically named operations inVector.The
addAlloperation inserts all of the elements of the specifiedCollectionstarting at the specified position. The elements are inserted in the order they are returned by the specifiedCollection'siterator. This call is the positional access analogue ofCollection'saddAlloperation.Here's a little function to swap two indexed values in a
List. It should look familiar from Programming 101 (assuming you stayed awake):Of course there's one big difference. This is a polymorphic algorithm: it swaps two elements in anyprivate static void swap(List a, int i, int j) { Object tmp = a.get(i); a.set(i, a.get(j)); a.set(j, tmp); }List, regardless of its implementation type. "Big deal," you say, "What's it good for?" Funny you should ask. Take a look at this:This algorithm (which is included in the JDK'spublic static void shuffle(List list, Random rnd) { for (int i=list.size(); i>1; i--) swap(list, i-1, rnd.nextInt(i)); }Collectionsclass) randomly permutes the specified
Listusing the specified source of randomness. It's a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactlylist.size()-1iterations). The following short program uses this algorithm to print the words in its argument list in random order:In fact, we can make this program even shorter and faster. Theimport java.util.*; public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i=0; i<args.length; i++) l.add(args[i]); Collections.shuffle(l, new Random()); System.out.println(l); } }Arraysclass has a static factory method called
asListthat allows an array to be viewed as aList. This method does not copy the array; changes in theListwrite through to the array, and vice-versa. The resultingListis not a general-purposeListimplementation, in that it doesn't implement the (optional)addandremoveoperations: arrays are not resizable. Taking advantage ofArrays.asListand calling an alternate form ofshufflethat uses a default source of randomness, you get the followingtiny program, whose behavior is identical to the previous program:
import java.util.*; public class Shuffle { public static void main(String args[]) { List l = Arrays.asList(args); Collections.shuffle(l); System.out.println(l); } }
As you'd expect, theIteratorreturned byList'siteratoroperation returns the elements of the list in proper sequence. Additionally,Listprovides a richer iterator, called aListIterator, that allows you to traverse the list in either direction, modify the list during iteration, and obtain the current position of the iterator. TheListIteratorinterface is summarized below (including the three methods it inherits fromIterator):The three methods thatpublic interface ListIterator extends Iterator { boolean hasNext(); Object next(); boolean hasPrevious(); Object previous(); int nextIndex(); int previousIndex(); void remove(); // Optional void set(Object o); // Optional void add(Object o); // Optional }ListIteratorinherits fromIterator(hasNext,next, andremove) are intended to do exactly the same thing in both interfaces. ThehasPreviousandpreviousoperations are exact analogues ofhasNextandnext. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. Thepreviousoperation moves the cursor backwards whereasnextmoves it forwards.Here's the standard idiom for iterating backwards through a list:
Note the argument tofor (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) { Foo f = (Foo) i.previous(); ... }listIteratorin the above idiom. TheListinterface has two forms of thelistIteratormethod. The form with no arguments returns aListIteratorpositioned at the beginning of the list, and the form with anintargument returns aListIteratorpositioned at the specified index. The index refers to the element that would be returned by an initial call tonext. If the index value ofnis used, then the initial call tonextwould return null, since it would point just past the end of the list. An initial call topreviouswould return the element whose index wasindex-1. In a list of lengthn, there aren+1valid values forindex, from0ton, inclusive.Intuitively speaking, the cursor is always between two elements, the one that would be returned by a call to
previousand the one that would be returned by a call tonext. Then+1validindexvalues correspond to then+1"gaps" between elements, from the gap before the first element to the gap after the last one. The diagram below shows the five possible cursor positions in a list containing four elements.Element(0) Element(1) Element(2) Element(3) ^ ^ ^ ^ ^ Index: 0 1 2 3 4Calls tonextandpreviouscan be intermixed, but you have to be a bit careful. The first call topreviousafter a sequence of calls tonextreturns the same element as the last call tonext. Similarly, the first call tonextafter a sequence of calls topreviousreturns the same element as the last call toprevious. This will become obvious if you stare at the foregoing text long enough. If it doesn't, go get yourself a steaming hot mug of Java, and try again.It should come as no surprise that the
nextIndexmethod returns the index of the element that would be returned by a subsequent call tonext, andpreviousIndexreturns the index of the element that would be returned by a subsequent call toprevious. These calls are typically used for one of two purposes: To report the position where something was found, or to record the position of theListIteratorso that anotherListIteratorwith identical position can be created.It should also come as no surprise that the number returned by
nextIndexis always one greater than the number returned bypreviousIndex. This implies the behavior of the two boundary cases: a call topreviousIndexwhen the cursor is before the initial element returns-1, and a call tonextIndexwhen the cursor is after the final element returnslist.size()+1. To make all of this concrete, here's a possible implementation ofList.indexOf:Note that thepublic int indexOf(Object o) { for (ListIterator i = listIterator(); i.hasNext(); ) if (o==null ? i.next()==null : o.equals(i.next())) return i.previousIndex(); return -1; // Object not found }indexOfmethod returnsi.previousIndex()though it is traversing the list in the forward direction. This is becausei.nextIndex()would return the index of the element that we are about to examine, and we want to return the index of the element that we just examined.The
Iteratorinterface provides theremoveoperation to remove from theCollectionthe last element returned bynext. TheListIteratorinterface provides two additional operations to modify the list:setandadd. Thesetmethod "overwrites" the last element returned bynextorpreviouswith the specified element. It is demonstrated by the following polymorphic algorithm to replace all occurrences of one specified value with another:The only bit of trickiness in this example is the equality test betweenpublic static void replace(List l, Object val, Object newVal) { for (ListIterator i = l.listIterator(); i.hasNext(); ) if (val==null ? i.next()==null : val.equals(i.next())) i.set(newVal); }valandi.next. We have to special-case anvalvalue ofnullin order to prevent aNullPointerException.The
addmethod inserts a new element into the list, immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:public static void replace(List l, Object val, List newVals) { for (ListIterator i = l.listIterator(); i.hasNext(); ) { if (val==null ? i.next()==null : val.equals(i.next())) { i.remove(); for (Iterator j = newVals.iterator(); j.hasNext(); ) i.add(j.next()); } } }
The range-view operation,subList(int fromIndex, int toIndex), returns aListview of the portion of this list whose indices range fromfromIndex, inclusive, totoIndex, exclusive. This half-open range mirrors the typicalfor-loop:As the term view implies, the returnedfor (int i=fromIndex; i<toIndex; i++) { ... }Listis backed by theListon whichsubListwas called, so changes in the formerListare reflected in the latter.This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a
Listcan be used as a range operation by passing asubListview instead of a wholeList. For example, the following idiom removes a range of elements from a list:Similar idioms may be constructed to search for an element in a range:list.subList(fromIndex, toIndex).clear();Note that the above idioms return the index of the found element in theint i = list.subList(fromIndex, toIndex).indexOf(o); int j = list.subList(fromIndex, toIndex).lastIndexOf(o);subList, not the index in the backingList.Any polymorphic algorithm that operates on a
List(like thereplaceandshuffleexamples, above) works with theListreturned bysubList.Here's a polymorphic algorithm whose implementation uses
subListto deal a hand from a deck. That is to say, it returns a newList(the "hand") containing the specified number of elements taken from the end of the specifiedList(the "deck"). The elements returned in the hand are removed from the deck.The literal-minded might say that this program deals from the bottom of the deck, but I prefer to think that the computer is holding the deck upside down. At any rate, for many commonpublic static List dealHand(List deck, int n) { int deckSize = deck.size(); List handView = deck.subList(deckSize-n, deckSize); List hand = new ArrayList(handView); handView.clear(); return hand; }Listimplementations, likeArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.Here's
a programusing the
dealHandmethod in combination withCollections.shuffleto generate hands from a normal 52-card deck. The program takes two command line arguments: the number of hands to deal and the number of cards in each hand.
Let's run the program:import java.util.*; class Deal { public static void main(String args[]) { int numHands = Integer.parseInt(args[0]); int cardsPerHand = Integer.parseInt(args[1]); // Make a normal 52-card deck String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"}; String[] rank = new String[] {"ace","2","3","4","5","6","7","8", "9","10","jack","queen","king"}; List deck = new ArrayList(); for (int i=0; i<suit.length; i++) for (int j=0; j<rank.length; j++) deck.add(rank[j] + " of " + suit[i]); Collections.shuffle(deck); for (int i=0; i<numHands; i++) System.out.println(dealHand(deck, cardsPerHand)); } }% java Deal 4 5 [8 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds] [4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts] [7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs] [8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts]While the
subListoperation is extremely powerful, some care must be exercised when using it. The semantics of theListreturned bysubListbecome undefined if elements are added to or removed from the backingListin any way other than via the returnedList. Thus, it's highly recommended that you use theListreturned bysubListonly as a transient object, to perform one or a sequence of range operations on the backingList. The longer you use thesubListobject, the greater the probability that you'll compromise it by modifying the backingListdirectly (or through anothersubListobject).
Most of the polymorphic algorithms in theCollectionsclass apply specifically toList. Having all of these algorithms at your disposal makes it very easy to manipulate lists. Here's a summary of these algorithms, which are described in more detail in the Algorithms lesson.
sort(List): Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)shuffle(List): Randomly permutes the elements in aList. (Shown above.)reverse(List): Reverses the order of the elements in aList.fill(List, Object): Overwrites every element in aListwith the specified value.copy(List dest, List src): Copies the sourceListinto the destination List.binarySearch(List, Object): Searches for an element in an orderedListusing the binary search algorithm.
|
|
Start of Tutorial > Start of Trail > Start of Lesson |
Search
Feedback Form |
Copyright 1995-2004 Sun Microsystems, Inc. All rights reserved.