ArrayList, LinkedList源码笔记

Table of Contents

最近工作不忙, 抽空看了一下ArrayList和LinkedList的源码. 这两个类是List的具体实现类, 所以在它们之上还有许多的 抽象接口和抽象类, 下面源码分析的笔记

代码基于JDK

标记接口

在Java中有一类接口叫做"标记接口"(Marker Interface). 标记接口 是没有任何方法的接口, 它仅仅标志实现它的类具有"某个特点", 而系统的 其他应用可能会在对类做操作时先判断其是否具有这个特点(例如下面的Cloneable).

Cloneable

标志该类可以继承. Object类的clone()函数会先判断该类是否具有该特性, 如果没有则报错:

protected Object clone() throws CloneNotSupportedException {
    if (!(this instanceof Cloneable)) {
        throw new CloneNotSupportedException("Class " + getClass().getName() +
                                             " doesn't implement Cloneable");
    }

    return internalClone();
}

Serializable

标志该类可以被序列化和反序列化.

RandomAccess

这个标记接口被List类使用,标志该List具备 快速随机访问功能.

ArrayList

定义

ArrayList直接继承自AbstractList, 并实现了以下接口:

  1. List : 说明ArrayList具备List接口的功能.
  2. RandomAccess: 说明ArrayList是支持快速访问的.
  3. Cloneable: 可以被clone.
  4. Serializable: 可以被序列化和反序列化.
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

主要成员

  1. ArrayList的底层数据存储就像它的名字一样, 使用了一个 Object[] 数组, 因为ArrayList是支持泛型的, 所以在添加数据时,数据被转成了Object存储, 在获取数据时,又将其转化成相应的类型.
  2. 同时, AL还维护了一个size变量用来记录当前的数组大小.

构造函数

ArrayList支持三种类型的构造函数.

  1. 默认构造函数. 默认构造函数只有一行代码, 就是把存放数据的数组指向一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    另外AL里还定义了另外一个空数组EMPTY_ELEMENTDATA. 之所以要定义两个空数组, 是因为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是与DEFAULT_CAPACITY来结合使用的, 该数组标志着第一次添加 元素时elementData要扩容的大小. 可以看如下代码:

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }
    

    当第一次添加元素时, minCapacity的值为1, 所以会将 elementData扩容到DEFAULT_CAPACITY的大小.

  2. 带size的构造函数. 使用该构造函数可以指定数组的初始大小.会直接创建一个 Object数组.

    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);
        }
    }
    
  3. 使用集合创建ArrayList, 这个构造函数接受一个集合, 并使用该集合去初始化 elementData. 因为AL是接受泛型参数, 所以集合参数的 类型是该泛型的任意子类. 该函数的步骤

    1. 调用集合的toArray()函数.
    2. 赋值size值. 如果size大于0, 判断集合的class 是否为Object[].class, 如果不是, 则调用Arrays 的函数 copyOf() 将其转化成Object[]类型.
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

添加数据

ArrayList提供了两个添加数据的接口. add(E e)及 add(int index, E element). 这两个函数的实现都分为 两步:

  1. 查看当前空间是否够用, 不够则扩容.
  2. 插入数据. 第一个add()函数直接将数据放到指定位置. 第二个则调用了系统的arraycopy()函数将整体元素后移, 然后将元素放到指定位置.
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

查看当前空间

查看当前空间是通过调用ensureCapacityInternal()函数来实现的 需要传递给函数一个参数, 标志需要确保的最小size值. 该函数调用了ensureExplicitCapacity()来做扩容的工作(不一定必做). 如果需要扩容, 后者则会调用到了grow()函数做实际扩容, 该函数的步骤

  • 将当前容量增大1.5倍.
  • 如果增大后的容量还小于要求的容量, 则将其设为要求的容量.
  • 将增大后的容量与最大的阈值MAX_ARRAY_SIZE 作比较, 如果比它大, 那么调用hugeCapacity() 函数确定最后的容量大小:
    • 如果要求的容量是负数, overflow, 报错.
    • 如果大于MAX_ARRAY_SIZE, 则新容量为 Integer.MAX_VALUE. 否则为 MAX_ARRAY_SIZE.
  • 调用Arrays的copyOf()函数生成一个新容量大小的数组.

代码如下:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

查找数据

ArrayList支持基于下标查找数据, 并且该操作是O(1) 操作. 不过会将返回的数据强制转化为泛型类型.

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

删除数据

ArrayList提供了以下的删除API: remove(int), remove(Object), clear(), removeAll(Collection), removeIf(Predicate).

注:这些删除操作都会修改modCount的值, 该值用来判断List是否被多进程修改

按坐标删除

步骤:

  1. 计算要移动的元素数: num = size - index - 1
  2. 调用System.arraycopy()移动数组.
  3. 将数组的最后一个元素置为null.
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

删除指定元素

该函数先知道元素位置, 然后在做数组移动 和置null工作. 注: 由于AL支持存放null元素, 所以删除的时候null和实际元素要区分对待

清空所有

把所有元素置null就可以了.

批量删除

(即删除交集) removeAll()函数接受一个集合参数, 然后调用 batchRemove()做实际的删除工作. batchRemove()接受两个参数, 第一个就是上面的集合, 第二个 参数是boolean类型, 标志集合中的元素是否保留, 如果该参数 值为TRUE,则标志集合中的元素要保留, 否则删除.

removeAll()函数在调用该函数时传入的参数为false. batchRemove()会遍历当前所有元素, 然后判断是否在传入的集合中 也包含, 同时更新当前数组.

public boolean removeAll(Collection<?> c) {
     Objects.requireNonNull(c);
     return batchRemove(c, false);
 }

 private boolean batchRemove(Collection<?> c, boolean complement) {
     final Object[] elementData = this.elementData;
     int r = 0, w = 0;
     boolean modified = false;
     try {
         for (; r < size; r++)
             if (c.contains(elementData[r]) == complement)
                 elementData[w++] = elementData[r];
     } finally {
         // Preserve behavioral compatibility with AbstractCollection,
         // even if c.contains() throws.
         if (r != size) {
             System.arraycopy(elementData, r,
                              elementData, w,
                              size - r);
             w += size - r;
         }
         if (w != size) {
             // clear to let GC do its work
             for (int i = w; i < size; i++)
                 elementData[i] = null;
             modCount += size - w;
             size = w;
             modified = true;
         }
     }
     return modified;
 }

保留交集

retainAll()函数与removeAll()类似, 只不过retainAll()里传入的集合内容都会在 数组里保存, 其余的删除.

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

条件删除

removeIf()是提供了条件删除的功能, 该函数接受一个 Predicate的参数, predicate提供了判断条件, 如果 AL里的元素满足条件, 则将其删除.

@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

removeIf()的实现使用了BitSet类, 该类提供了bitmap 功能.主要步骤:

  1. 遍历元素, 如果满足Predicate的test条件, 则设置 removeSet的相应bit位. 遍历过程中会一直检查modCount有没有被其他线程修改. 如果修改则终止遍历并抛异常.
  2. 再次遍历元素, 获取removeSet里被设为没被设为true的 index,并存入elementData.
  3. 将elmentData剩下的元素设为null以方便GC回收.
  4. 修改modCount的值.

批量修改

replaceAll()函数提供了批量修改功能, 该函数接受一个一元操作符的类 UnaryOperator 实例. 然后将操作应用于所有元素.

关于fail-fast

在需要遍历元素的过程中, 经常会在for() 循环里判断modCount的值有没有变化, 如果 有变化则立即停止循环并抛出并发异常.

而modCount会变化的唯一可能是其他线程同时 在操作这个ArrayList.

注: 在add()类相关函数中没有发现modCount的操作.

迭代器

ArrayList支持两种迭代器: iterator和listIterator.

Iterator实现: Itr

通过iterator()函数可以获取AL的Iterator, 函数的实现中 创建了一个AL自定义的内部类Itr. Itr继承自抽象类 Iterator.

Itr内部定义了一个cursor变量, 以及一个expectedModCount, 一个lastRet(用来保存上一次的位置). 当创建一个新实例时, 会将其赋值为modCount. 看一下对Iterator 所提供的API的实现.

  1. hasNext(): 将cursor当前值与size做比较, 如果不相等则表示还有 元素.
  2. next(): 返回一个泛型的值. 函数实现步骤:
    1. 检查是否被其他线程修改. 如果是报同步异常.
    2. 检查cursor的值是否超出了size, 如果是报异常. (是不是modCount未修改, 但元素已删除的时候会出现这种情况?).
    3. 检查i的值是否超出了AL的数组长度, 如果是则抛同步异常.
    4. 将cursor的值加1, 并返回之前cursor位置的元素. 并讲之前值赋值给lastRet.
  3. remove(): 删除当前cursor指向的元素. 函数实现步骤:
    1. 判断lastRet是否小于0, 如果是, 说明还没调用next()就调用remove. 抛非法状态异常.
    2. 检查是否有其他线程修改.
    3. 调用remove()删除lastRet当前指向的元素. 将cursor的值更新为lastRet, 并把lastRet设为-1(从这儿可以看出不能连续调用两次remove()). 更新expectedModCount. 如果这一步抛出边界异常, 则捕获并重新抛出同步异常.
public boolean hasNext() {
          return cursor != size;
      }

      @SuppressWarnings("unchecked")
      public E next() {
          checkForComodification();
          int i = cursor;
          if (i >= size)
              throw new NoSuchElementException();
          Object[] elementData = ArrayList.this.elementData;
          if (i >= elementData.length)
              throw new ConcurrentModificationException();
          cursor = i + 1;
          return (E) elementData[lastRet = i];
      }

      public void remove() {
          if (lastRet < 0)
              throw new IllegalStateException();
          checkForComodification();

          try {
              ArrayList.this.remove(lastRet);
              cursor = lastRet;
              lastRet = -1;
              expectedModCount = modCount;
          } catch (IndexOutOfBoundsException ex) {
              throw new ConcurrentModificationException();
          }
      }

ListIterator实现: ListItr

ListItr继承Itr并实现了ListIterator接口. 包括: previous(), hasPrevious(), nextIndex(), previousIndex()等.

子列表

ArrayList提供了接口subList()来获取该AL的一个子集. 这是通过创建 一个新的SubList类实例来实现的.

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, offset, fromIndex, toIndex);
}

SubList类是ArrayList的一个子类, 它的底层数据存储仍然是ArrayList的elementData 数组, 所以对SubList的修改也会反馈到ArrayList中. SubList重要维护了一个索引来记录它所包含的数据. 包括 offset, size等. 由于SubList也继承自AbstractList, 所以它也提供了List的所有增删查的行为, 当都是在函数内部通过坐标索引计算后调用ArrayList相应的api实现. 同时, SubList也提供Iterator接口.

Iterable

实现了Iterable的接口类, 可以使用 "for-loop" 形式的语法. 例如这里实现一个 Foo 类实现了 Iterable 接口. 那么可以使用 如下代码来操作 Foo 实例.

Foo foo = new Foo();
for(T t : foo ) {//do  something}

该接口的几个主要API:

名称 功能
interator() 返回一个Iterator 实例, 用于实现对Interable接口的"遍历".
forEach(action) 接受一个Cousumer类型的参数action, 然后对"遍历"后的每个元素用action做处理.

Iterator

Iterator是集合的"迭代器", 提供了对集合进行遍历的方法. Iterator一般 都是依附Iterable存在的.
Iterator提供的API:

名称 功能
hasNext() 判断集合是否还有元素.
next() 返回下一个元素.
remove() 删除next()返回的元素.
forEachRemaining(action) 对集合剩下的元素执行action动作. action的定义与Iterable介绍的相同.

Collection

Collection是Java"集合"家族的顶层接口, 继承自Iterable. 定义了集合的一些共同特性:

API名称 描述
size() 集合大小
isEmpty() 是否为空
contains() 是否包含元素
iterator() 返回该集合的迭代器
toArray()/toArray(T[] a) 集合转化为数组
add(E e) 添加元素
remove(E e) 删除元素
addAll(c) 添加一个Collection
clear() 清空整个集合

List

List是"队列"家族的抽象类, 队列是一种"有先后顺序"的集合, 队列中的元素 有添加的先后顺序, 新元素都会添加到队列尾部. 该类继承自Collection, 除了Collection的特性, 该类的其他主要特性包括:

API 描述
add(e) 添加到队尾, 返回是否添加成功
remove(e) 删除第一次出现的元素
addAll(index, c) 将集合c添加到index开始的位置
replaceAll(operator) 使用operator来替换所有元素
sort(c) 使用Comparator c对队列进行排序
get(index) 获取index位置的元素
set(index, e) 替换index位置的元素, 返回旧元素
add(index, e) index位置插入一个元素
remove(index) 删除index位置的元素
index(e) 获取元素在队列中第一次出现的位置, 或-1
lastIndexOf(e) 获取元素在队列中最后一次出现的位置, 或-1
subList(start, end) 获取[start, end) 位置的子列表
listIterator() 获取list的ListIterator

PS:

  1. replaceAll()实现: 首先获取队列的ListIterator, 然后过该iterator 来操作队列.

    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    
  2. sort(Comparator c)实现: 首先调用toArray()方法将队列转化为array, 然后调用 Arrays.sort() 函数来对array进行排序, 最后将排序后的 array通过ListIterator存入队列.

    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    
  3. subList(): 通过该函数返回的子队列, 其数据还是存储在其"父队列"的底层实现中, 所以对该队列数据的修改都会影响付队列, 同样, 对父队列的修改也会影响子队列.

ListIterator

该类是List类的一个Iterator实现, 继承自Iterator接口, 其提供了遍历List的接口, 同时对一些接口做了条件约束: 即对List的遍历只能按照"从前向后"或"从后向前"的顺序.
该类的主要API如下:

API 描述
hasNext() 从前向后遍历,判断是否还有元素
next() 从前向后遍历, 返回下一个元素
nextIndex() 从前向后遍历, 返回下一个位置
hasPrevious() 从后向前遍历, 判断是否还有元素
previous() 从后向前, 返回下一个元素
previousIndex() 从后向前, 返回下一个元素位置
remove() 返回next()或previous()的返回值
set() 替换next()或previous()的返回值
add() 见注1

PS:

  1. add(): 插入到next()返回值的"前面", 或previous()返回值的"后面". 另一个观点, 从"从前向后"的视角来看, 新插入的元素永远在当前元素的"前面".

AbstractCollection

AbstractCollection是Collection接口的一个实现, 对于 集合类型的一些"可能"的共同操作, 该类给出了一些API实现, 包括:

  1. isEmpty()

    public boolean isEmpty() {
        return size() == 0;
    }
    
  2. contains(o) 该函数实现分两种情况: 如果o为null, 则判断集合中是否包含null. 否则,遍历 集合并调用参数o的equals()方法来判断是否有相等元素. 元素遍历是通过iterator实现.

    public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    
  3. toArray() 该函数用于将集合转换为数组, 需要关注的是, 在转化过程中, 集合的 结构可能被修改(多线程), 即元素被添加或删除.
    该函数的实现也cover了这种情况. 从下面代码可以看到,

    1. 在每次for循环开始都会调用hasNext()判断是已经到结尾(即期间有元素被删除). 如果是, 则直接调用Array的copyOf()函数把返回临时数组的一个copy, 该临时数组 用于存储已经遍历过的元素.
    2. 遍历完之后, 还会再次调用hasNext()判断是否有新元素, 如果有, 则调用finishToArray() 函数继续对集合进行变量, 并分配一个更大的数组, 知道集合变量完或者达到数组上限.
    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }
    
  4. toArray(T[] a) 如果a的size足够能容下集合元素, 则存入a中并返回a, 否则存入一个新分配的数组并返回.
  5. remove(): 实现方式与contains()相同, 也是通过iterator进行操作.
  6. containsAll()/addAll()/removeAll()
    实现方式基本相同, 都是遍历参数集合, 然后基于参数中的每个元素 对集合进行操作.
  7. retainAll(c). 只保留c和该集合的"交集"元素.
  8. clear(): 反复调用iterator的hasNext(), next(), remove()函数删除所有元素.

    public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }
    

AbstractList

该类是AbstractCollection的一个子类并实现了List接口, 该类实现了 List相关的一些共同操作. 包括:

  1. indexOf(o):寻找元素位置. 该函数的实现使用了previousIndex()函数, 因为 调用next()之后, iterator会移动到下一位, 所以需要调用这个函数才能获取 到"命中元素"的位置.

    public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }
    
  2. lastIndexOf(o): 实现方式与indexOf()相同, 只是遍历顺序相反.

Itr

该类是AbstractList的一个内部类, 在List的层级结构中, 是第一次具体实现 一个Iterator. 可以看下该类是如何具体实现Iterator的API的.

  1. hasNext():判断当前的光标是否等于size()函数. 如果等于, 表示到达尾部, 返回false.

    public boolean hasNext() {
        return cursor != size();
    }
    
  2. next():返回下一个元素. 由于光标一开始是指向第一个元素(index=0), 所以每次调用该函数, 返回的都是当前光标位置的元素, 然后再把光标 移动一个位置. 同时有一个成员变量 lastRet 用于记录这次返回值的位置.

       public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    

    在函数的开始调用了 checkForComodification() 函数, 该函数用于 判断是否有其他线程操作了该iterator所属的集合.它的实现原理是: Iterator有一个成员变量expectedModcount, 其值等于集合的变量modCount, 每次集合被修改(添加/删除), modCount的值都会发生变化. 所以如果发现 expectedModcount的值与该值不相等了, 说明"集合"被其他线程修改了. 在AbstractList中就会抛异常.

    final void checkForComodification() {
         if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
     }
    
  3. remove(): 如果当前光标没有指向list区间, 则抛异常. 否则调用 AbstractList的remove()函数. 然后将缓存光标 lastRet 置位-1. 并重新赋值 expectedModcount(因为AbstractList的 remove()函数可能会修改modCount的值).

ListItr

该类是Itr的子类并实现了ListIterator接口. 主要是实现了ListIterator"从后向前"的遍历方法.

  1. 构造函数ListItr(index): 直接将光标至于index的位置.
  2. hasPrevious():判断当前光标是否为0, 如果是返回false.
  3. previous(): 返回当前光标的前一个元素. 这里与next()不同, next()是先返回当前光标的值, 移动光标. previous()是返回 当前光标前面的值, 并移动光标.

    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    
  4. nextIndex(): 返回当前光标.
  5. previousIndex(): 返回当前光标减1.

SubList

该类是AbstractList的子类,是"子队列"概念的代码实现. 代表了某个 队列的一部分. 在其实现中, 其内容存储在原列表的底层存储中. 该类 只维护了一些"列表"状态, 来表示子对类. 任何对该类的队列的修改都会 影响到原列表, 反之亦然. 通过下面的几个函数可以看出对该类的增删其实调用的 都是原来队列的方法.

SubList(AbstractList<E> list, int fromIndex, int toIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > list.size())
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
    l = list;
    offset = fromIndex;
    size = toIndex - fromIndex;
    this.modCount = l.modCount;
}

public E set(int index, E element) {
    rangeCheck(index);
    checkForComodification();
    return l.set(index+offset, element);
}

public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    return l.get(index+offset);
}

public void add(int index, E element) {
    rangeCheckForAdd(index);
    checkForComodification();
    l.add(index+offset, element);
    this.modCount = l.modCount;
    size++;
}

public E remove(int index) {
    rangeCheck(index);
    checkForComodification();
    E result = l.remove(index+offset);
    this.modCount = l.modCount;
    size--;
    return result;
}

RandomAccessSubList

该类是SubList的一个子类, 但是实现了RandomAccess接口(空接口), 表明其具有RandomAccess的属性. 该类的所有操作几乎都是使用SubList的操作.

在AbstractList的subList()函数实现中, 会判断当前List是否为RandomAccess, 如果是, 则会返回一个 RandomAccessSubList 实例, 否则返回一个 SubList 实例.

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

AbstractSequentialList

在介绍LinkedList之前, 先看一下它的父类, 该类是AbstractList的 子类, 但是它具有"顺序"的属性, 这是相对于ArrayList的RandomAccess属性而言. 官方文档中对该属性是这样解释的.

* This class is the opposite of the <tt>AbstractList</tt> class in the sense
* that it implements the "random access" methods (<tt>get(int index)</tt>,
* <tt>set(int index, E element)</tt>, <tt>add(int index, E element)</tt> and
* <tt>remove(int index)</tt>) on top of the list's list iterator, instead of
* the other way around.<p>

上面这段文字解释了在该类中通过index "插入/删除" 元素的实现方法. 都是通过其ListIterator实现的. (想想在ArrayList中,这些方法都是直接 操作数组). 可以看下几个相关的API代码.

public void add(int index, E element) {
    try {
        listIterator(index).add(element);
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}
public E remove(int index) {
    try {
        ListIterator<E> e = listIterator(index);
        E outCast = e.next();
        e.remove();
        return outCast;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

另外, 该类的 iterator() 和 listIterator() 函数返回的都是 ListIterator实例.

Deque

双端队列, 支持头部和尾部的插入和删除动作. Deque接口提供了这些操作的相应API.

LinkedList

继承自AbstractSequentialList, 并实现了 ListDeque 接口.

不过与AbstractSequentialList不同的是, LinkedList的插入删除并 没有使用ListIterator, 而是直接操作链表. 下面是一些核心API:

  1. unlink(e): 删除元素, "几乎"所有删除API的底层实现. 与ArrayList不同的是, 它没有设计到"一片内存"区域的移动, 所以 效率上要比ArrayList高.

    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;
    }
    
  2. linkBefore(e, node): 插入元素,实现原理同unlink().
  3. node(index): 获取index位置的node, "几乎" 所有遍历类的底层实现. 这需要遍历链表, 不过因为LinkedList是双向列表, 所以该函数的实现上也有点技巧: 即如果index > size/2, 则从队列 尾部向前寻找, 否则从队列头部向后寻找.

    Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }
    

这三个函数基本就是LinkedList的核心原理.

Node

LinkedList是使用"链表"这种数据结构来存储数据, 所以其内部定义了一个 Node类用来表示链表节点. 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;
    }
}

SynchronizedList

由于List类不是线程安全的. 多线程可以同时修改list的内容. 所以为了解决这个问题, Collections类提供了一个 snchronizedList() 函数用于将 List 转化为一个 "同步" list. 其基本原理类似于adapter模式, 实现了一个新的list, 被提供了 同步功能. 看下部分源码:

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
    private static final long serialVersionUID = -7754090372962971524L;

    final List<E> list;

    SynchronizedList(List<E> list) {
        super(list);
        this.list = list;
    }
    SynchronizedList(List<E> list, Object mutex) {
        super(list, mutex);
        this.list = list;
    }

    public boolean equals(Object o) {
        if (this == o)
            return true;
        synchronized (mutex) {return list.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return list.hashCode();}
    }

    public E get(int index) {
        synchronized (mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized (mutex) {return list.set(index, element);}
    }
    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }
    public E remove(int index) {
        synchronized (mutex) {return list.remove(index);}
    }

Created At <2016-06-08 Wed> by Luis Xu. Email: xuzhengchaojob@gmail.com