文档

Java™教程
隐藏目录
接口
集合接口
Set接口
列表接口
队列接口
双端队列接口
Map接口
对象排序
SortedSet接口
SortedMap接口
接口概述
问题和练习
指南：集合
课程：接口
« 上一页 • 指南 • 下一页 »

列表接口

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

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

集合操作

从Collection继承的操作都做了你期望它们做的事情，假设你已经熟悉这些操作。如果你对Collection中的操作不熟悉，现在是阅读集合接口部分的好时机。 remove操作总是从列表中删除指定元素的第一个出现。 add和addAll操作总是将新元素追加到列表的末尾。因此，以下习语将一个列表连接到另一个列表。

list1.addAll(list2);

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

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

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

这是一个示例（JDK 8及更高版本），它将一些名称聚合成一个List：

List<String> 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 <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方法的多态算法。

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<String> list = new ArrayList<String>();
        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<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将光标向前移动。

下面是通过列表向后迭代的标准惯用法。

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.

五个可能的光标位置。

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

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

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

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将所有出现的一个指定值替换为另一个值。

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为null的情况，以防止出现NullPointerException。

add方法将一个新元素插入到当前游标位置之前的列表中。下面的多态算法示例演示了如何将指定值的所有出现替换为指定列表中包含的值序列。

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

范围视图操作

subList(int fromIndex, int toIndex)方法返回一个此列表部分的视图，其索引范围从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中的索引。

任何作用于List的多态算法，例如replace和shuffle示例，都适用于subList返回的List。

下面是一个多态算法的示例，它使用subList从一副牌中发牌。也就是说，它返回一个新的List（称为“手牌”），其中包含从指定List（称为“牌堆”）末尾取出的指定数量的元素。返回的手牌中的元素从牌堆中移除。

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，从列表末尾移除元素的性能要比从列表开头移除元素好得多。

下面是一个使用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("用法：Deal hands cards");
            return;
        }
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);
    
        // 创建一副普通的52张牌的牌堆。
        String[] suit = new String[] {
            "黑桃", "红心", 
            "方块", "梅花" 
        };
        String[] rank = new String[] {
            "A", "2", "3", "4",
            "5", "6", "7", "8", "9", "10", 
            "J", "Q", "K" 
        };

        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);
    
        if (numHands * cardsPerHand > deck.size()) {
            System.out.println("牌不够了。");
            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 Deal 4 5

[红心8, 黑桃J, 黑桃3, 黑桃4,
    方块K]
[方块4, 梅花A, 梅花6, 红心J,
    红心Q]
[黑桃7, 黑桃5, 方块2, 方块Q,
    梅花9]
[黑桃8, 方块6, 黑桃A, 红心3,
    红心A]

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

List算法

Collections类中的大多数多态算法专门适用于List。拥有所有这些算法使得操作列表非常容易。以下是这些算法的概述，更详细的说明请参见算法部分。

« 上一节 • 目录 • 下一节 »
上一页: Set接口
下一页: Queue接口