第十三章《集合》第2节：List集合

List这个单词意为“列表”，List类型的集合的特点是：元素呈线性排列，致密且有序。下面的图13-3展示了List类型集合的特点。

图13-3 List类型集合

图13-3中的每一个小圆形代表一个元素，可以看到，这些元素被放到List集合中后被排成一列，这就是“线性排列”。List集合中的元素都是连续的，中间不会空隙，这个特点可以概括为“致密”。List集合中每个元素都有自己的索引，因此它们有先后顺序，这个特点可以概括为“有序”。元素的索引就是元素的下标，程序员可以通过指定索引来找到List集合中的任意元素。

List是Collection的子接口，因此它继承了Collection接口的全部方法。Collection所定义的方法如表13-1所示。

表13-1 Collection接口的方法

List在继承了Collection方法的基础上，又扩展出很多通过索引操作元素的方法，下面的表13-2展示了List接口所定义的方法。

表13-2 List接口的方法

13.2.1 ArrayList类和Vector类

ArrayList类和Vector类是List接口最典型的两个实现类，它们都具有Collection接口和List接口所定义的方法。ArrayList和Vector这两个类的实现原理相似，它们的内部都封装了一个动态的、允许再分配的Object数组。当向ArrayList或Vector中添加的元素个数超出了该数组的长度时，数组会被重新分配空间，以存放更多的元素，因此读者也可以理解为ArrayList和Vector中的数组会自动增加。ArrayList和Vector在创建对象时，可以通过参数指定数组的初始长度，例如下面的语句在创建对象时设置数组长度为20。

ArrayList list = new ArrayList(20);

如果没有指定数组的长度，虚拟机会在对象内部创建长度为10的数组。

程序中对集合的操作一般包括：向集合中加入元素，获取集合中的某个元素、用一个对象取代集合中的某个元素、移除集合中的某个元素、清空集合等。下面的【例13_01】展示了ArrayList对元素的各种操作。

【例13_01 List集合对元素的常用操作】

Exam13_01.java

import java.util.ArrayList;
public class Exam13_01 {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        //向集合中加入5个元素1、2、3、4、5
        for(int i=1;i<=5;i++){
            list.add(i);//①
        }
        System.out.println("加入5个元素后的集合："+list);
        //在索引为2的位置插入元素6
        list.add(2,6);//②
        System.out.println("在索引2处插入元素6之后的集合："+list);
        //移除集合中的元素3
        list.remove(Integer.valueOf(3));//③
        System.out.println("移除元素3之后的集合："+list);
        //用元素8取代索引为1的元素
        list.set(1,8);
        System.out.println("用元素8取代索引为1处元素后的集合："+list);
        //取出索引为3的元素
        Object element = list.get(3);//④
        System.out.println("索引为3的元素是："+element);
        //清空集合
        list.clear();
        System.out.println("清空后的集合："+list);
    }
}

集合中只能加入对象而不能加入基础类型数据，本例中直接向ArrayList中加入1、2、3、4、5并没有出现任何问题，是因为包装类具有自动装箱功能，因此实际上加入集合的是5个Integer类的对象。语句①中add()方法把元素加入集合，由于没有指定元素在集合中的位置，因此元素会被加入到集合的末尾，而语句②中的add()方法指定了元素在集合中的位置，因此元素会被加入到集合的特定位置，这个元素进入集合后，由于它占据了某个特定位置，原来该位置上的元素就会向后移动，因此这个操作实际上应该被称为“插入”。需要注意，插入元素的索引值不能超过集合的长度，例如集合中只有5个元素，就不能把新元素插入到集合索引为10的位置。语句③的作用是移除集合中的元素3，可以看到，在调用remove()方法时，为方法传递的参数是一个Integer对象而不是整数3，这是因为remove()方法有两个版本，一个版本用参数指定移除的对象，另一个版本用参数指定移除元素的索引，因此如果语句③在调用remove()方法时传递的参数是3，那么就表示移除索引为3的元素。语句④通过get()方法获得了一个特定索引的元素，集合中的元素本来是Integer，但语句中却用Object类的引用指向了所获取的元素，这是因为集合在存入元素时会丢失元素的类型，因此使用get()方法获取的元素都被看作Object类的对象。如果希望集合能够记住元素的真实类型，可以在创建集合对象时指定集合的泛型，例如：

ArrayList<Integer> list = new ArrayList<Integer>();

以上语句中所创建的ArrayList对象只能存放Integer类的对象，并且使用get()方法获取到的元素也会被虚拟机直接看作Integer类而不是Object类。【例13_01】虽然使用ArrayList对象为例进行演示，实际上如果把程序中的ArrayList替换为Vector，程序也不会出现语法问题并且会有相同的执行效果。【例13_01】的运行结果如图13-4所示。

图13-4【例13_01】运行结果

程序中除对集合的元素进行各种操作之外，往往还会对集合做各种判断，这些判断包括：计算集合中元素的数量、判断集合是否为空集合、判断集合中是否含有某个对象、当前集合与其他集合是否有共同元素等。下面的【例13_02】展示了如何对List类型集合进行各种判断。

【例13_02 判断List集合特性】

Exam13_02.java

import java.util.ArrayList;
public class Exam13_02 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        System.out.println("list1是否是空集合："+list1.isEmpty());
        System.out.println("list1中的元素数量："+list1.size());
        System.out.println("list1中是否包含元素2："+list1.contains(2));
        //向list1中加入1、2、3、4、5
        for(int i=1;i<=5;i++){
            list1.add(i);
        }
        System.out.println("向list1加入5个元素后：");
        System.out.println("list1是否是空集合："+list1.isEmpty());
        System.out.println("list1中的元素数量："+list1.size());
        System.out.println("list1中是否包含元素2："+list1.contains(2));
        //向list2中加入2、4、6、8、10
        for(int i=1;i<=5;i++){
            list2.add(i*2);
        }
        System.out.print("使用增强型for循环遍历list2：[");
        for (Integer i:list2){
            System.out.print(i+" ");
        }
        System.out.println("]");//打印右中括号并换行
        System.out.println("list1与list2是否有共同元素："+list1.retainAll(list2));
        System.out.println("两个集合的共同元素是："+list1);
    }
}

【例13_02】的运行结果如图13-5所示。

图13-5【例13_02】运行结果

从图13-5可以看出：增强型for循环不仅仅能够遍历数组，还能够遍历List类型的集合，此外还可以看到，调用list1的retainAll()方法后，list1会去掉list2所没有的那些元素，值保留两个集合的共同元素。

【例13_02】的代码中，如果把ArrayList替换为Vector也会运行出同样的效果。Vector和ArrayList如此相像，它们之间又有什么区别呢？Vector是一个古老的集合，它从JDK 1.0就已经被定义，那时候Java还没有提供系统的集合框架。Vector中定义了一些名称很长的方法，例如addElement()，实际上这个方法与add ()方法没有任何区别。从JDK 1.2以后，Java提供了系统的集合框架，就将Vector改为实现List接口，成为了List接口的实现类之一，这导致 Vector里有一些功能重复的方法。Vector类的各种方法中，方法名更短的方法属于List接口中定义的方法，方法名更长的方法则是Vector原有的方法。

ArrayList一开始就作为List的主要实现类，因此没有那些方法名很长的方法。除此之外，ArrayList和Vector的显著区别是：ArrayList 是线程不安全的，当多个线程访问同一个ArrayList集合时，如果有超过一个线程修改了ArrayList集合，则程序必须手动保证该集合的同步性。但Vector集合则是线程安全的，无须程序保证该集合的同步性。因为Vector是线程安全的，所以Vector的性能比ArrayList 的性能要低。实际上，即使需要保证List集合线程安全，也同样不推荐使用Vector实现类。后面会介绍一个Collections工具类，它可以将一个ArrayList对象变成线程安全的。

13.2.2 LinkedList类

ArrayList和Vector的内部都有一个数组，元素就存储在数组中。把元素存储在数组中最大的优势就是能够实现随机访问，也就是说只要指出元素的索引，虚拟机就能够一次性计算出元素的内存地址并对其进行访问。但如果删除或插入一个元素，基于数组的集合在性能方面就没有优势了，这是因为每当删除集合中的一个元素后，这个元素后面的其他元素都要逐个向前“移动”，以填补它所留下的空缺，这就有可能出现删除一个元素，却导致一万个元素移动的情况。插入元素也会导致相同的情况发生，只是其他元素变成了向后移动。

除了基于数组的集合，Java语言还提供了一种基于链表的集合。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，如图13-6所示。

图13-6链表示意图

从图13-6可以看出：链表由一系列结点组成，每个结点包括两个部分：一部分是存储数据元素的数据域，另一部分是存储下其他结点地址的指针域。指针域中存储某个节点的地址这个行为常被表述为“指针指向某节点”。链表可以分为两种：如果一个节点只有一个指针，并且指针只是指向了下一个节点，那么这种链表称为“单链表”，而如果节点有两个指针，它们分别指向上一节点和下一节点，那么这种链表就称为“双链表”。从链表的结构可以看出：只有找到某个节点才能找到它的下一节点，因此链表结构并不具备“随机访问”的特性。但链表却能够很容易的实现节点的插入和删除的操作，因为每次插入或删除一个节点时，只需要改变某个节点指针的指向就可以。

Java语言也提供了表示链表的类，这个类就是LinkedList，更进一步说LinkedList实现的是一个双向链表。LinkedList定义了很多用于操作双向链表的方法，下面的表13-3展示了LinkedList所定义的方法，这些方法中并不包括List接口中所定义的那些方法。

表13-3 LinkedList类的方法

从表13-3可以看出：LinkedList类中有很多功能重复的方法，这是因为LinkedList实现了Iterable、Collection、Deque、List、Queue等多个接口，这些接口中的方法存在重复现象，而LinkedList继承了这些方法从而导致自身的方法出现大量重复。虽然LinkedList类中所定义的方法很多，但这些方法并不难理解。

关于LinkedList有一个很典型的例子：猴子选大王，题目是：有100只猴子围成一圈，按顺序每只猴子从1到100编号，并打算从中选出一个大王。经过协商，决定出选大王的规则是：从第一个开始循环报数，数到14的猴子出圈，最后剩下来的就是大王。实现这个计算的思路很简单，用一个LinkedList对象存放1~100的整数，用int型变量count表示猴子报的数，用pointer表示元素的索引，然后开始模拟报数的过程，如果没有报到14，count和pointer的值都自增，表示轮到下一只猴子报数。每次报到14时，移除索引为pointer的元素，由于这个元素被移除，pointer不需要自增即可表示下一个元素的索引，而count的值恢复为1，表示下一只猴子报的数重新回到1。需要注意：pointer的值在与链表长度相等时要重置为0，这样表示重新回到链表头部。实际上这个问题也可以用ArrayList解决，但由于LinkedList在删除元素时速度更快，因此使用LinkedList完成操作性能更好。下面的【例13_03】展示了如何使用LinkedList解决猴子选大王的问题。

【例13_03 猴子选大王】

Exam13_03.java

import java.util.LinkedList;
public class Exam13_03 {
    public static void main(String[] args) {
        LinkedList<Integer> monkeys = new LinkedList<Integer>();
        for (int i = 1; i <= 100; i++) {
            monkeys.add(i);
        }
        int count = 1;//猴子报的数
        int pointer = 0;  //pointer的值就是当前被判断元素的索引
        while (monkeys.size() > 1) {
            if (count == 14) {
                count = 1;
                //移除该元素，由于它被移除，pointer不需要自增即可表示下一元素的索引
                monkeys.remove(pointer);
            }else{
                count++;
                pointer++;
            }
            if (pointer ==monkeys.size()) {//达到尾部，重新返回初始指针处
                pointer = 0;
            }
        }
        System.out.println("大王的编号是："+monkeys.get(0));
    }
}

【例13_03】的运行结果如图13-7所示。

图13-7【例13_03】运行结果

13.2.3长度固定的List

第11章中讲解过一个操作数组的工具类:Arrays，这个类里提供了asList()方法，该方法可以把一个数组或指定个数的对象转换成一个List集合，这个 List集合的类型既不是ArrayList，也不是Vector，而是Arrays.ArrayList，也就是说它的类型是Arrays的内部类ArrayList。

Arrays.ArrayList是一个固定长度的List集合，因此只能遍历访问该集合里的元素，不可增加、删除该集合中的元素。任何试图增加或删除该集合元素的操作都会导致程序出现异常。下面的【例13_04】展示了如何获得长度固定的List集合，并通过forEach()方法遍历集合。

【例13_04长度固定的List】

Exam13_04.java

import java.util.*;
public class Exam13_04 {
    public static void main(String[] args) {
        List list = Arrays.asList("Java ","Python ","C++ ");
        //获得list的真实类型
        System.out.println("list的真实类型："+list.getClass().getName());
        System.out.print("中的所有元素list：");
        //调用forEach()方法遍历list
        list.forEach(System.out::print);
    }
}

【例13_04】通过asList()方法获得了一个长度固定的List对象，并通过getClass()方法获得对象的真实类型，紧接着调用forEach()方法遍历集合。forEach()方法是Iterable接口中定义的一个方法，因为List接口是间接Iterable子接口，因此所有List类型的集合都拥有forEach()方法。forEach()方法用来遍历集合，方法的参数类型Consumer，Consumer是一个接口，其中定义的accept()抽象方法用来表示如何访问集合元素。由于Consumer是一个函数式接口，因此本例中采用Lambda表达式表示其匿名实现类对象。【例13_04】的运行结果如图13-8所示。

图13-8【例13_04】运行结果