Java 集合之 List

目录

1、集合操作

2、位置访问和搜索操作

3、迭代器

4、范围操作

5、List 算法

---

List是一个有序的集合，列表可能包含重复的元素。除了继承自Collection的操作外，List接口还包括以下操作：

• 根据位置操作——根据元素在列表中的下标位置操作元素。如 get、set、add、addAll和remove等方法。
• 搜索——在列表中搜索指定的对象并返回其数字位置。搜索方法包括 indexOf 和 lastIndexOf
• 迭代——利用列表的顺序特性，扩展了Iterator语义。listIterator方法提供了这种行为。
• 范围操作——从List中截取指定范围的子集

Java平台包含两个通用List实现，分别是 ArrayList（基于数组）和 LinkedList（基于链表） 。

1、集合操作

List 从Collection 继承的操作，其中删除操作总是从列表中删除指定元素的第一个匹配项。add和addAll操作总是将新元素追加到列表的末尾。

下边代码是将一个列表的全部数据放置到另一个列表中

list1.addAll(list2);

下边代码是一种非破坏性形式，它生成第三个List

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

下边代码是 JDK 8及以后版本的示例，它将一些名称聚合到一个List中:

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

与 Set 接口一样，List (AbstractList) 也重写了 equals 和 hashCode 方法，因此可以比较两个 List 对象是否相等，而不用考虑它们的实现类。如果两个 List 对象以相同的顺序包含相同的元素，则认为它们是相等的。

2、位置访问和搜索操作

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

addAll() 操作将从指定位置开始插入指定集合的所有元素。元素按指定集合的迭代器返回的顺序插入。addAll() 也属于位置访问操作，功能与 Collection 的 addAll 操作类似。

下边代码演示了在 List 中交换两个不同位置的元素的操作：

public static <E> void swap(List<E> a, int i, int j) {
        E tmp = a.get(i); // 获取i位置的元素赋值给临时变量tmp-中转站
        a.set(i, a.get(j));// 把j位置的元素放置到i位置
        a.set(j, tmp);// 把tmp放置到j位置
    }

下边代码交换任何List中的两个元素，不管它的实现类型是什么。代码中复用了上边的交换方法。

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

上边算法，使用指定的随机数据，随机排列指定的列表。它从列表底部向上运行，反复将随机选择的元素交换到当前位置。就像实际场景中的洗牌操作，只是该算法保证了牌序的公平性(如果保证有一个无偏倚的随机数来源，那么所有的排列都具有相同的可能性)。下面的程序使用这个算法以随机顺序打印参数列表中的单词。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
 
public class Shuffle {
    public static void main(String[] args) {
        args = "A B C D E F G".split(" ");
        // List<String> list = Arrays.asList(args);
        List<String> list = new ArrayList<String>();
        for (String a : args) {
            list.add(a);
        }
        Collections.shuffle(list, new Random());
        System.out.println(list);
    }
 
    public static <E> void swap(List<E> a, int i, int j) {
        E tmp = a.get(i); // 获取i位置的元素赋值给临时变量tmp-中转站
        a.set(i, a.get(j));// 把j位置的元素放置到i位置
        a.set(j, tmp);// 把tmp放置到j位置
    }
 
    public static void shuffle(List<?> list, Random rnd) {
        for (int i = list.size(); i > 1; i--) {
            swap(list, i - 1, i - 2); // 复用swap()
        }
    }
}

3、迭代器

List 的迭代器操作(Iterator)将按正确的顺序返回列表中的元素。同时，List 还提供了一个功能更丰富的迭代器 ListIterator，它允许你向任意方向遍历列表，同时在迭代期间修改列表，并获得迭代器的当前位置。

ListIterator 从 Iterator 中继承的三个方法 hasNext、next 和 remove 功能保持不变。其中 hasPrevious 和 previous 完全类似于 hasNext 和 next。previous 操作向后移动光标（倒序，3->2->1），next 操作向前移动光标（正序，1->2->3）。// 这个方向感是站在 List 角度而言的

下面是向后遍历列表的标准用法：

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

注意：List 接口有两种形式的 ListIterator 方法，没有参数的 List 返回一个位于列表开头的ListIterator；带 int 参数的表单返回位于指定索引位置的 ListIterator，对 next 的初始调用将返回指定位置的元素，对 previous 的初始调用将返回索引为 index-1 的元素。在长度为 n 的列表中，索引有 n+1 个有效值，从0到n(包括0)。

一般来说，游标总是在两个元素之间（调用 previous 返回的元素和调用 next 返回的元素），n+1个有效索引值对应元素之间的 n+1个间隙，从第一个元素之前的间隙到最后一个元素之后的间隙。下图显示了包含四个元素的列表中，有五个可能的光标位置。

对 next 和 previous 的调用可以混合使用，但是必须要格外的注意，比如，对 previous 的第一次调用与对 next 的最后一次调用将返回相同的元素。类似地，对 next 的第一次调用与对 previous 的最后一次调用将返回相同的元素。

有关迭代器的更多操作用例，请参考官方文档

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

4、范围操作

范围操作，subList(int fromIndex, int toIndex) 返回部分 List 视图，其索引范围从 fromIndex (包括)到 toIndex (排除)，属于半开范围。有点类似于以下的范围操作：

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

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 中的索引。

有关范围操作的更多用例，请参考官方文档

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

5、List 算法

Collections类中的大多数算法都专门应用于List。有了所有这些算法，操作列表就可以变得非常容易。以下是这些算法的总结：

• sort — 使用归并排序算法对 List 进行排序，该算法提供了快速、稳定的排序(稳定排序不会重新排序相等的元素)
• shuffle — 随机排列 List 中的元素
• reverse — 将 List 中元素的顺序颠倒
• rotate — 将 List 中的所有元素旋转指定距离
• swap — 交换 List 中指定位置的元素
• replaceAll — 用另一个指定值替换一个指定值的所有匹配元素
• fill — 用指定的值覆盖 List 中的每个元素
• copy — 将源 List 复制到目标列表中
• binarySearch — 使用二进制搜索算法搜索有序列表中的元素
• indexOfSubList — 返回 List 的第一个 sublist 的索引
• lastIndexOfSubList — 返回 List 中与另一个 List 相等的最后一个 sublist 的索引