0. JDK1.7
1. 相关参数
- 1.1 常量
2. 构造方法
3.add、addAll方法与扩容
4. set方法
5. get方法
6. remove方法
8. clear方法
9. contains方法
10. isEmpty方法
11.toArray()
- 12. subList()
13. 常见问题
14. 自定义ArrayList

截屏2021-05-17 下午12.31.25.png
父类AbstractList实现了List，提供了几个抽象方法（get、set等），强制子类实现这些方法。ArrayList实现了List接口（冗余操作）

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

继承了AbstractList抽象类
接口：
- List接口（冗余）
- RandomAccess：随机访问功能，通过元素的序号快速获取元素对象
- Cloneable：重写了clone()方法，通过 Arrays.copyOf（）拷贝数组。
- Serializable：支持对象实现序列化，成员变量没有使用 transient 关键字修饰，通过实现 writeObject() 方法进行序列化，readObject()方法反序列化
  0. JDK1.7
  调用无参构造器的时候给底层数组elementData初始化，长度为10；jdk8是第一次add的时候初始化长度为10，懒初始化。所以扩容的时候也不需要再判断是否是使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行初始化了。
  1. 相关参数
  1.1 常量
```java // 默认的数组容量 private static final int DEFAULT_CAPACITY = 10;

// 空对象 private static final Object[] EMPTY_ELEMENTDATA = {};

// 一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 数组最大长度 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

<a name="E2ho9"></a>
## 1.2 变量
```java
// 当前数据存放的数组，当前对象不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
// 当前数组的长度 
private int size;
// 父类AbstractList继承的属性，记录list结构被修改（size被改变了）的次数（set不算结构被修改）
protected transient int modCount = 0;

2. 构造方法

如果使用的是无参构造器，则初始elementData的容量为0，第一次添加时，扩容elementData为10（默认值），如果再次扩容，则为1.5倍。

如果使用的是指定大小的构造器，初始elementData容量为指定大小，如果需要扩容，则直接扩容为1.5倍。

  // 空参构造
  public ArrayList() {
      // 初始化空对象用的是default值
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  // 带容量的构造
  public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          // 如果参数符合规定，就声明一个这个参数大小的容器
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
          // 如果是0，赋默认的空对象
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }
  // 带一个collection集合的构造
  public ArrayList(Collection<? extends E> c) {
      // 将集合c转成数组，只拷贝数组的地址
      elementData = c.toArray();
      // 将该数组的长度赋值给size
      // 数组长度不为0
      if ((size = elementData.length) != 0) {
          // 再次判断类型
          if (elementData.getClass() != Object[].class)
              // 将Collection对象的内容复制到elementData中
              elementData = Arrays.copyOf(elementData, size, Object[].class);
      } else {
          // 数组长度为0，赋值空数组
          this.elementData = EMPTY_ELEMENTDATA;
      }
  }
  // 将集合转成数组
  public Object[] toArray() {
      // 调用数组工具类的方法
      return Arrays.copyOf(elementData, size);
  }

3.add、addAll方法与扩容

add(E element)
add(int i , E element)
addAll(Collection<? extends E> c)
addAll(int index, Collection<? extends E> c)

3.1 在arraylist末尾添加元素
步骤：
检查是否容量是否足够，是否需要扩容
- ensureCapacityInternal方法检查是否是无参构建（第一次无参构建需要扩容为默认的10）
- ensureExplicitCapacity方法使得modCount+1，并判断是否需要扩容
- 需要扩容，通过grow方法扩容至原先的1.5倍。通过Arrays.copyOf方法(底层arraycopy方法)进行拷贝
赋值操作，返回true ```java /**
- 在ArrayList结尾添加元素
- 1.先确定是否要扩容
- 2.再执行赋值操作 */ public boolean add(E e) { // 确保数组已使用长度（size）加1之后足够存下下一个数据 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }

/** 确定minCapacity

如果是调用无参创建，初始为10 */ private void ensureCapacityInternal(int minCapacity) { // 如果是第一次使用默认空参创建数组，默认容量=DEFAULT_CAPACITY=10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
```
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
```
} // minCapacity为此时elementData必须的最小长度 ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { // 确保添加的元素有地方存储 // 修改次数+1，用于fail-fast处理 modCount++; // 如果minCapacity（当前所需数组最小长度）大于elementData（数组实际长度）的长度，则进行扩容处理 if (minCapacity - elementData.length > 0)
```
 // 扩容，可能会引起溢出问题
 grow(minCapacity);
```
} // ArrayList动态扩容机制的核心 private void grow(int minCapacity) { // 可能存在整型溢出 int oldCapacity = elementData.length; // 容量默认扩大1.5倍，（默认空参创建的第一次add时old为0，所以新的也为0，相当于没有实现） int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0)
```
 // 可能1：newCapacity<0整型溢出
 // 可能2：newCapacity<minCapacity ，扩容之后的新容量小于当前数组所需最小长度（默认构造器的第一次扩容）
 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) // 说明已经整型溢出 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

新版本的抽出了calculateCapacity方法
```java
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    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);
    }

3.2 在指定位置添加元素

检查位置是否合法
确保容量够，是否需要扩容（同add方法）
使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。
将新数据加到指定位置上
增加size ```java /**
- 在ArrayList特定位置添加单个元素
- 思考：add(E e)没有调用add(int index, E element)，出于性能的考虑，不需要检验位置是否合法 */ public void add(int index, E element) { // 检查位置是否合法 rangeCheckForAdd(index);
  
  // 跟add(E e)中处理方式类似 ensureCapacityInternal(size + 1); // 将elementData中位置为index位置及其后面的元素都向后移动一个下标 // 底层是native方法，使用cpp直接操作内存，性能比copyOf快，少了for的操作时间。两者都是浅拷贝，只拷贝了地址 System.arraycopy(elementData, index, elementData, index + 1,
```
             size - index);
```
  elementData[index] = element; size++; }

// 校验位置 private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

<a name="qpnP8"></a>
## 3.3 addAll末尾添加
```java
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;
        // 根据numNew的值
        return numNew != 0;
    }

3.4 addAll在中间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
        // 确定移动元素的个数
        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;
    }

4. set方法

public E set(int index, E element) {
        // 判断index是否合法 校验
        rangeCheck(index);
        // 获取旧值
        E oldValue = elementData(index);
        // 更改
        elementData[index] = element;
        return oldValue;
    }
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 E elementData(int index) {
        return (E) elementData[index];
    }

5. get方法

    public E get(int index) {
        // 校验index
        rangeCheck(index);
        // 返回获取的元素
        return elementData(index);
    }

6. remove方法

remove（int i）
remove（E element）
removeRange（int start,int end）
clear（）见8

removeAll（Collection c）

6.1 remove(int i)与remove(E element)

删除参数为值的remove方法需要遍历，另外在这里没有调用remove(int i)的方法是因为性能，不用再检验index了 ```java

// 参数为下标 public E remove(int index) {

  // 检查下标合法性
  rangeCheck(index);
  modCount++;
  // 保留该值
  E oldValue = elementData(index);
  // 计算移动个数
  int numMoved = size - index - 1;
  // 如果移动个数>0，就移动（只有删除最后一个元素才不用移动）
  if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
                       numMoved);
  // 最后一个位置置空，方便GC
  elementData[--size] = null; // clear to let GC do its work
  return oldValue;

}

E elementData(int index) {

  return (E) elementData[index];

}

// 参数为值
public boolean remove(Object o) {
    // 如果为null，删除为null的
    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])) {
                // 把索引传进去删除，不用再判断index了
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 删除元素
private void fastRemove(int index) {
    modCount++;
    // 移动的数据个数
    int numMoved = size - index - 1;
    // 如果移动的数据>0
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 删除过后最后一个的元素位置置为null，GC用
    elementData[--size] = null; // clear to let GC do its work
}

<a name="HB2PG"></a>
# 7. toString方法与Iterator
<a name="E2pUI"></a>
## 7.1 toString
该方法来自AbstractCollection类
```java
public abstract class AbstractCollection<E> implements Collection<E> {
  // ...
    public String toString() {
        // 获取迭代器
        Iterator<E> it = iterator();
        // 判断迭代器是否有元素
        if (! it.hasNext())
            return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            // 调用迭代器的next方法取出元素，将光标向下移动
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                // 没有元素
                return sb.append(']').toString();
            // 有元素追加逗号
            sb.append(',').append(' ');
        }
    }
}

7.2 Iterator接口

增强for循环就是采用迭代器实现的。
在获取迭代器的时候，集合只会执行一次将实际修改集合的次数modCount赋值给预期修改集合的次数expectedModCount。所以当一个线程在遍历时首先会判断这两个值是否相等，另一个线程对该集合（最后一个元素）增加或删除都会出现并发异常（增加和删除操作会修改集合的修改次数modCount）。建议使用迭代器的remove方法，会重新赋值
注：除了遍历到倒数第二个元素删除不会发生并发修改异常之外，其余元素删除时会发生并发修改异常。因为在遍历到倒数第二个元素时cursor此时会+1,删除完元素之后恰好和size相等，在hasNext方法中终止，就不会再走next方法了，就不会进行判断报并发修改异常。
在任何位置add会发生修改异常（iterator和list同时操作了，解决办法：ListIterator）

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        Iterator<String> ite = list.iterator();
        while (ite.hasNext()){
            if ("123".equals(ite.next())){
                list.add("789");  // 报并发修改异常
            }
            //if ("456".equals(ite.next())){
             //   list.remove("456");  // 报并发修改异常
            //}
        }
    }

public interface Iterator<E>{}

arrayList实现了该接口（内部类），重写了相关方法。提供了remove、向后遍历next

    public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E> {
        int cursor;       // 光标
        int lastRet = -1; // 记录-1
        // 将集合实际修改次数赋值给预期修改次数（并发修改异常）
        int expectedModCount = modCount;
        // 判断集合向后是否有元素
        public boolean hasNext() {
            // 光标是否与size相等
            return cursor != size;
        }
        // 向后遍历
        public E next() {
            // 检查是否出现并发异常  failed-fast机制
            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];
        }
        // 校验预期修改集合次数是否与实际修改集合次数相等
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
        // 删除
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                // 通过arraylist的remove方法删除值，这里会修改modCount
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                // 重新赋值了，就不会报并发修改异常
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

7.3 iterator()、Iterator、Iterable的关系

截屏2021-07-05 下午10.19.05.png

7.4 ListIterator接口

截屏2021-07-05 下午11.04.42.png
ListIterator接口继承了Iterator接口

public interface ListIterator<E> extends Iterator<E> {}

继承于Itr类，除了remove、向后遍历next之外，新增了add、set方法，向前遍历previous

  public ListIterator<E> listIterator() {
        return new ListItr(0);
    }
   public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    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();
            }
        }
    }

8. clear方法

    public void clear() {
        modCount++;
        // 元素全部置为null，方便GC
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        // 长度置为0
        size = 0;
    }

9. contains方法

    public boolean contains(Object o) {
        // 如果返回-1 则就没有这个值，否则返回这个值的下标
        return indexOf(o) >= 0;
    }
    public int indexOf(Object o) {
        // 判断null值
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            // 按顺序找
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        // 找不到返回-1
        return -1;
    }

10. isEmpty方法

     public boolean isEmpty() {
        return size == 0;
    }

11.toArray()

ArrayList提供了2个toArray()函数：

Object[] toArray() ：会抛出“java.lang.ClassCastException”异常，其返回的是 Object[] 数组，将 Object[] 转换为其它类型(如如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。

T[] toArray(T[] contents)：正常返回 T[]

   public Object[] toArray() {
      return Arrays.copyOf(elementData, size);
  }
  public <T> T[] toArray(T[] a) {
      if (a.length < size)
          // Make a new array of a's runtime type, but my contents:
          return (T[]) Arrays.copyOf(elementData, size, a.getClass());
      System.arraycopy(elementData, 0, a, 0, size);
      if (a.length > size)
          a[size] = null;
      return a;
  }

12. subList()

如果我们在开发过程中有需要获取集合中的某一部分的数据进行操作，我们可以通过使用SubList（）方法来进行获取，这里会创建ArrayList 的一个内部类 SubList（）。
SubList 继承了 AbstractList，并且实现了大部分的 AbstractList 方法。
需要注意的是，SubList 返回的集合中的某一部分数据，是会与原集合相关联。即当我们对Sublist 进行操作的时候，其实还是会影响到原始集合。所以在使用subList方法时，一定要想清楚，是否需要对子集合进行修改元素而不影响原有的list集合。
```
  public void add(int index, E e) {
          rangeCheckForAdd(index);
          checkForComodification();
          // 调用了原集合parent
          parent.add(parentOffset + index, e);
          this.modCount = parent.modCount;
          this.size++;
      }
```
13. 常见问题

13.1 如何扩容
如果使用的是无参构造器，则初始elementData的容量为0，第一次添加时，扩容elementData为10（默认值），如果再次扩容，则为1.5倍。

如果使用的是指定大小的构造器，初始elementData容量为指定大小（也要判断指定大小是否是0，如果是0，会走if (newCapacity - minCapacity < 0）判断将值改为1），如果需要扩容，则直接扩容为1.5倍。

13.2 ArraysList频繁扩容导致性能下降，如何处理

public static void main(String[] args) {
      ArrayList<String> list = new ArrayList<>();
      long start = System.currentTimeMillis();
      for (int i = 0; i < 100000; i++) {
          list.add(i + " ");
      }
      long end = System.currentTimeMillis();
      System.out.println(end - start + " ms");
  }

29 ms

解决方式：使用带参数的构造方法

23 ms

13.3 ArrayList插入或删除元素一定比LinkedList慢么

不一定，数组越靠后，效率越高，因为移动的次数少了

public static void main(String[] args) {
      ArrayList<String> list = new ArrayList<>(100000);
      for (int i = 0; i < 5000000; i++) {
          list.add(i + " ");
      }
      long start = System.currentTimeMillis();
      list.remove(1000000);
      long end = System.currentTimeMillis();
      System.out.println("arraylist: "+ (end - start) + " ms");
      LinkedList<String> linkedList = new LinkedList<>();
      for (int i = 0; i < 5000000; i++) {
          linkedList.add(i+" ");
      }
      long start1 = System.currentTimeMillis();
      linkedList.remove(1000000);
      long end1 = System.currentTimeMillis();
      System.out.println("linkedlist: "+ (end1 - start1) + " ms");
  }

arraylist: 1 ms
linkedlist: 24 ms

13.4 ArrayList是线程安全的么？

不是。加synchronized可以。或者使用Vector。

13.5 如何复制某个ArrayList到另一个ArrayList中去？

使用clone方法
使用ArrayList方法
使用addAll方法

14. 自定义ArrayList
```java public class MyArrayList {

private Object[] elementData; private int size;

private Object[] emptyArray = {};

private final int DEFAULT_CAPACITY = 10;

public MyArrayList() {
    elementData = emptyArray;
}
// add方法
public boolean add(E e) {
    // 校验扩容
    grow();
    elementData[size++] = e;
    return true;
}
// 简单扩容
private void grow() {
    if (elementData == emptyArray) {
        // 第一次扩容
        elementData = new Object[DEFAULT_CAPACITY];
    }
    //如果size == 集合存储元素数组的长度
    if (size == elementData.length) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}
public E set(int index, E element) {
    // 校验index
    checkIndex(index);
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}
public E remove(int index) {
    checkIndex(index);
    E oldValue = (E) elementData[index];
    int cnt = size - index - 1;
    if (cnt > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, cnt);
    }
    elementData[--size] = null;
    return oldValue;
}
public int size() {
    return size;
}
public E get(int index) {
    checkIndex(index);
    return (E) elementData[index];
}
private void checkIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("索引越界");
    }
}
@Override
public String toString() {
    if (size == 0) {
        return "[]";
    }
    StringBuilder sb = new StringBuilder("[");
    for (int i = 0; i < size; i++) {
        if (i == size - 1) {
            sb.append(elementData[size-1]).append("]");
        }else {
            sb.append(elementData[i]).append(", ");
        }
    }
    return sb.toString();
}

} ```

ArrayList

0. JDK1.7

1. 相关参数

1.1 常量