文档

Java™ 教程-Java Tutorials 中文版
接口
Collection 接口
Set 接口
List 接口
Queue 接口
Deque 接口
Map 接口
对象排序
SortedSet 接口
SortedMap 接口
接口总结
问题和练习
Trail: Collections
Lesson: Interfaces
« 上一页 • 路径 • 下一页 »

List 接口

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

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

集合操作

从 Collection 继承的操作都是关于你期望他们做的事情，假设你已经熟悉它们。如果你不熟悉 Collection，现在是阅读 The Collection Interface 部分的好时机。remove 操作始终从列表中移除 第一个 匹配项。add 和 addAll 操作始终将新元素附加到列表的 结尾。因此，以下习惯用法将一个列表连接到另一个列表。

list1.addAll(list2);

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

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

请注意，习惯用法以其非破坏性形式利用了 ArrayList 的标准转换构造函数。

这是一个将一些名字聚合到 List 的示例(JDK 8 及更高版本)： 

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 类中，使用指定的随机源随机置换指定的列表。它有点微妙：它从底部向上运行列表，反复地将随机选择的元素交换到当前位置。与大多数幼稚的洗牌尝试不同，它是 fair (公平的)(所有排列均以相同的可能性发生，假设无偏见的随机源)且 fast (快速的)(要求正好 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 的库版本(使用默认的随机源)，你将获得以下 tiny 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);
    }
}

迭代器

正如你所期望的那样，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 的列表中，有 n+1 个 index 的有效值，从 0 到 n，包括在内。

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

五个箭头代表五个光标位置，从 0 到 4，有四个元素，每个箭头之间有一个元素。

五个可能的光标位置。

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

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

同样，nextIndex 返回的数字总是比 previousIndex 返回的数字大一点也就不足为奇了。这意味着两种边界情况的行为：(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 之间的相等性测试。你需要小心特殊情况下 null 的 val 值以防止 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);
        }
    }
}

范围视图操作

range-view 操作，subList(int fromIndex, int toIndex)，返回此列表部分的 List 视图，其索引范围从 fromIndex(包括) 到 toIndex(不包含)。half-open range (半开范围) 反映了典型的 for 循环。

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

正如术语 view (视图) 所暗示的那样，subList 被调用返回的 List 是 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(“hand”)，它包含从指定的 List(“deck”)的末尾获取的指定数量的元素。手中返回的元素将从牌组中移除。

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("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 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 实例的时间越长，通过直接修改后备 List 或通过另一个 subList 对象来破坏它的可能性就越大。请注意，修改子列表的子列表并继续使用原始子列表(尽管不是并发)是合法的。

列表算法

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

« 上一页•路径•下一页 »
Previous page: The Set Interface
Next page: The Queue Interface