JDK源码之ArrayList源码剖析

发表于 | 分类于

ArrayList是Java集合类中一个非常重要的实现类，低层实现为数组，在随机存储方面性能很高，但是在增删数据方面性能一般。平常使用的很多，但是还没有系统的取读取其源码。

继承关系

1
2
3
4
5
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  ...
}

  1. ArrayLis继承了AbstractList抽象类

  2. ArrayList实现了List接口，RandomAccess接口，Cloneable接口和Serializable接口。

    • List接口：一开始以为List接口都是很熟悉的东西，结果注释了下源码，发现还是有很多新加的特性，比如可分割迭代器这种，从来没有用过，不过今天的重点不在这里。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      public interface List<E> extends Collection<E> {
          //返回列表的长度
          int size();
          //列表是否为空
          boolean isEmpty();
          //列表中是否包含某个元素
          boolean contains(Object o);
          //获取列表的迭代器
          Iterator<E> iterator();
          //将列表转换成一个Object数组
          Object[] toArray();
          //将列表转换成任意类型的数组
          <T> T[] toArray(T[] a);
          //向列表中添加元素e
          boolean add(E e);
          //从列表中移除元素o
          boolean remove(Object o);
          //看列表中是否包含另一个集合的全部元素
          boolean containsAll(Collection<?> c);
          //将一个集合加入到列表中
          boolean addAll(Collection<? extends E> c);
          //将一个集合在指定位置加入到列表中
          boolean addAll(int index, Collection<? extends E> c);
          //将列表中属于另一个集合的元素都移除
          boolean removeAll(Collection<?> c);
          //移除所有不在另一个集合中的元素，取交集
          boolean retainAll(Collection<?> c);
          //对所有元素进行统一操作
          default void replaceAll(UnaryOperator<E> operator) {
              Objects.requireNonNull(operator);
              final ListIterator<E> li = this.listIterator();
              while (li.hasNext()) {
                  li.set(operator.apply(li.next()));
              }
          }
          //根据给定的比较器对列表进行排序
          @SuppressWarnings({"unchecked", "rawtypes"})
          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);
              }
          }
          //清空列表
          void clear();
          // 判断两个列表是否相等
          boolean equals(Object o);
          //返回列表的哈希值
          int hashCode();
          //获取index位置的元素
          E get(int index);
          //将index位置元素的值设定为element
          E set(int index, E element);
          //在指定位置添加元素
          void add(int index, E element);
          //移除index位置的元素
          E remove(int index);
          //元素o的最靠前的下标
          int indexOf(Object o);
          //元素o最靠后的下标
          int lastIndexOf(Object o);
          //返回迭代器列表
          ListIterator<E> listIterator();
          //返回指定位置之后的迭代器列表
          ListIterator<E> listIterator(int index);
          //返回字列表
          List<E> subList(int fromIndex, int toIndex);
          //返回并行迭代器列表
          @Override
          default Spliterator<E> spliterator() {
              return Spliterators.spliterator(this, Spliterator.ORDERED);
          }
      }

    • RandomAccess接口：是一个空的接口，目的是为了标明实现该接口的List是否支持随机访问，支持的话访问会更加高效。Java中有很多空接口是为了起到标记的作用，看ArrayList源码时需要注意这一点的作用。

      1
      2
      public interface RandomAccess {
      }

    • Cloneable接口：目的是为了表明实现了该接口的对象可以调用clone方法来实现对象的复制，设计模式中原型模式就是用的这个特性，该特性jdk1.0就已经支持了，可以说很Java了。

      1
      2
      public interface Cloneable {
      }

    • Serializable接口：序列化接口是为了标记一个对象的状态是否能序列化到文件，提供了一种内存中对象的保存和加载机制，也是个标记接口。

      1
      2
      public interface Serializable {
      }

可以看出，ArrayList除了三个标记接口外，最重要的还是List接口方法的实现。

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//序列化接口的VersionID，序列化时记录到文件中，反序列化过程中进行版本校验。
private static final long serialVersionUID = 8683452581122892189L;
//ArrayList初始的列表大小
private static final int DEFAULT_CAPACITY = 10;
//共享的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
 //共享空数组，专门给默认大小使用的。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 //ArrayList数据保存的位置，不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList中元素的个数
private int size;

构造方法

总结来说，ArrayList的构造方法有啥三个，默认长度的，指定长度的，根据集合类生成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 创建一个指定大小的ArrayList
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);
    }
}
// 创建一个默认大小（10）的ArrayList
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 根据给定的集合，创建包含该集合的所有元素的ArrayList
public ArrayList(Collection<? extends E> c) {
    // 将给定集合元素存储到elementData数组中
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 返回的不是Object数组时，进行数组复制操作
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 空数组时，为elementData赋值
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

trimToSize()方法

该方法是将ArrayList的容量设置为当前size的大小。目的是为了缩减ArrayList的存储空间，ArrayList的容量为开辟的数组长度，size为存进去的元素个数。当我们只需要对ArrayList做查询操作，而不需要进行新增操作，则可以trim节省内存空间。

1
2
3
4
5
6
7
8
9
public void trimToSize() {
    // 继承自AbstractList，防止多线程操作情况下，List发生结构性变化。
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

JDK源码里面三元表达式用的比较多，if判断用的比较少，以后需要多使用三元表达式，很简洁直观。

size()方法

1
2
3
4
// 返回列表中的元素个数
public int size() {
    return size;
}

isEmpty()方法

1
2
3
4
// 判断ArrayList是否为空
public boolean isEmpty() {
    return size == 0;
}

contains(Object o)方法

1
2
3
4
//调用indexof方法来判断一个对象是否在ArrayList中
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

indexOf(Object o) 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//判断一个元素是否在列表中，如果存在，返回第一个靠前位置的下标，如果不存在，返回-1。
public int indexOf(Object o) {
    // 如果传入的对象为null,则看有没有对象为null在列表中
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    // 调用Object的equals方法来进行比较两个元素是否相等
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf(Object o) 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
//找到一个元素在列表中最后一个出现的索引并返回，没找到返回-1，和indexOf方法，只是遍历数组时倒叙遍历而已，不赘述。
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

clone()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// clone方法是Object类的方法，返回当前ArrayList的一个副本
public Object clone() {
    try {
        // v为赋值的实例属性
        ArrayList<?> v = (ArrayList<?>) super.clone();
        //数据和modCount赋值
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

toArray()方法

1
2
3
4
//返回一个Object数组，直接调用Arrays中的copyof方法
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

toArray(T[] a)方法

1
2
3
4
5
6
7
8
9
10
11
12
// 将ArrayList中的元素赋值到一个数组中去
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 如果a的长度小于ArrayList的长度，返回一个包含ArrayList所有元素的数组
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 将ArrayList额elementData数组复制到a数组，然后将a数组的size位置赋值为空。
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

get(int index)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 获取指定下标的元素并返回，可以看出get方法其实就是两个方法的封装
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
 // 检查index是否超出了ArrayList的size。
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 从elementData中返回index位置的元素。
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

set(int index, E element)方法

1
2
3
4
5
6
7
8
9
10
// 将指定index下的元素设置为element，并返回旧的值。
public E set(int index, E element) {
    // index的范围检验
    rangeCheck(index);
    // 获取旧的值
    E oldValue = elementData(index);
    // 更新elementData中的值
    elementData[index] = element;
    return oldValue;
}

add(E e)方法

1
2
3
4
5
6
7
8
// 将元素e添加到ArrayList的末尾
public boolean add(E e) {
    // 校验size+1是否超过了ArrayList的大小
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在elementData中赋值
    elementData[size++] = e;
    return true;
}

add之前，首先需要检查是否存在数组越界的问题，这个由ensureCapacityInternal来确保，如果发生了越界则进行扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 验证minCapacity是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    // elementData为默认的空值时，也就是第一次插入元素，最小容量为两者的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 验证是否需要对elementData进行扩容
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 需要进行扩容，调用grow方法进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// elementData的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 进行必要的扩容操作，确保elementData可以存放所有的元素
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新的容量为原来容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 不够的话，直接将需要的元素数设置为数组长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将原来的数组元素复制到新的数组中
    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;
}

add(int index, E element)方法

1
2
3
4
5
6
7
8
9
10
11
12
// 在指定位置index处添加指定元素element
public void add(int index, E element) {
    // 检查index是否小于elementData的长度
    rangeCheckForAdd(index);
    // 检查elementData中添加一个元素是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将elementData数组index位置之后的元素向后移动，在index位置添加element，size++
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

remove(int index)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 移除指定index位置的元素并返回该元素
public E remove(int index) {
    // 检查index是否小于elementData长度
    rangeCheck(index);
    modCount++;
    // 旧值
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index位置的元素顺次向前移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    // 返回旧值
    return oldValue;
}

remove(Object o)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 从ArrayList中删除从0开始第一个遇到的o元素，成功返回true，失败返回false
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            // 找到o的下标
            if (o.equals(elementData[index])) {
                // 移除元素index
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 快速移除index下标处的元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index位置的元素顺次向前移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

clear()方法

1
2
3
4
5
6
7
8
9
10
// 从ArrayList中移除所有元素
public void clear() {
    modCount++;
    // 将elementData中所有元素设置为空
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

addAll(Collection<? extends E> c)方法

1
2
3
4
5
6
7
8
9
10
11
12
// 将指定集合c中的所有元素都添加到列表尾部，成功返回true，失败返回false
public boolean addAll(Collection<? extends E> c) {
    // 将集合c转换成数组a存储
    Object[] a = c.toArray();
    int numNew = a.length;
    // 扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将数组a添加到elementData数组之后
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

addAll(int index, Collection<? extends E> c)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 将指定集合c中的所有元素都添加到列表指定位置index只有，成功返回true，失败返回false
public boolean addAll(int index, Collection<? extends E> c) {
    // index合法性检查
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    // 扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 原数组需要移动的数量
    int numMoved = size - index;
    if (numMoved > 0)
        // 将原数组index位置之后的元素，后移newNum个位置
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 将数组a复制到index位置之后的空间
    System.arraycopy(a, 0, elementData, index, numNew);
    // size更新
    size += numNew;
    return numNew != 0;
}

removeAll(Collection<?> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 从ArrayList中移除集合c中的所有元素
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++)
            // 将ArrayList和c的交集元素保存或者丢弃，到局部变量elementData，最后一个下标为w
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 出现异常，没有完全遍历完
        if (r != size) {
            // 将r右边的元素直接复制到w右边
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // 将w下标之后的元素设置为null
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

retainAll(Collection<?> c) 方法

1
2
3
4
5
6
7
// 取并集
public boolean retainAll(Collection<?> c) {
    // 非空检查
    Objects.requireNonNull(c);
    // 返回差集
    return batchRemove(c, true);
}

序列化与反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 序列化方法，将列表状态写入数据流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
// 反序列化方法
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in capacity
    s.readInt(); // ignored
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

listIterator(int index)方法

这部分内容没有仔细去看，暂不注解，后面会进行完善。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// 获取列表指定位置的迭代器对象
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
// 获取list开头的迭代器对象
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
// Itr 内部类
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    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();
        }
    }
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
// ListItr内部类
private class ListItr extends Itr implements ListIterator<E> {
    // 构造方法
    ListItr(int index) {
        super();
        cursor = index;
    }
    // 是否有上一个迭代对象
    public boolean hasPrevious() {
        return cursor != 0;
    }
    // 获取当前迭代对象的下标
    public int nextIndex() {
        return cursor;
    }
    // 获取上一个迭代对象的下标
    public int previousIndex() {
        return cursor - 1;
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

subList(int fromIndex, int toIndex)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 从列表中取出指定位置的子列表
public List<E> subList(int fromIndex, int toIndex) {
    // 起点和终点的下标检查
    subListRangeCheck(fromIndex, toIndex, size);
    // 调用SubList内部类来实现字列表的实现
    return new SubList(this, 0, fromIndex, toIndex);
}
// 起点和终点的下标检查
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}
// SubList内部类，对ArrayList数组直接进行增删改查，只是为其限定了边界
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;
    // 构造方法，父列表，偏移量，fromIndex，toIndex
    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }
    public int size() {
        checkForComodification();
        return this.size;
    }
    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }
    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }
    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        parent.removeRange(parentOffset + fromIndex,
                           parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }
    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;
        checkForComodification();
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }
}

forEach(Consumer<? super E> action)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Collection方法中的增强型for循环
@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

Sort方法

1
2
3
4
5
6
7
8
9
10
11
// 传入比较器，对ArrayList进行排序
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}
Donate comment here