Java 集合框架中的 List

List

本文代码基于 openJDK 18

List 接口承继自 Collection ， 除了承继了 Collection 中的才能，自身拓宽了几个默许办法：

// 批量修正操作
default void replaceAll(UnaryOperator<E> operator) 
// 排序，运用的是 Arrays.sort 
default void sort(Comparator<? super E> c) 
​
// 方位拜访操作
E get(int index);
E set(int index, E element);
void add(int index, E element); // Collection 有 add ，这儿拓宽了指定 index 。
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
​
// 迭代器
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
​
// 容器
List<E> subList(int fromIndex, int toIndex);

这儿简略介绍一下，List 相较于 Collection 拓宽的功用：

• 批量操作增加排序，阐明 List 是有序的。
• 方位拜访操作，阐明 List 是能够进行方位索引的。
• 容器支撑了子 List，能够对 List 进行截取。

List 接口的直接完成包含：ArrayList、Vector、LinkedList、CopyOnWriteArrayList。

ArrayList

ArrayList 是一个动态数组，支撑随机拜访。答应存储包含 null 的元素。内部的数据结构是数组。除了完成 List 接口外，还供给了一些办法用来处理数组扩容的办法。

它与 Vector 的差异在于，Vector 是同步的，所有操作办法都加了 synchronized 修饰。而 ArrayList 没有。

承继联系

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

内部数据结构

transient Object[] elementData; 
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
​
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
​
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
   } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
   } else {
    throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
   }
}

初始化时，依据 initialCapacity 参数创立大小，默许容量时 0 。

真正保存数据的是 elementData ，这是一个目标数组。

增加数据是顺序的在数组尾部增加新元素，当向容器中增加元素时，假如容量不足，容器会主动增大底层数组的大小。

扩容逻辑

扩容来源于增加操作：

// 刺进式的增加
public void add(int index, E element) {
    rangeCheckForAdd(index); // 确保 index 在 0 到 size 范围内
    modCount++; // 增加操作计数
  final int s; // 数组当时容量
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow(); // 扩容
    System.arraycopy(elementData, index,
           elementData, index + 1,
           s - index); // 仿制数组
    elementData[index] = element;
    size = s + 1;
}
​
// 一般的增加方式，增加到数组尾部
public boolean add(E e) {
    modCount++; // 操作次数增加
    add(e, elementData, size);
    return true;
}
​
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

扩容逻辑在 grow() 中：

private Object[] grow() {
  return grow(size + 1);
}
​
private Object[] grow(int minCapacity) {
  int oldCapacity = elementData.length; // 本来的容量
    // 本来容量大于 0，或数组不是默许数组时，核算新的容量
  if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    int newCapacity = ArraysSupport.newLength(oldCapacity,
        minCapacity - oldCapacity, /* 最小容量 */
        oldCapacity >> 1      /* preferred growth */);
      // 回来仿制好的数组
    return elementData = Arrays.copyOf(elementData, newCapacity);
   } else {
      // 默许结构办法的状况，回来一个默许容量为 10 的数组
    return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
   }
}

扩容逻辑是，假如是默许结构参数，即 ArrayList() 创立的目标，默许数组容量为 DEFAULT_CAPACITY ，值为 10；

假如本来的数组容量大于 0，经过 ArraysSupport.newLength(oldLength, minGrowth, prefGrowth) 来核算新的容量。

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
  int prefLength = oldLength + Math.max(minGrowth, prefGrowth);
  return 0 < prefLength && prefLength <= 2147483639 ? prefLength : hugeLength(oldLength, minGrowth);
}

该办法三个参数分别是：

0. oldLength：原始数组的长度，即当时数组的长度。
1. minGrowth：最小增加值，表明数组的最小增加空间。假如数组需求扩容，至少会增加 minGrowth 个空间。
2. prefGrowth：优先增加值，表明数组的优先增加空间。数组需求扩容时，会优先增加 prefGrowth 个空间。

首要，经过 prefLength = oldLength + Math.max(minGrowth, prefGrowth); 核算得到一个或许的新长度 prefLength，其间取 minGrowth 和 prefGrowth 的较大值，以确保新长度至少增加 minGrowth 个空间。

这儿的扩容核算为，新容量 = 原始容量 + 最小增加量和原始容量的一半两者的取较大一方的值，一般状况下是 1.5 倍原容量扩容。

接下来，判别 prefLength 是否在一定范围内。查看新长度是否大于 0 且小于等于 Integer.MAX_VALUE。

假如新长度满意上述条件，则回来 prefLength 作为新的数组长度。否则，调用 hugeLength(oldLength, minGrowth) 办法，该办法将回来一个巨大的容量数（2147483639），假如最小容量仍大于这个数，则回来最大数量，别的便是对 minLength 为负数的状况做了约束。

private static int hugeLength(int oldLength, int minGrowth) {
  int minLength = oldLength + minGrowth;
  if (minLength < 0) {
    throw new OutOfMemoryError("Required array length " + oldLength + " + " + minGrowth + " is too large");
   } else {
    return minLength <= 2147483639 ? 2147483639 : minLength;
   }
}

手动节省容量

ArrayList 还对外供给了一个节省内存空间的主动调整容量办法，但 ArrayLsit 内部并没有自己调用：

public void trimToSize() {
  modCount++;
  if (size < elementData.length) {
    elementData = (size == 0)
     ? EMPTY_ELEMENTDATA
      : Arrays.copyOf(elementData, size);
   }
}

该办法将此 ArrayLis t实例的容量修剪为列表的当时大小。

Fail-Fast机制

ArrayList 也采用了快速失利的机制，经过记载 modCount 参数来完成。在面对并发的修正时，迭代器很快就会彻底失利，而不是冒着在将来某个不确定时刻产生任意不确定行为的风险。Fast-Fail 机制本身并不能确保线程安全。

Vector

承继联系

与 ArrayList 彻底共同：

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

内部数据结构

protected Object[] elementData;
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 Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
public Vector() {
    this(10);
}

内部数据结构与 ArrayList 相同，默许结构办法设置的容量也是 10。

扩容逻辑

也是从 add 操作入手：

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    elementCount = s + 1;
}

同样来自于 grow 系列办法：

private Object[] grow() {
    return grow(elementCount + 1);
}
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                       /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容逻辑与 ArrayList 基本共同，但引荐扩容为 capacityIncrement， capacityIncrement 在结构办法中能够设置：

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

默许是 0，也便是说默许状况下，扩容是原容量 2 倍扩容（ArrayList 是 1.5 倍）。

与 ArrayList 的差异

最大的差异是 Vector 的操作都加上了 synchronized 关键字：

public synchronized boolean add(E e)
public synchronized E get(int index)
public synchronized E set(int index, E element)

所以 Vector 是线程安全的，而 ArrayList 无法确保线程安全。

另一个差异便是默许扩容量不同：Vector 默许是 2 倍，ArrayList 默许是 1.5 倍。

Stack

Vector 有一个子类 Stack，也便是栈结构类型。表明目标的后进先出仓库。Stack 承继自 Vector ，并拓宽了五个答应将容器视为栈结构的操作。 包含常见的 pop 和 push 操作、以及查看栈顶元素的办法、查看栈是否为空的办法以及从栈顶向下进行搜索某个元素，并获取该元素在栈内深度的办法。

但 JDK 更引荐运用 Deque 来完成栈才能。Deque 接口及其完成供给了一组更完好的 LIFO 仓库操作才能，应该优先考虑运用 Deque 及其完成。例如：

Deque<Integer> stack = new ArrayDeque<Integer>();

LinkedList

基于双向链表完成，只能顺序拜访，但是能够快速地在链表中心刺进和删去元素。不仅如此，LinkedList 还能够用作栈、队列和双向队列。

承继联系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• AbstractSequentialList 是 List 接口的骨架完成（Skeletal Implementation），它供给了一种最小化完成 List 接口所需的努力，能够用作”顺序拜访”数据存储（如链表）的后备支撑。关于随机拜访数据（如数组），应该优先运用 AbstractList 而不是这个类。
• Deque：双向队列，支撑从两头对元素进行刺进和移除，后续在 Queue 接口系统详细阐明。
• Cloneable：目标仿制。
• Serializable：序列化才能。

内部数据结构

transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

经过 first 和 last 表明双向链表的两个方向的头节点。Node 的数据结构是：

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

增加操作

有两种增加方式，一种是增加到链表尾部，另一种是增加到指定方位

public boolean add(E e) {
    linkLast(e);
    return true;
}
// 将指定的元素刺进到列表的指定方位。将当时该方位上的元素（假如有的话）和任何后续的元素都向右移动（索引加一）。
public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

linkLast

这儿用到了 linkLast 办法将元素增加到链表尾部：

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

linkBefore

刺进到指定方位的增加操作：

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

这段代码用于在一个链表中的指定节点 succ 之前刺进一个新的节点，新节点的元素值为 e。它会创立一个新的节点 newNode，然后将 newNode 刺进到 pred 和 succ 之间，修正它们之间的链接联系，使得新节点成为 pred 的后继节点，同时也成为 succ 的前驱节点。

在刺进新节点后，还会更新列表的大小 size 和修正计数器 modCount，以确保列表的状况正确并支撑快速失利机制。

这儿的 succ 参数经过 node(int index) 而来：

// in add()
linkBefore(element, node(index));

查询操作

node 办法中，依据 index 判别是在链表的前半部分仍是后半部分，然后在从链表头部或尾部去遍历，进步功率：

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

所以链表操作的时刻复杂度基本上便是这个办法的时刻复杂度 O(size >> 1) 。

删去操作

LinkedList 的 remove 操作有很多，关于链表头部和尾部的删去是 removeFirst 和 removeLast：

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

来自 Deque 的 remove 办法完成：

public E remove() {
    return removeFirst();
}

依据 index 删去的办法：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

依据目标删去的办法：

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

这些删去办法，都有关于链表的操作办法。

删去链表尾部

    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

删去链表头部

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

删去链表中的指定元素

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

线程安全

LinkedList 的所有操作都没有线程安全相关的逻辑，所以也是无法确保线程安全的。但 LinkedList 的操作类办法都有 modCount 计数，支撑 Fast-Fail ，确保并发操作时防止对不共同的数据进行操作。

Java的快速失利（fast-fail）机制是一种在调集类上用于检测并发修正的机制。

快速失利机制的完成是经过在每次对调集进行迭代或修正操作时，都会查看调集的修正次数（modCount）。调集的 modCount 是一个计数器，用于记载对调集进行修正的次数。当一个迭代器或者一个线程开端遍历调集时，会记载当时调集的 modCount 值。当接下来产生调集的修正（增加、删去等）时，modCount 值会增加。假如在迭代或拜访过程中，发现调集的 modCount 值与记载的 modCount 值不共同，就会抛出 ConcurrentModificationException 反常，以提醒程序有并发修正操作产生，进而防止对不共同的数据持续操作。

CopyOnWriteArrayList

CopyOnWriteArrayList 并不是 Java 调集结构中的成员，而是来自于 java.util.concurrent 结构，即 Java 并发结构，所以自然具有确保线程安全的才能。

承继联系

线程安全

/** 保护所有变量的锁 */
final transient Object lock = new Object();
/** 内部的数据结构，只能经过getArray/setArray拜访。 */
private transient volatile Object[] array;

经过 lock 目标合作 synchronized 来供给加锁才能；经过 transient 确保数据不会被序列化；经过 volatile 关键字确保写操作会立即同步到主内存，确保多线程的可见性。别的便是禁止指令重排序。

这儿运用 lock 目标合作 synchronized 关键字而不是 ReentrantLock ，是由于这儿保护所有可变操作的锁。（在两者都能够运用时，咱们稍微倾向于运用内置监视器而不是ReentrantLock。）

早些版本的 JDK 是 ReentrantLock ，openJDK 18 运用 lock 目标合作 synchronized。

将 array 声明为 volatile 或许是由于该变量在多线程环境下会被频繁地读写，并且多个线程之间需求及时地获取到 array 的最新值。运用 volatile 关键字能够确保线程之间对 array 的修正和读取操作是同步的，防止了由于线程缓存导致的数据不共同问题。

需求注意的是，volatile 关键字仅仅确保了可见性和禁止指令重排序，但并不能确保对 array 的复合操作（例如读取-修正-写入）是原子性的。假如需求确保复合操作的原子性，需求运用其他同步机制，例如运用锁（synchronized）或者并发调集类来确保线程安全。

底层数据结构

/** 内部的数据结构，只能经过getArray/setArray拜访。 */
private transient volatile Object[] array;

初始化和结构办法

// 创立一个空列表
public CopyOnWriteArrayList() {
    setArray(new Object[0]); 
}
// 创立一个包含调集元素的列表
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] es;
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        es = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}
// copy 给定的数组创立列表
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

结构办法中最后都调用了 setArray() 办法，将数组保存到了属性 array 中。

增加操作

直接增加元素到数组尾部：

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

synchronized 确保同步，直接经过 Arrays.copyOf(int[], int) 仿制一份容量 + 1 的新数组。

增加到指定方位：

public void add(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException(outOfBounds(index, len));
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len + 1);
        else {
            newElements = new Object[len + 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    }
}

synchronized 确保同步，本质也是经过 System.arraycopy 系列办法将本来的数组拆成两份然后拼接到 newElements 中，最后经过 setArray 更新底层数据结构。

由于是多线程，所以供给了额外的增加办法，来查看数组中是否现已存在某个元素，假如数组中不存在，则增加；否则，不增加，直接回来，能够确保多线程环境下不会重复增加元素。

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOfRange(e, snapshot, 0, snapshot.length) < 0
        && addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i]
                    && Objects.equals(e, current[i]))
                    return false;
            if (indexOfRange(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

删去操作

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index);
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index,
                             numMoved);
        }
        setArray(newElements);
        return oldValue;
    }
}

也是经过 System.arraycopy 来重新组成数组的。

查询操作

public E get(int index) {
    return elementAt(getArray(), index);
}
static <E> E elementAt(Object[] a, int index) {
    return (E) a[index];
}

由于底层时数组，所以直接索引。

扩容逻辑

从增加和删去操作能够看出，CopyOnWriteArrayList 都是直接更新容量，然后经过 System.arraycopy 仿制，所以扩容每次都是 +1 / -1 。

总结

List 接口下的完成包含：ArrayList、Vector、LinkedList 和 CopyOnWriteArrayList 。它们之间有以下差异：

List 完成	底层数据结构	扩容机制	线程安全
ArrayList	数组	每次 1.5 倍扩容	无法确保线程安全
Vector	数组	每次 2 倍扩容	sychronized 关键字修饰办法
LinkedList	双向链表	链表无需扩容	无法确保线程安全
CopyOnWriteArrayList	数组	每次依据增加/删去数量扩容	Object 目标合作 sychronized 代码块