第九十章 Java标准库－链表(List)

1 概述

链表(List)是最为常用的一种数据结构。链表是一种有序容器(Ordered Collection)，有时又被称为序列(sequence)。在链表中，元素之间首尾相连，组成了一条长长的元素链。为了向开发人员提供链表功能，Java标准库也提供了链表相关的接口和类。

java.util.List表示的是链表接口；它继承自java.util.Collection接口，所以List对象也是集合对象。List接口包含了所有链表操作的接口。

java.util.AbstractList是一个抽象的链表类。它提供了需要实现List接口的必要内容。如果开发人员需要实现一个随机访问的链表类的话，可以考虑继承自AbstractList类，因为它能帮助减少开发工作量。如果开发人员需要实现一个顺序访问的链表类的话，可以考虑继承自java.util.AbstractSequentialList类。AbstractSequentialList继承自AbstractList；在随机访问的基础上，AbstractSequentialList实现了顺序访问的一些必要功能。

Java标准库中包含的List相关类的结构如下图所示。

图一 List相关类结构图

2 链表的接口

2.1 添加元素

List接口提供了add()和addAll()接口，用于向链表添加新元素。add(index, element)方法可以将新元素放置在指定的位置。例如：

List<Integer> aListOfInteger = new LinkedList<Integer>();
aListOfInteger.add(1); // 在链表尾部添加新元素1
aListOfInteger.add(0, 2); // 在链表的第一个位置，即头部，添加新元素2
List<Integer> secondList = new LinkedList<Integer>();
secondList.addAll(aListOfInteger); // 将aListOfInteger中的元素添加入secondList

2.2 删除元素

remove()方法可以删除指定的元素或者删除指定位置的元素。clear()方法则删除链表中的所有元素。如果需要一次删除多个元素的话，可以使用removeAll()方法。

aListOfInteger.remove(0); // 删除链表中第一个元素
aListOfInteger.remove(Integer.valueOf(2)); // 删除链表中值为2的元素 
aListOfInteger.clear(); // 删除链表中所有的元素

2.3 链表长度

isEmpty()可以用于判断链表是否为空链表。size()方法返回链表中元素的个数。

List<Integer> aListOfInteger = new LinkedList<Integer>();
aListOfInteger.add(1); // 在链表尾部添加新元素1
aListOfInteger.add(2); // 在链表尾部添加新元素2
System.out.println(aListOfInteger.isEmpty()); // 打印false，当前链表不为空
System.out.println(aListOfInteger.size()); // 打印2，当前链表的元素个数

2.4 访问链表的元素

get()方法允许开发人员根据元素所在位置获取元素。iterator()方法返回一个Iterator对象，提供依次访问链表元素的接口。

System.out.println(aListOfInteger.get(0)); // 打印链表中第一个元素

// 打印链表中每一个元素
Iterator<Integer> it = aListOfInteger.iterator(); 
while (it.hasNext()) {
    System.out.println(it.next());
}

listIterator()方法也提供了类似的功能。只不过，listIterator()方法可以接受一个参数，指定迭代器的起始位置。

// 从第二个元素开始遍历链表
ListIterator<Integer> it = aListOfInteger.listIterator(1);
while (it.hasNext()) {
    System.out.println(it.next());
}

2.5 查找元素

contains()和containsAll()方法在链表对象中查找一个或者多个元素。这两个方法仅返回容器是否包含给定的元素。如果需要查找并获取元素时，可使用indexOf()和lastIndexOf()方法。indexOf()方法从前向后查找给定的元素；lastIndexOf()方法从后向前查找指定的元素。这两个方法的返回值表示的是查找元素在链表中的位置。如果链表中不包含该元素的话，则返回-1。

List<Integer> aListOfInteger = new LinkedList<Integer>();
aListOfInteger.add(1); // 在链表尾部添加新元素1
aListOfInteger.add(2); // 在链表尾部添加新元素2

System.out.println(aListOfInteger.contains(1)); // 返回true，因为链表包含元素1
System.out.println(aListOfInteger.indexOf(1)); // 返回0，因为元素1所在的位置是0

2.6 创建不可变更的链表

List接口还提供了多个of()静态方法，用于创建不可变更的链表对象。例如，如下的代码示例创建了包含一个元素和两个元素的链表对象。

List<Integer> list1 = List.of(1);
List<Integer> list2 = List.of(1, 2);

2.7 链表比较

List接口覆盖了equals()方法，定义了链表比较的逻辑。只有当两个链表包含相同个数的元素，并且在相同位置处的两个元素"相同"时，List类的equals()方法才返回true；否则返回false。两个元素相同是指在这两个元素上调用Objects.equals()方法的结果为true。

List<Integer> list1 = List.of(1, 2);
List<Integer> list2 = List.of(1, 2);
System.out.println(list1.equals(list2)); // 打印true

2.8 其他

sort()方法能够将链表中的元素按照指定的顺序排序。List类的sort()方法的功能与java.util.Collections类的sort()方法的功能类似。

subList()方法可以从一个链表对象中创建出一个子链表。第一个参数和第二个参数设置了一个起始位置和终止位置。在这个区间内的元素将包含在子链表中(在终止位置的元素不包含在子链表中)。

toArray()方法可将链表的所有元素按照顺序导入到一个数组对象中。

List<Integer> aListOfInteger = new LinkedList<Integer>();
aListOfInteger.add(2); // 在链表尾部添加新元素2
aListOfInteger.add(1); // 在链表尾部添加新元素1
aListOfInteger.sort(); // 排序

List<Integer> subList = aListOfInteger.subList(0, 1);
Integer[] anArray = subList.toArray(Integer[]::new);

2.9 java.util.Collections中的链表方法

java.util.Collections类中也提供了一些链表的操作方法。rotate()方法可以循环移动链表中的元素。如果把链表首尾相连的话，rotate()方法能将链表中的元素向尾部平移。例如，当链表的元素为[1, 2, 3]时，在调用rotate(list, 1)之后，链表的元素会变为[3, 1, 2]。平移的距离也可以是负数。当平移距离是负数时，则向链首平移。例如，当链表为[1, 2, 3]时，在调用rotate(list, -1)之后，链表变为[2, 3, 1]。

Collections.swap()方法可以用于交换链表中的两个元素。例如，下面的代码交换链表的第一个和第二个元素。

List<Integer> aList = ...;
Collections.swap(aList, 0, 1);

Collections.shuffle()方法能够随机打乱链表中元素的次序。在使用完shuffle()方法之后，各种元素的排列的概率基本相同。

Collections.replaceAll()方法可将链表中给定值替换为另一个值。例如，下面的代码将链表中值为1的元素替换为值为2的元素。

List<Integer> aList = ...;
Collections.replaceAll(aList, 1, 2);

Collections.copy()方法将源链表中的元素拷贝到目标链表之中。目标链表的长度不能短于源链表。目标链表中超出源链表长度部分的元素保持不变。

我们将在下面介绍了两个链表实现ArrayList和LinkedList都不提供并发保护。如果希望将ArrayList或者LinkedList对象加上并发保护的话，可以使用Collections.synchronizedList()方法。

List<Integer> syncrhonizedArrayList = Collections.synchronizedList(new ArrayList<Integer>());
List<Integer> syncrhonizedLinkedList = Collections.synchronizedList(new LinkedList<Integer>());

3 链表的实现

Java标准库中提供了多种链表的实现。其中，ArrayList和LinkedList是最为常见的两种。我们将在本小节中介绍它们的实现细节。

3.1 java.util.ArrayList

ArrayList类使用了数组(Array)来实现链表。链表中的所有元素保存在一个数组中。当数组被填满时，这个数组能够自动増长。因为所有的元素都是存放在数组中的，所以，方法size()、isEmpty()、get()、set()、iterator()都可以在常量时间内完成。

我们再来看看OpenJDK 15如何实现ArrayList。ArrayList类放置在java.util包中。它包含了两个重要的成员变量。elementData是保存元素的数组；size表示当前链表包含的元素个数。因此，size()方法和isEmpty()方法可以直接使用成员变量size。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...

    transient Object[] elementData;

    private int size;

    ...

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    ...
}

图二 ArrayList内部结构图

因为所有的元素都包含在数组之中，所以get()和set()方法直接使用了数组的访问方法。checkIndex()方法检查参数index是否越界。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    E elementData(int index) {
        return (E) elementData[index];
    }

    public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    ...
}

当添加新元素时，首先判断数组elementData是否已填满。如果未填满，则直接放置在数组中。如果已填满，则申请一个更大的数组空间，将已有的元素全部拷贝到新的数组中，然后再填入新元素。在grow()方法中，ArrayList类创建了一个更大的数组，并使用了Arrays.copyOf()方法来将元素拷贝到新数组中。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,　newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
    ...
}

所以，当移除元素时，ArrayList也需要向前平移删除位置之后的元素。元素平移是调用System.arraycopy()方法完成的。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }
    ...
}

在查找元素时，沿着数组从前向后或者从后向前逐个比较，完成查找。

// OpenJDK 15
package java.util;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
    ...
}

另一个使用数组来实现链表接口的类是java.util.Vector。Vector的实现方式与ArrayList非常相似。但是Vector有着两个显著的区别。第一，开发人员可以为Vector设置自动增长的步长。步长保存在成员变量capacityIncrement中。第二，Vector为每个方法增加了并发保护。每个方法都被保护在synchronized之中。我们仅在下面列出Vector实现的不同之处。有兴趣的读者可以自行查看其实现的代码。

// OpenJDK 15
package java.util;


public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;

    protected int elementCount;

    protected int capacityIncrement;

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public synchronized int size() {
        return elementCount;
    }

    public synchronized boolean add(E e) {
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }

    public boolean remove(Object o) {
        return removeElement(o);
    }

    public synchronized void removeElementAt(int index) {
        ...
    }
}

3.2 java.util.LinkedList

LinkedList是一个双向链表的实现。在LinkedList链表中，元素存放在节点上，节点之间首尾相连，形成链表。当需要使用索引来操作链表时，首先需要从表头或者表尾开始遍历链表，查找到索引指向的位置，然后再处理相应的操作。

在OpenJDK 15中，LinkedList类放置在java.util包中。LinkedList类包含了三个重要的成员变量；size表示链表的长度；first和last分别表示链表的头节点和尾节点。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;
    ...
}

图三 LinkedList内部结构图

每个节点是一个Node对象。Node是LinkedList类的内部类。Node类由三个成员组成，分别为item、next和prev。它们分别表示链表中的元素和指向前驱、后继节点的引用。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    ...
}

因为LinkedList类的first和last分别指向链首和链尾，所以，它能直接返回第一个元素和最后一个元素。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    ...
}

当从链首插入新元素时，新节点的next指向当前的链首，并且将first指向新节点。然后再更新链尾。我们省略了从链尾插入新元素的代码，读者如果感兴趣的话，可自行查看。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    public void addFirst(E e) {
        linkFirst(e);
    }
    ...
}

当从链首删除元素时，首先将first指向第一个元素的next指向的元素，然后更新成员变量last。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    ...
}

当查找元素时，indexOf()方法从链首开始遍历链表，直到到达链尾或者找到目标元素。lastIndexOf()方法则从链尾开始向前查找。我们在这里省略了lastIndexOf()方法的实现。

// OpenJDK 15
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
    ...
}

4 小结

本章介绍了Java标准库中的链表的接口与两个最常用的实现。ArrayList使用数组来实现链表；而LinkedList则是一个双向链表的实现。ArrayList的特点是空间使用率较高，每个元素紧紧的排列在一起，遍历每个元素的速度较快。但是，当需要动态增长时，ArrayList需要复制所有的元素到新的数组中。LinkedList的动态性更好。从链首或者链尾删除元素较快。但是，当遍历链表时，LinkedList只能沿着每个节点，一步一步的前进。Vector与ArrayList非常相似。Vector为开发人员提供了灵活的动态增长步长和并发保护。