ArrayList

List的动态数组实现，线程不安全，可以存null。

interface Iterable

可迭代的抽象集合接口，包含一个迭代器（iterator），实现该接口的集合支持迭代遍历。

interface Collection extends Iterable

集合的最基本接口，定义了集合应该包含的基本方法。如下选取了部分方法：

  • size() ：返回集合包含元素个数
  • isEmpty() ：判断集合是否为空
  • contains(Object o) ：判断对象是否包含
  • Iterator iterator() ：提供迭代器
  • add(E e) ：添加元素（add(int index)不是集合基本方法，是根据集合的属性衍生出来的功能）
  • remove(Object o) ：删除元素（不提供remove(int index)，原因同上）

abstract class AbstractCollection implements Collection

提供了Collection的骨架（skeletal）实现，减小了实现Collection接口的代价。
AbstractCollection实现了Collection中可以依赖Collection中包含接口可实现的接口，剩余的接口让子类自己去实现。
比如Collection.isEmpty()，只需要调用Collection.size()判断是否为0就可，所以AbstractCollection实现了isEmpty()方法，子类只需要实现size() 方法就可。

interface List extends Collection

List，Set，Map是用来区分不同类型的集合的。
List表示其中的元素按线性方式存储，可以有重复对象，允许按照对象在集合中的索引位置检索对象，允许排序等。
所以在Collection的基础上，List添加了如add(int index, E element) 在指定位置添加元素，get(int index) 通过index获取元素，indexOf(Object o) 判断元素所在index，sort() 排序等在线性存储时适用的方法。
List的子类通常使用数组来存储元素。

interface Cloneable

标记接口（在执行相关方法时，会检查是否实现了特定接口），实现该接口的类可以使用java.lang.Object.clone()方法进行浅克隆。

interface RandomAccess

标记接口，实现该接口的类表示支持快速随机访问（通过index访问），未实现的随机访问成本较高（比如LinkedList未实现该接口）

interface Serializable

标记接口，实现该接口的类表示支持序列化相关的操作。

abstract class AbstractList extends AbstractCollection implements List

提供了List的骨架（skeletal）实现，减小实现List接口的代价。因为List是在Collection基础上的扩展，所以AbstractList首先继承AbstractCollection来复用已经实现了的Collection方法，AbstractList主要实现了List中的部分可以通过现有方法实现的扩展方法。
如indexOf(Object o) 判断元素所在index，通过调用迭代器遍历元素实现。

class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

List的动态数组方式实现，元素允许为null，提供基本的add，get，remove，foreach功能。
ArrayList 使用数组来存储元素，可是指定初始化数组的容量大小，或者默认一个空数组（空数组首次扩容为10）。

  • ArrayList适合只在队尾插入元素，同时需要随机访问元素时使用会有很好的性能。
  • ArrayList 线程不安全。
  • 访问：通过index直接访问数组中的元素。(复杂度：O(1))
  • 扩容：ArrayList的容量最大可达2^31-1 ，每次扩容后的数组长度是 min(MAX_ARRAY_SIZE, old + (old >> 1))
  • 插入：默认的add操作是在数组尾添加元素，当然也可以指定index进行插入（index后面的数组使用java.lang.System#arraycopy本地方法，进行后移）
  • 删除：基本的删除一个元素的操作（指定index或object），都是在确定index后，将index后的子串进行前移一格。removeAll则略有不同，通过遍历数组，将需要保留的元素按顺序放入数组，然后清空剩余的子串。(复杂度：O(N))具体实现如下：
1
2
3
4
5
6
int r = 0, w = 0;
for (; r < size; r++)
    if (c.contains(elementData[r]) == false)
        elementData[w++] = elementData[r];
for (int i = w; i < size; i++)
    elementData[i] = null;
  • 迭代：ArrayList实现了ListIterator，在基本的Iterator基础上支持反向遍历等。
  • 相等：通过listIterator遍历两个list的元素判断是否相等，包含元素都相等则List相等。
  • 排序：使用数组的通用排序方法进行排序java.util.Arrays#sort(T[], int, int, java.util.Comparator<? super T>)；

LinkedList

List的双向链表实现，线程不安全，可以存null。

interface Queue extends Collection

Queue是用来区分不同类型的集合的一种。
Queue接口表示集合支持队列的属性，先进先出，FIFO (first-in-first-out)。但是该规则非必须，只需要规定某种优先级，优先极高的先出队列就可以属于Queue，比如优先队列，比如Stack(FILO，先进后出)
Queue定义了队列支持的基本方法，和List略微有不同：

  • offer() 添加元素到队尾
  • remove()，poll() 返回队首元素，并从queue中移除
  • element()，peek() 返回队首元素，不移除

interface Deque extends Queue

Queue的一种线性的实现，支持从队首对尾插入或访问元素(double ended queue)。所以包含的方法在Queue的基础上，区分头尾的操作(offerFirst , offerLast)

abstract class AbstractSequentialList extends AbstractList

为List的线性实现提供骨架实现。线性实现支持按顺序访问数据，不支持随机访问数据（或者随机访问数据代价较高），比如链表，无法和数组一样通过index直接定位元素，需要迭代到相应的index才能获取。
因为AbstractSequentialList无法按照index快速访问对应元素，所以get() 是通过listIterator迭代器来获取对应index的元素。包括set(), add(), addAll(), remove() 都是迭代到对应的index，然后进行操作。

class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

List的双向链表实现，在基础的List操作上，支持在队首队尾进行add、get、remove等操作，可以用作队列、栈、双向链表的实现。
LinkedList使用链表存储元素，不像数组存储，元素不是连续的，而是通过在每个元素上添加其前后元素的指针来把链表连接起来，所以很多操作(add, remove等)首先遍历到对应位置，然后更改元素的前后指针。

  • 在需要经常在队列的中部插入元素时，LinkedList会比较合适。
  • LinkedList 线程不安全。
  • 节点定义：
1
2
3
4
5
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}
  • 插入：链表的插入操作通过改变每个节点的前后指针就可以实现。指定插入位置的操作复杂度为(O(N))，主要用在遍历到index的位置。首尾操作的话为O(1)。
1
2
3
4
5
6
7
8
9
void linkBefore(E e, Node<E> succ) {
    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;
}
  • 访问：链表不支持O(1)的随机访问，如果要访问index的元素，需要从队首或队尾进行遍历到对应位置，复杂度O(N)。
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}