Java™ 教程（List接口）

List是一个有序的Collection（有时称为序列），列表可能包含重复元素，除了从Collection继承的操作之外，List接口还包括以下操作：

位置访问 — 根据列表中的数字位置操纵元素，这包括get、set、add、addAll和remove等方法。

搜索 — 搜索列表中的指定对象并返回其数字位置，搜索方法包括indexOf和lastIndexOf。

迭代 — 扩展Iterator语义以利用列表的顺序性，listIterator方法提供此行为。

范围视图 — sublist方法对列表执行任意范围操作。

Java平台包含两个通用的List实现，ArrayList，通常是性能更好的实现，而LinkedList在某些情况下提供更好的性能。

假设你已经熟悉它们，那么从Collection继承的操作都可以完成你期望它们做的事情，如果你不熟悉Collection，现在是阅读Collection接口部分的好时机，remove操作始终从列表中删除指定元素的第一个匹配项，add和addAll操作始终将新元素附加到列表的末尾，因此，以下语法将一个列表连接到另一个列表。

list1.addAll(list2);

这是这个语法的非破坏性形式，它产生第三个List，其中包含附加到第一个列表的第二个列表。

List list3 = new ArrayList(list1);
list3.addAll(list2);

请注意，此语法在其非破坏性形式中利用了ArrayList的标准转换构造函数。

这是一个将一些名称聚合到List中的示例（JDK 8及更高版本）：

List list = people.stream()
.map(Person::getName)
.collect(Collectors.toList());

与Set接口一样，List强化了对equals和hashCode方法的需求，因此可以比较两个List对象的逻辑相等性，而不考虑它们的实现类，如果两个List对象包含相同顺序的相同元素，则它们是相等的。

基础的位置访问操作是get、set、add和remove（set和remove操作返回被覆盖或删除的旧值），其他操作（indexOf和lastIndexOf）返回列表中指定元素的第一个或最后一个索引。

addAll操作从指定位置开始插入指定Collection的所有元素，元素按指定Collection的迭代器返回的顺序插入，此调用是Collection的addAll操作的位置访问模拟。

这是在List中交换两个索引值的一个小方法。

public static  void swap(List a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

当然，有一个很大的区别，这是一个多态算法：它交换任何List中的两个元素，无论其实现类型如何，这是另一种使用前面swap方法的多态算法。

public static void shuffle(List list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

此算法包含在Java平台的Collections类中，使用指定的随机源随机置换指定的列表，这有点微妙：它从底部向上运行列表，反复将随机选择的元素交换到当前位置。不像大多数天真的洗牌尝试，这是公平的（假设一个公平的随机源，所有排列都有相同的可能性）和快速（需要完全list.size()-1交换），以下程序使用此算法以随机顺序打印其参数列表中的单词。

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List list = new ArrayList();
        for (String a : args)
            list.add(a);
        Collections.shuffle(list, new Random());
        System.out.println(list);
    }
}

事实上，这个程序可以更短、更快，Arrays类有一个名为asList的静态工厂方法，它允许将数组视为List，此方法不会复制数组，List中的更改会写入数组，反之亦然。生成的List不是通用List实现，因为它没有实现（可选）add和remove操作：数组不可调整大小。利用Arrays.asList并调用shuffle的库版本（使用默认的随机源），你将得到以下微小程序，其行为与前一个程序相同。

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List list = Arrays.asList(args);
        Collections.shuffle(list);
        System.out.println(list);
    }
}

正如你所期望的那样，List的iterator操作返回的Iterator以适当的顺序返回列表的元素，List还提供了一个更丰富的迭代器，称为ListIterator，它允许你在任一方向遍历列表、在迭代期间修改列表、并获取迭代器的当前位置。

ListIterator从Iterator继承的三个方法（hasNext、next和remove）在两个接口中完全相同，hasPrevious和previous操作和hasNext和next的很相似，前一个操作引用（隐式）游标之前的元素，而后者引用游标之后的元素，previous操作向后移动光标，而next向前移动光标。

这是在列表中向后迭代的标准语法。

for (ListIterator it = list.listIterator(list.size()); it.hasPrevious(); ) {
    Type t = it.previous();
    ...
}

请注意前面的语法中listIterator的参数，List接口有两种形式的listIterator方法，不带参数的形式返回位于列表开头的ListIterator，带有int参数的形式返回一个位于指定索引处的ListIterator。索引引用初始调用next返回的元素，对previous的初始调用将返回索引为index-1的元素，在长度为n的列表中，index有n+1个有效值，从0到n（包括n）。

直观地说，游标总是在两个元素之间 — 一个将通过调用previous返回，一个将通过调用next返回。n+1个有效索引值对应于元素之间的n+1个间隙，从第一个元素之前的间隙到最后一个元素之后的间隙，下图显示了包含四个元素的列表中的五个可能的游标位置。

对next和previous的调用可以混合使用，但是必须小心一点，对previous的第一次调用返回与对next的最后一次调用相同的元素，类似地，在对previous进行一系列调用之后，对next的第一次调用与对previous的最后一次调用返回相同的元素。

nextIndex方法返回后续调用next返回的元素的索引，并且previousIndex返回后续调用previous返回的元素的索引，这些调用通常用于报告找到某些内容的位置或记录ListIterator的位置，以便可以创建具有相同位置的另一个ListIterator。

同样也不足为奇的是，nextIndex返回的数字总是大于previousIndex返回的数字，这意味着两种边界情况的行为：（1）当光标位于初始元素之前时对previousIndex的调用返回-1，当光标位于最后一个元素之后时调用nextIndex返回list.size()。为了使所有这些具体化，以下是List.indexOf的可能实现。

public int indexOf(E e) {
    for (ListIterator it = listIterator(); it.hasNext(); )
        if (e == null ? it.next() == null : e.equals(it.next()))
            return it.previousIndex();
    // Element not found
    return -1;
}

请注意，indexOf方法返回it.previousIndex()，即使它正在向前遍历列表，原因是it.nextIndex()将返回我们要检查的元素的索引，并且我们想要返回刚检查的元素的索引。

Iterator接口提供remove操作以从Collection中删除next返回的最后一个元素，对于ListIterator，此操作将删除next或previous返回的最后一个元素。ListIterator接口提供了两个额外的操作来修改列表 — set和add，set方法用指定的元素覆盖next或previous返回的最后一个元素，以下多态算法使用set将一个指定值的所有出现替换为另一个。

public static  void replace(List list, E val, E newVal) {
    for (ListIterator it = list.listIterator(); it.hasNext(); )
        if (val == null ? it.next() == null : val.equals(it.next()))
            it.set(newVal);
}

在这个例子中唯一的棘手是val和it.next之间的相等性测试，你需要特殊情况下val值为null以防止NullPointerException。

add方法在当前光标位置之前立即将新元素插入到列表中，此方法在以下多态算法中说明，以使用指定列表中包含的值序列替换指定值的所有出现。

public static  
    void replace(List list, E val, List newVals) {
    for (ListIterator it = list.listIterator(); it.hasNext(); ){
        if (val == null ? it.next() == null : val.equals(it.next())) {
            it.remove();
            for (E e : newVals)
                it.add(e);
        }
    }
}

范围视图操作subList(int fromIndex，int toIndex)返回此列表部分的List视图，其索引范围从fromIndex（包括）到toIndex（不包括），这个半开放范围反映了典型的for循环。

for (int i = fromIndex; i < toIndex; i++) {
    ...
}

正如术语视图所暗示的那样，返回的List由调用了subList的List进行备份，因此前者中的更改将反映在后者中。

此方法消除了对显式范围操作的需要（对于数组通常存在的排序），任何期望List的操作都可以通过传递subList视图而不是整个List来用作范围操作，例如，以下语句从List中删除了一系列元素。

list.subList(fromIndex, toIndex).clear();

可以构造类似的语句以搜索范围中的元素。

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

请注意，前面的语句返回subList中找到的元素的索引，而不是支持列表中的索引。

在List上操作的任何多态算法（例如replace和shuffle示例）都与subList返回的List一起使用。

这是一个多态算法，其实现使用subList来处理来自牌组的牌，也就是说，它返回一个新的List（“hand”），它包含从指定List（“deck”）末尾获取的指定数量的元素，手中返回的元素将从牌组中移除。

public 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;
}

请注意，此算法将牌从牌组末端移除，对于许多常见的List实现，例如ArrayList，从列表末尾删除元素的性能明显优于从头开始删除元素的性能。

以下是一个程序，它将dealHand方法与Collections.shuffle结合使用，从正常的52张卡牌中生成牌局，该程序采用两个命令行参数：（1）手牌数（2）每手牌数。

import java.util.*;

public class Deal {
    public static void main(String[] args) {
        if (args.length < 2) {
            System.out.println("Usage: Deal hands cards");
            return;
        }
        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]);
    
        // Shuffle the deck.
        Collections.shuffle(deck);
    
        if (numHands * cardsPerHand > deck.size()) {
            System.out.println("Not enough cards.");
            return;
        }
    
        for (int i = 0; i < numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
  
    public 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;
    }
}

运行程序会产生如下输出。

% 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]

尽管subList操作非常强大，但在使用它时必须小心，如果以通过返回的List之外的任何方式向支持List添加或删除元素，则subList返回的List的语义将变为undefined。因此，强烈建议你仅将subList返回的List用作临时对象 — 在支持List上执行一个或一系列范围操作，使用subList实例的时间越长，通过直接修改支持List或通过另一个subList对象来破坏它的可能性就越大，请注意，修改子列表的子列表并继续使用原始子列表（尽管不是并发）是合法的。

Collections类中的大多数多态算法专门应用于List，拥有所有这些算法可以很容易地操作列表，以下是这些算法的摘要，这些算法在“算法”部分中有更详细的描述。

sort — 使用合并排序算法对List进行排序，该算法提供快速、稳定的排序（稳定排序是不重新排序相同元素的排序）。

shuffle — 随机置换List中的元素。

reverse — 反转List中元素的顺序。

rotate — 将List中的所有元素旋转指定的距离。

swap — 交换列表中指定位置的元素。

replaceAll — 将所有出现的一个指定值替换为另一个。

fill — 用指定的值覆盖List中的每个元素。

copy — 将源列表复制到目标列表。

binarySearch — 使用二进制搜索算法搜索有序List中的元素。

indexOfSubList — 返回一个List的第一个子列表的索引，该列表等于另一个。

lastIndexOfSubList — 返回一个List的最后一个子列表的索引，该列表等于另一个。