# 列表接口

> 原文： [https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html](https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html)

[`List`](https://docs.oracle.com/javase/8/docs/api/java/util/List.html) 是有序的 [`Collection`](https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html) （有时称为*序列*）。列表可能包含重复元素。除了从`Collection`继承的操作之外，`List`接口还包括以下操作：

*   `Positional access` - 根据列表中的数字位置操纵元素。这包括`get`，`set`，`add`，`addAll`和`remove`等方法。
*   `Search` - 搜索列表中的指定对象并返回其数字位置。搜索方法包括`indexOf`和`lastIndexOf`。
*   `Iteration` - 扩展`Iterator`语义以利用列表的顺序特性。 `listIterator`方法提供此行为。
*   `Range-view` - `sublist`方法在列表中执行任意*范围操作*。

Java 平台包含两个通用`List`实现。 [`ArrayList`](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) ，通常表现较好， [`LinkedList`](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html) 在某些情况下可提供更好的性能。

## 收集操作

假设您已经熟悉它们，那么从`Collection`继承的操作都可以完成您期望它们做的事情。如果您不熟悉`Collection`，现在是阅读[`collection`接口](collection.html)部分的好时机。 `remove`操作始终从列表中删除*指定元素的第一个*。 `add`和`addAll`操作总是将新元素附加到列表的*端*。因此，以下习语将一个列表连接到另一个列表。

```java
list1.addAll(list2);

```

这是这个习语的非破坏性形式，它产生第三个`List`，由第一个附加的第二个列表组成。

```java
List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);

```

请注意，成语以其非破坏性形式利用了`ArrayList`的标准转换构造器。

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

```java
List<String> list = people.stream()
.map(Person::getName)
.collect(Collectors.toList());

```

与 [`Set`](https://docs.oracle.com/javase/8/docs/api/java/util/Set.html) 接口类似，`List`增强了对`equals`和`hashCode`方法的要求，因此可以比较两个`List`对象的逻辑相等性，而不考虑它们的实现类。如果两个`List`对象包含相同顺序的相同元素，则它们是相等的。

## 位置访问和搜索操作

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

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

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

```java
public 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`中交换两个元素，而不管其实现类型如何。这是另一种使用前面`swap`方法的多态算法。

```java
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`](https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html) 类中，使用指定的随机源随机置换指定的列表。它有点微妙：它从底部向上运行列表，反复地将随机选择的元素交换到当前位置。与大多数幼稚的洗牌尝试不同，它是*公平*（所有排列均以相同的可能性发生，假设无偏倚的随机源）和*快*（需要完全`list.size()-1`交换）。以下程序使用此算法以随机顺序打印其参数列表中的单词。

```java
import 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`](https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html) 类有一个名为`asList`的静态工厂方法，它允许将数组视为`List`。此方法不会复制数组。 `List`的更改写入数组，反之亦然。生成的 List 不是通用的`List`实现，因为它没有实现（可选）`add`和`remove`操作：数组不可调整大小。利用`Arrays.asList`并调用`shuffle`的库版本（使用默认的随机源），您将得到以下 [`tiny program`](examples/Shuffle.java) ，其行为与之前的程序相同。

```java
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);
    }
}

```

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

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

这是在列表中向后迭代的标准习惯用法。

```java
for (ListIterator<Type> 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`，包括在内。

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

![Five arrows representing five cursor positions, from 0 to 4, with four elements, one between each arrow.](img/f7b88bd0a9491d7a605ea7c612526c1e.jpg)

五个可能的光标位置。



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

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

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

```java
public int indexOf(E e) {
    for (ListIterator<E> 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`将一个指定值的所有出现替换为另一个。

```java
public 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`和`it.next`之间的相等性测试。您需要特殊情况`val`的`val`值以防止`NullPointerException`。

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

```java
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);
        }
    }
}

```

## 范围视图操作

`range-view`操作`subList(int fromIndex, int toIndex)`返回该列表部分的`List`视图，其索引范围从`fromIndex`（包括）到`toIndex`，不包括。这个*半开范围*反映了典型的`for`环路。

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

```

正如*视图*所暗示的那样，返回的`List`由调用`subList`的`List`备份，因此前者的变化反映在后者中。

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

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

```

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

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

```

请注意，前面的习语返回`subList`中找到的元素的索引，而不是后缀`List`中的索引。

在`List`上运行的任何多态算法，例如`replace`和`shuffle`示例，都与`subList`返回的`List`一起使用。

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

```java
public 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`实现，例如`ArrayList`，从列表末尾删除元素的性能明显优于从头开始删除元素的性能。

以下是 [`a program`](examples/Deal.java) ，它将`dealHand`方法与`Collections.shuffle`结合使用，从正常的 52 张牌组中生成牌局。该程序采用两个命令行参数：（1）交易手数和（2）每手牌数。

```java
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<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]);

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

```

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

```java
% 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`的语义将变为未定义。因此，强烈建议您仅将`subList`返回的`List`用作瞬态对象 - 在后备`List`上执行一个或一系列范围操作。使用`subList`实例的时间越长，通过直接或通过另一个`subList`对象修改后备`List`来破坏它的可能性就越大。请注意，修改子列表的子列表并继续使用原始子列表（尽管不是并发）是合法的。

## 列表算法

`Collections`类中的大多数多态算法特别适用于`List`。拥有所有这些算法可以很容易地操作列表。以下是这些算法的小结，这些算法在[算法](../algorithms/index.html)部分中有更详细的描述。

*   `sort` - 使用合并排序算法对`List`进行排序，该算法提供快速，稳定的排序。 （*稳定排序*是不重新排序相同元素的排序。）
*   `shuffle` - 随机置换`List`中的元素。
*   `reverse` - 反转`List`中元素的顺序。
*   `rotate` - 将`List`中的所有元素旋转指定的距离。
*   `swap` - 交换`List`中指定位置的元素。
*   `replaceAll` - 将一个指定值的所有出现替换为另一个。
*   `fill` - 用指定的值覆盖`List`中的每个元素。
*   `copy` - 将源`List`复制到目标`List`。
*   `binarySearch` - 使用二进制搜索算法搜索有序`List`中的元素。
*   `indexOfSubList` - 返回一个`List`的第一个子列表的索引，该索引等于另一个。
*   `lastIndexOfSubList` - 返回一个`List`的最后一个子列表的索引，该索引等于另一个。