一文直接带你吃透 ArrayList

ArrayList 是日常开发中相当常见、面试也相当常考的一种 JDK 集合类，了解并熟悉、甚至能实现一个 ArrayList 对面试、提升自己编码功底大有益处。

一、写给小白 ArrayList 简单使用技巧

这部分是 ArrayList 的简单使用技巧，主要是介绍 ArrayList 的几个常见方法。

  1. /**
  2.  * 编写一个ArrayList的简单实用demo
  3.  * ArrayList 的常见方法包括：
  4.  *        add(element):添加元素
  5.  *        get(index):获取下标元素
  6.  *        remove(index):移除下标对应元素
  7.  *        set(index,element):将index处的元素修改为element
  8.  */
  9. public class arrayList {
  10.     public static void main(String[] args) {
  11.         // 创建 ArrayList 的对象
  12.         ArrayList al = new ArrayList();
  13.         // 添加元素
  14.         al.add("finky");
  15.         // 构造随机数并进行添加
  16.         Random rnd = new Random();
  17.         for (int i = 0; i < 20; i++) {
  18.             al.add(rnd.nextInt(1000));
  19.         }
  20.         // 取出ArrayList里的元素进行打印
  21.         for (int i = 0; i < al.size(); i++) {
  22.             System.out.print(al.get(i) + "  ");
  23.         }
  24.         // 修改0号index成的元素为doocs
  25.         System.out.println();
  26.         al.set(0, "doocs");
  27.         System.out.println(al.get(0));
  28.         // 移除“doocs”元素
  29.         al.remove(0);
  30.         System.out.println(al.get(0));
  31.     }
  32. }
  1. // 这是上面打印后的demo，可以看到第0处下标元素先是修改成了doocs，进行移除后，第0处下标元素变成了912
  2. finky  912  922  284  305  675  565  159  109  73  298  491  920  296  397  358  145  610  190  839  845
  3. doocs
  4. 912

二、ArrayList 的源码分析

我们来看看 ArrayList 的源码：

1、来看看 ArrayList 的初始化：

  1. // ArrayList 初始化时默认大小为10
  2. private static final int DEFAULT_CAPACITY = 10;
  4. // 直接初始化的话一个空数组
  5. private static final Object[] EMPTY_ELEMENTDATA = {};
  7. // 初始化ArrayList,传入初始化时的大小
  8. public ArrayList(int initialCapacity) {
  9.     if (initialCapacity > 0) {
  10.         this.elementData = new Object[initialCapacity];
  11.     } else if (initialCapacity == 0) {
  12.         this.elementData = EMPTY_ELEMENTDATA;
  13.     } else {
  14.         throw new IllegalArgumentException("Illegal Capacity: "+
  15.                                             initialCapacity);
  16.     }
  17. }
  18. // 如果不传入大小的话就默认大小是10，那么这里就有一个问题：我们上面插入的元素超过了10，继续插入元素就会进行拷贝扩容，性能不是特别高。所以我们一般情况下初始化时给定一个比较靠谱的数组大小，避免到时候导致元素不断拷贝
  19. public ArrayList() {
  20.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  21. }

总结一下 ArrayList 初始化：我们创建 ArrayList 对象时，如果没有传入对应的大小，就会默认创建一个元素大小为 10 的数组，下次插入元素超过 10 时，会进行数组的拷贝扩容，这样性能消耗太高，所以建议就是在初始化时给定一个不要太小的容量大小。==

2、 ArrayList 的 add 方法：

先上add 方法的代码：

  1. public boolean add(E e) {
  2.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  3.     elementData[size++] = e;
  4.     return true;
  5. }
  7. public void add(int index, E element) {
  8.     rangeCheckForAdd(index);
  9.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  10.     System.arraycopy(elementData, index, elementData, index + 1,
  11.                         size - index);
  12.     elementData[index] = element;
  13.     size++;
  14. }
  16. public void add(E e) {
  17.     checkForComodification();
  18.     try {
  19.         int i = cursor;
  20.         ArrayList.this.add(i, e);
  21.         cursor = i + 1;
  22.         lastRet = -1;
  23.         expectedModCount = modCount;
  24.     } catch (IndexOutOfBoundsException ex) {
  25.         throw new ConcurrentModificationException();
  26.     }
  27. }
  29. private void rangeCheck(int index) {
  30.     if (index < 0 || index >= this.size)
  31.         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  32.     }
  33. }

arraylist添加集合的方法

先判断当前数组元素是否满了，如果塞满了就会进行数组扩容，随后进行数组拷贝。

再然后插入元素，同时对应的 index++。

3、瞧瞧 ArrayList 的 set 方法：

  1. public E set(int index, E element) {
  2.     rangeCheck(index);
  3.     E oldValue = elementData(index);
  4.     elementData[index] = element;
  5.     return oldValue;
  6. }
  8. public void set(E e) {
  9.     if (lastRet < 0)
  10.         throw new IllegalStateException();
  11.     checkForComodification();
  13.     try {
  14.         ArrayList.this.set(lastRet, e);
  15.     } catch (IndexOutOfBoundsException ex) {
  16.         throw new ConcurrentModificationException();
  17.     }
  18. }

1、先进行 index 判断是否越界，如果没有越界的话获取原来的旧的值

2、进行替换并返回该位置原来的旧的值

4、ArrayList 的 get 方法：

  1. public E get(int index) {
  2.     rangeCheck(index);
  3.     checkForComodification();
  4.     return ArrayList.this.elementData(offset + index);
  5. }

进行 index 是否越界的判断，然后去取对应下标的值。

5、ArrayList 的 remove 方法：

  1. public void remove() {
  2.     if (lastRet < 0)
  3.         throw new IllegalStateException();
  4.     checkForComodification();
  6.     try {
  7.         ArrayList.this.remove(lastRet);
  8.         cursor = lastRet;
  9.         lastRet = -1;
  10.         expectedModCount = modCount;
  11.     } catch (IndexOutOfBoundsException ex) {
  12.         throw new ConcurrentModificationException();
  13.     }
  14. }
  16. public E remove(int index) {
  17.     // 进行index是否越界的判断
  18.     rangeCheck(index);
  19.     checkForComodification();
  20.     E result = parent.remove(parentOffset + index);
  21.     this.modCount = parent.modCount;
  22.     this.size--;
  23.     return result;
  24. }
  26. public E remove(int index) {
  27.     rangeCheck(index);
  28.     modCount++;
  29.     E oldValue = elementData(index);
  30.     int numMoved = size - index - 1;
  31.     if (numMoved > 0)
  32.         System.arraycopy(elementData, index+1, elementData, index,
  33.                             numMoved);
  34.     elementData[--size] = null;
  35.     return oldValue;
  36. }

arrayList删除元素的过程.png

1、先进行下标是否越界的判断，获取 index 处的元素值（这是要删除的值）

2、然后进行元素拷贝，把 index 后面的元素往前拷贝

6、关于 ArrayList 动态扩容和数组拷贝：

  1. private void ensureCapacityInternal(int minCapacity) {
  2.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  3. }
  5. private void ensureExplicitCapacity(int minCapacity) {
  6.     modCount++;
  7.     if (minCapacity - elementData.length > 0)
  8.         grow(minCapacity);
  9. }
  11. private void grow(int minCapacity) {
  12.     // overflow-conscious code
  13.     int oldCapacity = elementData.length;
  14.     // 扩容的代码：这里做了位运算，相当于数组扩容了1.5倍
  15.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  16.     if (newCapacity - minCapacity < 0)
  17.         newCapacity = minCapacity;
  18.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  19.         newCapacity = hugeCapacity(minCapacity);
  20.     // 随后进行元素拷贝
  21.     elementData = Arrays.copyOf(elementData, newCapacity);
  22. }

现在假定场景：arraylist 中已经有 10 个元素类，要放第 11 个元素。

此时进行容量检测，出现问题：空间大小不够。

解决方法：此时进行数组扩容右位移 1（相当于总容量多加 1.5 倍）扩容，老的大小+老大小的一半，进行元素拷贝

三、来仿照 JDK 源码写一个自己的 ArrayList 把

  1. public class OwnArrayList<E> {
  2.     private E data[];
  3.     private int size;
  5.     public OwnArrayList(int capacity) {
  6.         data = (E[]) new Object[capacity];
  7.         size = 0;
  8.     }
  9.     //   初始化是默认设置大小为20
  10.     public OwnArrayList() {
  11.         this(20);
  12.     }
  14.     //    获取数组容量
  15.     public int getCapacity() {
  16.         return data.length;
  17.     }
  19.     //    获取数组元素个数
  20.     public int getSize() {
  21.         return size;
  22.     }
  24.     //    判断数组是否为空
  25.     public boolean isEmpity() {
  26.         return size == 0;
  27.     }
  29.     // 获取index索引位置的元素
  30.     public E get(int index) {
  31.         if (index < 0 || index >= size)
  32.             throw new IllegalArgumentException("add failed,the index should >= 0 or <= size");
  33.         return data[index];
  34.     }
  36.     // 修改index索引位置的元素为e
  37.     public void set(int index, E e) {
  38.         if (index < 0 || index >= size)
  39.             throw new IllegalArgumentException("add failed,the index should >= 0 or <= size");
  40.         data[index] = e;
  41.     }
  43.     //    在数组中间插入一个元素
  44.     public void add(int index, E element) {
  45.         if (size == data.length) {
  46.             throw new IllegalArgumentException("AddLast failed,array has already full");
  47.         }
  48.         if (index < 0 || index > size) {
  49.             throw new IllegalArgumentException("add failed,the index should >= 0 or <= size");
  50.         }
  51.         for (int i = size - 1; i >= index; i--) {
  52.             data[i + 1] = data[i];
  53.         }
  54.         data[index] = element;
  55.         size++;
  56.     }
  58.     //    向数组元素末尾添加一个元素
  59.     public void addLast(E element) {
  60.         add(size,element);
  61.     }
  63.     //    在数组头部插入一个元素
  64.     public void addFirst(E element) {
  65.         add(0, element);
  66.     }
  68.     // 判断是否含有元素
  69.     public boolean contains(E e) {
  70.         for (int i = 0; i < size; i++)
  71.             if (data[i] == e)
  72.                 return true;
  73.         return false;
  74.     }
  76.     // 查找元素e的位置
  77.     public int find(E e) {
  78.         for (int i = 0; i < size; i++) {
  79.             if (data[i] == e) {
  80.                 return i;
  81.             }
  82.         }
  83.         return -1;
  84.     }
  86.     // 删除index位置的元素
  87.     public E remove(int index) {
  88.         if (index < 0 || index > size) {
  89.             throw new IllegalArgumentException("index should be 0 to size");
  90.         }
  91.         E remove_element = data[index];
  92.         for (int i = index + 1; i < size; i++) {
  93.             data[i - 1] = data[i];
  94.         }
  95.         size--;
  96.         return remove_element;
  97.     }
  99.     // 删除末尾元素
  100.     // 注意：这是逻辑删除，但是size的大小已经做了相应的减少，所以从实际意义上我们外界并不能访问到末尾元素的值
  101.     public E removelast() {
  102.         return remove(size - 1);
  103.     }
  105.     // 删除开头元素
  106.     public E removeFirst() {
  107.         return remove(0);
  108.     }
  110.     // 将数组空间的容量变成newCapacity大小
  111.     private void resize(int newCapacity) {
  112.         newCapacity = getCapacity()*2;
  113.         E[] newData = (E[]) new Object[newCapacity];
  114.         for (int i = 0; i < size; i++)
  115.             newData[i] = data[i];
  116.         data = newData;
  117.     }
  118. }

四、面试时关于 ArrayList 要说的事

如果有人问你 ArrayList 知多少，我觉得可以从这几个方面出发：

ArrayList 的底层是基于数组进行的，进行随机位置的插入和删除、以及扩容时性能很差，但进行随机的读和取时速度却很快。

接着可以从源码的角度分析 add、remove、set、get、数组扩容拷贝的过程场景。

最后也是特别重要的一点，就是要积极掌握主动性，延伸出 LinkedList 的特点、源码、两者间的对比等。

注：当需要动态数组时我们通常使用 ArrayList 而不是使用类似的 vector，这里有一点说明一下，就是尽管 Vector 的方法都是线程安全的，但其在单线程下需要花费的时间更多，而 ArrayList 尽管不是线程安全的，但其花费的时间很少。

终：参考资料

  1. JDK 集合框架 ArrayList 源码
  2. 《Core.Java.Volume.I.Fundamentals.11th.Edition》