AList
is an orderedCollection
(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited fromCollection
, theList
interface includes operations for the following:
Positional access
manipulates elements based on their numerical position in the listSearch
searches for a specified object in the list and returns its numerical positionIteration
extendsIterator
semantics to take advantage of the list's sequential natureRange-view
performs arbitrary range operations on the list.The
List
interface follows.The Java platform contains two general-purposepublic interface List<E> extends Collection<E> { // Positional access E get(int index); E set(int index, E element); //optional boolean add(E element); //optional void add(int index, E element); //optional E remove(int index); //optional boolean addAll(int index, Collection<? extends E> c); //optional // Search int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); // Range-view List<E> subList(int from, int to); }List
implementations.ArrayList
, which is usually the better-performing implementation, andLinkedList
which offers better performance under certain circumstances. Also,Vector
has been retrofitted to implementList
.
If you've usedVector
, you're already familiar with the general basics ofList
. (Of course,List
is an interface, whileVector
is a concrete implementation.)List
fixes several minor API deficiencies inVector
. Commonly usedVector
operations, such aselementAt
andsetElementAt
, have been given much shorter names. When you consider that these two operations are theList
analog of square brackets for arrays, it becomes apparent that shorter names are highly desirable. Consider the following assignment statement.Thea[i] = a[j].times(a[k]);Vector
equivalent is:Thev.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);List
equivalent is:You may already have noticed that thev.set(i, v.get(j).times(v.get(k)));set
method, which replaces theVector
methodsetElementAt
, reverses the order of the arguments so that they match the corresponding array operation. Consider the following assignment statement.Thegift[5] = "golden rings";Vector
equivalent is:Thegift.setElementAt("golden rings", 5);List
equivalent is:For consistency's sake, the methodgift.set(5, "golden rings");add(int, E)
, which replacesinsertElementAt(Object, int)
, also reverses the order of the arguments.The three range operations in
Vector
(indexOf
,lastIndexOf
, andsetSize
) have been replaced by a single range-view operation (subList
), which is far more powerful and consistent.
The operations inherited fromCollection
all do about what you'd expect them to do, assuming you're already familiar with them. If you're not familiar with them fromCollection
, now would be a good time to read The Collection Interface section. Theremove
operation always removes the first occurrence of the specified element from the list. Theadd
andaddAll
operations always append the new element(s) to the end of the list. Thus, the following idiom concatenates one list to another.Here's a nondestructive form of this idiom, which produces a thirdlist1.addAll(list2);List
consisting of the second list appended to the first.Note that the idiom, in its nondestructive form, takes advantage ofList<Type> list3 = new ArrayList<Type>(list1); list3.addAll(list2);ArrayList
's standard conversion constructor.Like the
Set
interface,List
strengthens the requirements on theequals
andhashCode
methods so that twoList
objects can be compared for logical equality without regard to their implementation classes. TwoList
objects are equal if they contain the same elements in the same order.
The basicpositional access
operations (get
,set
,add
andremove
) behave just like their longer-named counterparts inVector
(elementAt
,setElementAt
,insertElementAt
, andremoveElementAt
) with one noteworthy exception: Theset
andremove
operations return the old value that is being overwritten or removed; theVector
counterparts (setElementAt
andremoveElementAt
) return nothing (void
). Thesearch
operationsindexOf
andlastIndexOf
behave exactly like the identically named operations inVector
.The
addAll
operation inserts all the elements of the specifiedCollection
starting at the specified position. The elements are inserted in the order they are returned by the specifiedCollection
's iterator. This call is the positional access analog ofCollection
'saddAll
operation.Here's a little method to swap two indexed values in a
List
. It should look familiar from Programming 101.Of course, there's one big difference. This is a polymorphic algorithm: It swaps two elements in anypublic static <E> void swap(List<E> a, int i, int j) { E tmp = a.get(i); a.set(i, a.get(j)); a.set(j, tmp); }List
, regardless of its implementation type. Here's another polymorphic algorithm that uses the precedingswap
method.This algorithm, which is included in the Java platform'spublic static void shuffle(List<?> list, Random rnd) { for (int i = list.size(); i > 1; i--) swap(list, i - 1, rnd.nextInt(i)); }Collections
class, randomly permutes the specified list using 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()-1
swaps). The following program uses this algorithm to print the words in its argument list in random order.In fact, this program can be made even shorter and faster. Theimport java.util.*; public class Shuffle { public static void main(String[] args) { List<String> list = new ArrayList<String>(); for (String a : args) list.add(a); Collections.shuffle(list, new Random()); System.out.println(list); } }Arrays
class has a static factory method calledasList
, which allows an array to be viewed as aList
. This method does not copy the array. Changes in theList
write through to the array and vice versa. The resulting List is not a general-purposeList
implementation, because it doesn't implement the (optional)add
andremove
operations: Arrays are not resizable. Taking advantage ofArrays.asList
and calling the library version ofshuffle
, which 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<String> list = Arrays.asList(args); Collections.shuffle(list); System.out.println(list); } }
As you'd expect, theIterator
returned byList
'siterator
operation returns the elements of the list in proper sequence.List
also provides a richer iterator, called aListIterator
, which allows you to traverse the list in either direction, modify the list during iteration, and obtain the current position of the iterator. TheListIterator
interface follows.The three methods thatpublic interface ListIterator<E> extends Iterator<E> { boolean hasNext(); E next(); boolean hasPrevious(); E previous(); int nextIndex(); int previousIndex(); void remove(); //optional void set(E e); //optional void add(E e); //optional }ListIterator
inherits fromIterator
(hasNext
,next
, andremove
) do exactly the same thing in both interfaces. ThehasPrevious
and theprevious
operations are exact analogues ofhasNext
andnext
. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. Theprevious
operation moves the cursor backward, whereasnext
moves it forward.Here's the standard idiom for iterating backward through a list.
Note the argument tofor (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) { Type t = it.previous(); ... }listIterator
in the preceding idiom. TheList
interface has two forms of thelistIterator
method. The form with no arguments returns aListIterator
positioned at the beginning of the list; the form with anint
argument returns aListIterator
positioned at the specified index. The index refers to the element that would be returned by an initial call tonext
. An initial call toprevious
would return the element whose index wasindex-1
. In a list of lengthn
, there aren+1
valid values forindex
, from0
ton
, inclusive.Intuitively speaking, the cursor is always between two elements the one that would be returned by a call to
previous
and the one that would be returned by a call tonext
. Then+1
validindex
values correspond to then+1
gaps between elements, from the gap before the first element to the gap after the last one. The following figure shows the five possible cursor positions in a list containing four elements.Calls to The five possible cursor positions.
next
andprevious
can be intermixed, but you have to be a bit careful. The first call toprevious
returns the same element as the last call tonext
. Similarly, the first call tonext
after a sequence of calls toprevious
returns the same element as the last call toprevious
.It should come as no surprise that the
nextIndex
method returns the index of the element that would be returned by a subsequent call tonext
, andpreviousIndex
returns the index of the element that would be returned by a subsequent call toprevious
. These calls are typically used either to report the position where something was found or to record the position of theListIterator
so that anotherListIterator
with identical position can be created.It should also come as no surprise that the number returned by
nextIndex
is always one greater than the number returned bypreviousIndex
. This implies the behavior of the two boundary cases: (1) a call topreviousIndex
when the cursor is before the initial element returns-1
and (2) a call tonextIndex
when the cursor is after the final element returnslist.size()
. To make all this concrete, the following is a possible implementation ofList.indexOf
.Note that thepublic int indexOf(E e) { for (ListIterator<E> it = listIterator(); it.hasNext(); ) if (e == null ? it.next() == null : e.equals(it.next())) return it.previousIndex(); return -1; // Element not found }indexOf
method returnsit.previousIndex()
even though it is traversing the list in the forward direction. The reason is thatit.nextIndex()
would return the index of the element we are about to examine, and we want to return the index of the element we just examined.The
Iterator
interface provides theremove
operation to remove the last element returned bynext
from theCollection
. ForListIterator
, this operation removes the last element returned bynext
orprevious
. TheListIterator
interface provides two additional operations to modify the list set
andadd
. Theset
method overwrites the last element returned bynext
orprevious
with the specified element. The following polymorphic algorithm usesset
to replace all occurrences of one specified value with another.The only bit of trickiness in this example is the equality test betweenpublic static <E> void replace(List<E> list, E val, E newVal) { for (ListIterator<E> it = list.listIterator(); it.hasNext(); ) if (val == null ? it.next() == null : val.equals(it.next())) it.set(newVal); }val
andit.next
. You need to special-case aval
value ofnull
to prevent aNullPointerException
.The
add
method 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 <E> void replace(List<E> list, E val, List<? extends E> newVals) { for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){ if (val == null ? it.next() == null : val.equals(it.next())) { it.remove(); for (E e : newVals) it.add(e); } } }
Therange-view
operation,subList(int fromIndex, int toIndex)
, returns aList
view 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++) { ... }List
is backed up by theList
on whichsubList
was called, so changes in the former are 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
List
can be used as a range operation by passing asubList
view instead of a wholeList
. For example, the following idiom removes a range of elements from aList
.Similar idioms can be constructed to search for an element in a range.list.subList(fromIndex, toIndex).clear();Note that the preceding 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
, such as thereplace
andshuffle
examples, works with theList
returned bysubList
.Here's a polymorphic algorithm whose implementation uses
subList
to deal a hand from a deck. That is, 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.Note that this algorithm removes the hand from the end of the deck. For many commonpublic static <E> List<E> dealHand(List<E> deck, int n) { int deckSize = deck.size(); List<E> handView = deck.subList(deckSize - n, deckSize); List<E> hand = new ArrayList<E>(handView); handView.clear(); return hand; }List
implementations, such asArrayList
, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.The following is
a program
that uses thedealHand
method in combination withCollections.shuffle
to generate hands from a normal 52-card deck. The program takes two command-line arguments: (1) the number of hands to deal and (2) the number of cards in each hand.Running the program produces the following output.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<String> deck = new ArrayList<String>(); 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]Although the
subList
operation is extremely powerful, some care must be exercised when using it. The semantics of theList
returned bysubList
become undefined if elements are added to or removed from the backingList
in any way other than via the returnedList
. Thus, it's highly recommended that you use theList
returned bysubList
only as a transient object to perform one or a sequence of range operations on the backingList
. The longer you use thesubList
instance, the greater the probability that you'll compromise it by modifying the backingList
directly or through anothersubList
object. Note that it is legal to modify a sublist of a sublist and to continue using the original sublist (though not concurrently).
Most polymorphic algorithms in theCollections
class apply specifically toList
. Having all 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 section.
sort
sorts aList
using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)shuffle
randomly permutes the elements in aList
.reverse
reverses the order of the elements in aList
.rotate
rotates all the elements in aList
by a specified distance.swap
swaps the elements at specified positions in aList
.replaceAll
replaces all occurrences of one specified value with another.fill
overwrites every element in aList
with the specified value.copy
copies the sourceList
into the destinationList
.binarySearch
searches for an element in an orderedList
using the binary search algorithm.indexOfSubList
returns the index of the first sublist of oneList
that is equal to another.lastIndexOfSubList
returns the index of the last sublist of oneList
that is equal to another.