ArrayList是工作中常用的集合, 基于数组实现, 可以插入空数据, 也支持随机访问. ArrayList比较适合 get/set操作, 因为 add/remove需要移动数据, 相对来说比较消耗性能.

默认初始长度

1.默认初始长度为 10
2.底层结构为Object[] 数组

  1. private static final int DEFAULT_CAPACITY = 10;
  2. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  3. /**
  4.  * 构造一个初始容量为10的空列表
  5.  */
  6. public ArrayList() {
  7.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  8. }

添加方法 add()

  1. 向数组中添加元素, 流程如下

    1. /**
    2. * 将指定的元素追加到此列表的末尾.
    3. */
    4. public boolean add(E e) {
    5.  // 扩容
    6.  ensureCapacityInternal(size + 1);  // Increments modCount!!
    7.  // 添加元素
    8.  elementData[size++] = e;
    9.  return true;
    10. }

    2.扩容过程

    1. transient Object[] elementData;
    2. // 扩容
    3. private void ensureCapacityInternal(int minCapacity) {
    4.  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    5. }
    6. // 计算容量, elementData为空 则使用默认容量 10, 指定容量
    7. private static int calculateCapacity(Object[] elementData, int minCapacity) {
    8.  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    9.      return Math.max(DEFAULT_CAPACITY, minCapacity);
    10.  }
    11.  return minCapacity;
    12. }
    13. // 修改次数自增, 并且如果 新的长度-原长度>0 则使用 grow(minCapacity)方法进行扩容
    14. private void ensureExplicitCapacity(int minCapacity) {
    15.  modCount++;
    16.  // overflow-conscious code
    17.  if (minCapacity - elementData.length > 0)
    18.      grow(minCapacity);
    19. }

  2. 添加元素赋值

    1. elementData[size++] = e;

    扩容流程 grow(minCapacity)

    通过扩容流程可以看出扩容过程中, 是将创建一个原数组1.5倍大小的新数组, 同时将数组元素复制到新数组, 所以一般使用中, 尽量指定数组大小, 从而避免数组的复制.

    1. /**
    2. * 增加容量确保能容纳 minCapacity 数量的元素
    3. */
    4. private void grow(int minCapacity) {
    5.  // overflow-conscious code
    6.  // 获取当前 elementData 的长度
    7.  int oldCapacity = elementData.length;
    8.  // 获取新的长度 为当前长度的 1.5倍
    9.  int newCapacity = oldCapacity + (oldCapacity >> 1);
    10.  // 比较并交换
    11.  if (newCapacity - minCapacity < 0)
    12.      newCapacity = minCapacity;
    13.  // 防止超出最大长度
    14.  if (newCapacity - MAX_ARRAY_SIZE > 0)
    15.      newCapacity = hugeCapacity(minCapacity);
    16.  // minCapacity is usually close to size, so this is a win:
    17.  // 数组复制
    18.  elementData = Arrays.copyOf(elementData, newCapacity);
    19. }

    删除 remove 方法

    删除过程中使用 System.arraycopy 本地方法, 对数组进行复制, 所以 ArrayList的 新增和删除方法性能不如, LinkList, 但是 get和set方法, 则直接根据索引修改数据, 比较适合对数据进行修改的操作.

    1. /**
    2. * 删除指定位置的元素, 后面的元素将前移
    3. */
    4. public E remove(int index) {
    5.  // 检查索引 否则抛出 IndexOutOfBoundsException(outOfBoundsMsg(index))
    6.  rangeCheck(index);
    7.  // 修改次数自增
    8.  modCount++;
    9.  E oldValue = elementData(index);
    10.  int numMoved = size - index - 1;
    11.  if (numMoved > 0)
    12.      // 数组复制
    13.      System.arraycopy(elementData, index+1, elementData, index,
    14.                       numMoved);
    15.  elementData[--size] = null; // clear to let GC do its work
    16.  return oldValue;
    17. }
    18. /**
    19. * 删除指定元素
    20. */
    21. public boolean remove(Object o) {
    22.  if (o == null) {
    23.      for (int index = 0; index < size; index++)
    24.          if (elementData[index] == null) {
    25.              fastRemove(index);
    26.              return true;
    27.          }
    28.  } else {
    29.      for (int index = 0; index < size; index++)
    30.          if (o.equals(elementData[index])) {
    31.              fastRemove(index);
    32.              return true;
    33.          }
    34.  }
    35.  return false;
    36. }
    37. /**
    38. * System.arraycopy 方法拷贝 删除
    39. */
    40. private void fastRemove(int index) {
    41.  modCount++;
    42.  int numMoved = size - index - 1;
    43.  if (numMoved > 0)
    44.      System.arraycopy(elementData, index+1, elementData, index,
    45.                       numMoved);
    46.  elementData[--size] = null; // clear to let GC do its work
    47. }