1 概述

ArrayList实现了List接口
  
  
  
  
  ，是 顺序容器  
  
  
  
  
 ，允许放入null元素 有一个容量(capacity)
 


 


 


 


 


，表示底层数组的实际大小
  
  
  
  
  。如果容量不足
 
 
 
 
 ，容器会 自动增大底层数组的大小 支持泛型   
   
   
   
   
 ，泛型擦除后
 

 

 

 

 

，容器的元素都是 Object类型 ArrayList没有实现同步(synchronized)

 

 

 

 

 ，因此它是 线程不安全的  
  
  
  
  
 。（vector线程安全） 关于数组：一旦数组初始化完成           ，则长度不可改变 因此ArrayList扩容时会涉及数组的拷贝

2 底层数据结构

两个重要成员变量

Object[] elementData：

存储列表元素的数组；该数组的长度就是列表的容量

列表的容量是指它所能存储元素的最大个数 size：

列表的大小
 


 


 


 


 


。指当前列表包含的元素个数
 
 

 
 

 
 

 
 

 
 

，跟容量不是一个概念

size 跟 elementData数组长度是不一样的
 
 
 
 
 。elementData 允许长度大于元素的个数

transient Object[] elementData; //存储列表元素的数组 private int size;//元素的数量 protected transient int modCount = 0; //list的修改次数

3 构造函数

有三个构造函数：

指定初始容量大小时









，创建一个容量为参数的Object数组                ，并赋值给数据数组 不指定初始容量大小时 
 
 
 
 
 
 
 
 
 
，数据数组赋值为一个无限容量的空数组 构造参数为集合类型















，将参数转换成Object类型数组          ，并赋值给数据数组 注意  
 
  
 
  
 
  
 
  
 
 ，只有当第一次add元素时










，才会指定数组的长度

参照源码：

//指定初始容量大小时
  
  
  
  
  ，创建一个容量为参数的Object数组  
  
  
  
  
 ，并赋值给数据数组 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); } } // 不指定初始容量大小时
 


 


 


 


 


，数据数组赋值为一个无限容量的空数组 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 构造参数为集合类型
 
 
 
 
 ，将参数转换成Object类型数组   
   
   
   
   
 ，并赋值给数据数组 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }

4 自动扩容

添加元素时
 

 

 

 

 

，会判断添加后是否超出当前数组长度

 

 

 

 

 ，超出则会执行数组扩容； 数组扩容时           ，会将老数组中的元素重新 拷贝一份到新的数组中   
   
   
   
   
 。（因为数组长度不可变
 
 

 
 

 
 

 
 

 
 

，因此需要创建新数组） 数组执行扩容









，扩容后的容量为扩容前的 1.5倍 尽可能评估所需要容量的大小                ，避免扩容
 

 

 

 

 

。（因为扩容占用更多的内存）

参考源码:

重点！！！！！：添加前 
 
 
 
 
 
 
 
 
 
，都判断是否需要扩容：（如果size+1后















，超过elementData的长度          ，则执行扩容  
 
  
 
  
 
  
 
  
 
 ，扩容为原来的1.5倍）

public boolean add(E e) { ensureCapacityInternal(size + 1); // size 初始化时是0










， elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //计算所需容量:第一次添加时
  
  
  
  
  ，容量为10；反则  
  
  
  
  
 ，容量为当前长度+1 private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次添加时
 


 


 


 


 


，数组长度变为10 } return minCapacity;//如果数组不为空时
 
 
 
 
 ，最小长度是当前长度+1 } //再次计算数组所需容量 private void ensureExplicitCapacity(int minCapacity) { modCount++;//列表修改次数递增 //所需容量大于数组的长度,则执行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容   
   
   
   
   
 ，数组的内存状态已经发生变化了 private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);// 新的长度为旧长度的1.5倍 【右移1位（除以2）】 if (newCapacity - minCapacity < 0) // 如果扩容后的长度小于所需要的最小长度
 

 

 

 

 

，则使用最小长度(基本不会发生) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) //这里是极限的情况

 

 

 

 

 ，即逼近数组分配的最大内存空间 newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); // 执行数组拷贝 }

5 set() get() remove()

set()方法也就变得非常简单           ，直接对数组的指定位置赋值即可

 

 

 

 

 。 public E set(int index, E element) { rangeCheck(index);//下标越界检查 E oldValue = elementData(index); elementData[index] = element;//赋值到指定位置
 
 

 
 

 
 

 
 

 
 

，复制的仅仅是引用 return oldValue;//返回原先位置上的元素 } get()方法同样很简单









，唯一要注意的是由于底层数组是Object[]                ，得到元素后需要进行类型转换           。 public E get(int index) { rangeCheck(index); return (E) elementData[index];//注意类型转换 } remove()方法也有两个版本 
 
 
 
 
 
 
 
 
 
，一个是remove(int index)删除指定位置的元素















，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素
 
 

 
 

 
 

 
 

 
 

。删除操作是add()操作的逆过程          ，需要将删除点之后的元素向前移动一个位置









。需要注意的是为了让GC起作用  
 
  
 
  
 
  
 
  
 
 ，必须显式的为最后一个位置赋null值                。 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; //清除该位置的引用










，让GC起作用 return oldValue; }

6 Fail-Fast机制

ArrayList也采用了快速失败的机制
  
  
  
  
  ，通过记录 modCount 参数来实现 
 
 
 
 
 
 
 
 
 
。在面对并发的修改时  
  
  
  
  
 ，迭代器很快就会完全失败
 


 


 


 


 


，而不是冒着在将来某个不确定时间发生任意不确定行为的风险















。