β

[集合框架] List 接口

Aptusource.orgAptusource.org 223 阅读

List 是有序的 Collection(有时也称为序列),List 中可以包含重复数据。List 中除了继承自 Collection 的方法外还额外添加了自己的方法。List 接口主要包含了以下操作:

Java 平台提供了两个 List 的实现:ArrayList,它是一个高性能的实现。LinkedList,在某些特殊情况下会有更高的性能。

集合操作

remove 方法总是会删除 list 中的第一个元素,add 和 addAll 方法总是在 list 的最后添加元素,因此,下面的方法是将一个 list 连接到另一个 list 后面:

list1.addAll(list2);

下面的版本不会破坏 list1 的数据,而是会新建一个 list 用于存储:

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

下面是 Java 8 中的例子,将 name 存储到 list 中:

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

List 改进了 equals 和 hashCode 方法,因此两个 List 之间可以进行比较,而不用考虑它们的具体实现。只要两个 List 中的元素和顺序一致,那么它们就相等(equal)。

位置访问和搜索

基本的位置访问方法是 get、set、 add 和 remove,set 和 remove 方法的返回值是被覆盖的和被删除的旧数据。indexOf 和 lastIndexOf 方法返回特定元素在 list 中的第一个和最后一个位置。

addAll 方法将在指定的位置插入 Collection 中的所有元素。元素插入的顺序由 Collection 返回的迭代器决定。

下面的方法演示了如何交换 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 中的数据,而不用考虑 List 的具体实现是什么。下面有另外一个多态算法使用了上面的方法:

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

上面这个算法已经包含在了 Collections 类中,这个方法将会使用随机生成器随机置换 list 中的元素。这个方法有点微妙,它从 list 最后位置开始,重复使用随机元素和当前元素交换。不像很多不成熟的随机实现,这个算法更加公平(所有元素的交换都是等效的,因为使用了公平的随机数生成器)和快速(一共只交换 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:

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 中的数据。List 还提供了一个功能更丰富的迭代器,叫做 ListIterator,它可以从两个方向进行数据迭代、在迭代的时候可以改变 List、获取当前迭代器的索引。

ListIterator 继承了 Iterator 的三个方法(hasNext、 next 和 remove),这三个方法的功能和 Iterator 一致。除此之外,ListIterator 还提供了 hasPrevious 和 previous 方法,这两个方法和 hasNext 和 next 方法类似,不过方向相反,hasPrevious 方法判断当前元素之前是否还有元素,previous 方法把当前游标向前移动一个元素。下面是使用这两个方法反向遍历 List 的例子:

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

注意上面例子中的 listIterator 方法,它可以不带参数,也可以带有一个参数。如果不带参数,那么返回的 ListIterator 将会指向 List 的最开始位置,如果带有参数,那么返回的 ListIterator 将会指向 List 中参数设置的位置。

当前索引指向的元素就是调用 next 方法返回的元素,调用 previous 方法返回的元素的索引是 index – 1。在一个长度是 n 的 list 中,一共有 n+1 个合法的索引,分别是从 0 到 n。

next 方法和 previous 方法可以混合使用。不过使用时要小心,第一次调用 previous 和最后一次调用 next 返回的是同一个元素。反之亦然。

调用 nextIndex 返回的索引指向的元素和调用 next 方法返回的元素相同,调用 previousIndex 返回的索引指向的元素和调用 previous 方法返回的元素相同。这些方法主要用于记录检索到的元素所在的索引位置。

nextIndex 返回的数字总是比 previousIndex 返回的数字大 1。这个潜在的行为有两个边界值:1)如果当前游标在 List 的最前面,调用 previousIndex 返回 -1;2)如果当前游标在 List 的最后,调用 nextIndex 返回 list.size()。总和以上,下面编写一个 List.indesOf 方法:

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

注意在代码中虽然使用了正向遍历,但是返回值却是 it.previousIndex()。这是因为 it.nextIndex 方法将会返回我们将要检查的元素,而我们希望得到的结果是我们刚刚检查过的元素索引。

Iterator 接口提供了 remove 方法用于删除最有一次 next 方法返回的元素。使用 ListIterator 接口,remove 方法可以删除最后一次 next 或 previous 返回的元素。ListIterator 中还提供了两个方法用于修改 List,这两个方法是 set 和 add。set 方法将会用指定的元素覆盖最后一次 next 或 previous 返回的元素。下面的方法演示了如何使用 newVal 替换 List 中的 val:

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

add 方法将会立即在当前游标之前插入一个新元素,下面的例子演示了如果 list 中出现了 val 元素,那么将会使用 newVals 中的元素来替换:

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) 方法将会返回 List 从 fromIndex(包括)到 toIndex(不包括)的元素。这个半开区间有点类似 for 循环:

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

List 调用 subList 方法返回的 subList 是 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。

下面使用 subList 来实现一个算法,从牌夹中取出一手牌,返回取得的这一手牌,并从牌夹中删除取出的牌:

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,
 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
    ace of hearts]

虽然 subList 很强大,但是使用的时候要小心。例如,如果使用 subList 返回了一个 List,然后又通过别的方法更改了原始 List 中的数据,之前返回的 subList 将变得没有意义。因此,建议使用 subList 返回的 List 对象只作为临时对象使用。注意,如果更改了 subList 的 subList,那么再继续使用第一个 subList 将是非法的。

List 算法

大多数 Collections 类中的算法也适用于 List,所有这些算法都帮助你更为简单地支配 List,下面简要看一下这些算法:

作者:Aptusource.orgAptusource.org
最好的 Java 技术博客
原文地址:[集合框架] List 接口, 感谢原作者分享。

发表评论