List - ArrayList - 《Huang Java 开发学习》

概览
关键属性
构造器
1.添加元素
2.扩容
3.删除元素
4.查询元素
5.迭代器
- Iterator
- ListIterator
6. Fail-Fast
7. 序列化
8.System.arraycopy()和Arrays.copyOf()方法

概览

ArrayList类扩展AbstractList，实现了 List接口、RandomAccess 接口，因此支持随机访问。

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

ArrayList类扩展AbstractList并执行List接口。
支持随机访问，但是在List的中间插入和移除元素时较慢。
底层为单向链表，基于数组实现

关键属性

private static final int DEFAULT_CAPACITY = 10; // 默认初始大小
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // size为默认大小的空数组
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
transient Object[] elementData;
private int size; //容器大小

定义在 AbstractList 中的。记录对 List 操作的次数。主要使用是在 Iterator，是防止在迭代的过程中集合被修改。
protected transient int modCount = 0; // 用来记录AbstractList修改次数

构造器

ArrayList(); // 建立一个默认大小的空数组，即=DEFAULTCAPACITY_EMPTY_ELEMENTDATA,但是在第一次添加元素的时候扩容到10
ArrayList(Collection c); // 建立由c初始化的数组列表
ArrayList(int capacity); // 建立指定初始容量的数组列表
// 若指定的collection的大小为0或者capacity=0，建立一个空数组，即=EMPTY_ELEMENTDATA

1.添加元素

public boolean add(E e)

将元素填在原size后

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

public void add(int index, E element)

将index位置上及之后的元素往后移一位，再将填充元素复制到index位置

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

public boolean addAll(Collection<? extends E> c)

将填充元素复制到原size位置后

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c)

将index位置上及之后的元素往后移填充元素数目位，再将填充元素复制到index位置和其后面的填充元素数目位

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
// 将index后面的元素往后移
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

2.扩容

在添加元素前，都会去判断是否需要扩容

添加元素会调用ensureCapacityInternal(添加元素后数组内元素数=minCapacity)
计算最小容量：判断当前elementData是否=DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即使用无参构造器创建，若等于，minCapacity<=10，即minCapacity=10,否则minCapacity=添加元素后数组内元素数
判断是否扩容
1. 否：minCapacity <= elementData.length
2. 是：minCapacity > elementData.length
扩容，计算新数组容量大小newCapacity，默认是newCapacity=oldCapacity + (oldCapacity >> 1)，但若有以下这几种情况
1. minCapacity > elementData.length*1.5（一次性添加大量数据），newCapacity=minCapacity ；
2. elementData.length*1.5要大于Integer.MAX_VALUE - 8
  1. elementData.length*1.5 > minCapacity > Integer.MAX_VALUE - 8 ，newCapacity = Integer.MAX_VALUE；
  2. elementData.length*1.5 > Integer.MAX_VALUE-8 > minCapacity ，newCapacity= Integer.MAX_VALUE - 8；

调用 Arrays.copyOf ，把原数组复制到新数组，属于浅拷贝。这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

// minCapacity = size+添加元素数目
private void ensureCapacityInternal(int minCapacity) {
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 为使用无参构造函数创建的ArrayList设置elementData.length的最小值，即默认值 10
// elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ?minCapacity=10:minCapacity = 添加元素后的size大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     return minCapacity;
}
// 新size > elementData.length ，则将数组扩容
private void ensureExplicitCapacity(int minCapacity) {
     modCount++;
     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
}
// 若 新size > elementData.length*1.5，elementData.length=新size值；
// 若 elementData.length*1.5 > 新size > Integer.MAX_VALUE - 8 ，elementData.length = Integer.MAX_VALUE；
// 若 elementData.length*1.5 > Integer.MAX_VALUE-8 > 新size ，elementData.length = Integer.MAX_VALUE - 8；
// 以上不满足，elementData.length*=1.5
//
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;
}

3.删除元素

本质：

调用 System.arraycopy() 方法拷贝数组，将需要删除的元素段之后的元素组复制到需要删除的起始位置，再将（size-删除数目）到 size 的元素引用指向null。
该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

方法：

public E remove(int index)
- 检验index合法与否
- 判断要删除的元素是否位于数组的最后一个位置
- 若是最后一个，直接将数组最后一个元素置为null
- 若不是，调用 System.arraycopy() 方法拷贝数组，将index位置之后的元素复制到index位置至size-1的位置，将数组最后一个元素置为null
- 返回index位置上的元素
```
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;
}
```
public boolean remove(Object o)
- 判断o对象是否为空
- 遍历查询获得要删除元素的下标index
- E remove(int index) 与 private void fastRemove(int index) 基本相同。将index位置之后的元素复制到index位置至size-1的位置，将数组最后一个元素置为null

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++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
        }
    return false;
}
private void fastRemove(int index) {
        modCount++;
        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
}

public boolean removeAll(Collection<?> c)

删除相同元素

判断c是否为空，空抛出异常
声明r,w，r是遍历数组的下标，w是存在原数组但不存在c的元素个数
遍历数组，将存在原数组但不存在c的元素依次从0开始存放
若是在调用contains，判断原数组元素是否存在c时抛出异常，将未遍历的部分拷贝至已整理部分的数组后
若原数组与c没有相同元素，那么返回false，表示数组未修改

若原数组存在与c相同的元素，那么返回true，并将下标为w至size的元素指向null

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

public boolean retainAll(Collection<?> c)

删除c中不存在的那些元素，即保留相同元素

判断c是否为空，空抛出异常
声明r,w，r是遍历数组的下标，w是存在原数组且存在c的元素个数
遍历数组，将存在原数组且存在c的元素依次从0开始存放
若是在调用contains，判断原数组元素是否存在c时抛出异常，将未遍历的部分拷贝至已整理部分的数组后
若c包含了所有原数组的元素，那么返回false，表示数组未修改
若c没有包含了所有原数组的元素，那么返回true，并将下标为w至size的元素指向null
- public void clear()

将数组内所有对象引用指向null

public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
}

4.查询元素

public E get(int index)

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

5.迭代器

Iterator

单向遍历，从头至尾

public Iterator<E> iterator() { return new 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;
    }
    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继承了Itr，包含了Itr所有方法，并扩展了hasPrevious、nextIndex、previousIndex 、previous、set和add方法

public ListIterator<E> listIterator() { return new ListItr(0); }
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();
            }
        }
}

6. Fail-Fast

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    //这里 记录操作前的 modCount
    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]);//操作
    }
    //这里的modCount是操作后的 modCount与之前的作比较
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

7. 序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

transient Object[] elementData; // non-private to simplify nested class access

ArrayList 实现了 writeObject() 和 readObject() 来只序列化数组中有元素填充那部分内容。

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。

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++) {
        // 使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

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
        //根据size来分配内存，来控制只序列化数组中有元素填充那部分内容
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            // 使用的是 ObjectInputStream 的 readObject() 方法进行反序列化
            a[i] = s.readObject();
        }
    }
}

8.System.arraycopy()和Arrays.copyOf()方法

Arrays.copyOf() 的源代码内部调用了 System.arraycopy() 方法。

System.arraycopy() 方法需要目标数组，将原数组拷贝到目标数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置；
Arrays.copyOf() 是系统自动在内部创建一个数组，并返回这个新创建的数组。