public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
该源码分析基于Java 1.8
ArrayList继承AbstractList实现的接口有List<E>, RandomAccess, Cloneable, java.io.Serializable。
其中List接口定义了列表必须实现的方法。
其中RandomAccess是一个标记接口,标记该接口是否是随机存取的,如果随机存取采用
for typical instances of the class, this loop: * <pre> * for (int i=0, n=list.size(); i < n; i++) * list.get(i); * </pre> * runs faster than this loop: * <pre> * for (Iterator i=list.iterator(); i.hasNext(); ) * i.next(); * </pre>
第一种的效率大于第二种遍历效率。
而Serializable表示ArrayList可以序列化。
Cloneable接口实现对象的浅拷贝,元素本身不会被复制。
/** * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The * elements themselves are not copied.) * * @return a clone of this <tt>ArrayList</tt> instance */ public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
ArrayList初始化:
private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; //ArrayList初始化时传入容量为0时 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //初始化时未传入参数 transient Object[] elementData; // non-private to simplify nested class access 存放ArrayList容器内容的Object数组 private int size; //Arraylist包含元素个数 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; } 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; } }
上面源码需要注意的是: 被transient 标记的Object[] elementData,用transient关键字标记的成员变量不参与序列化过程。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。
elementData用来存储ArrayList中的元素对象,ArrayList中的增删改查都是居于elementData实现的。
ArrayLis在初始化时,提供了3中形式,第一种根据传入的initialCapacity的值设置elementData对象。第二种使用默认的构造函数创建ArrayList,将elementData设置为
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是一个空的Object数组。第三种根据传入的Collection集合,先调用c.toArray()将集合转换成Object[]数组返回给elementData。
下面分析下ArrayList的常用方法:
get方法
public E get(int index) { rangeCheck(index); return elementData(index); } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
该方法根据传入的index获取该位置的元素,首先需要检查index是否越界。最后返回elementData(index)
set方法
public E set(int index, E element) { rangeCheck(index); //越界检查 E oldValue = elementData(index);//存储旧值 elementData[index] = element;//设置新值 return oldValue; // 返回新值 }
private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
该方法修改ArrayList中index位置的element,返回该位置原来的值。
add方法: 有两个具体在源码中分析
第一种在ArrayList末尾添加一个元素:
区别一些概念: 元素个数=ArrayList.size() , 而elementData数组长度 = ArrayList的容量。
public boolean add(E e) { ensureCapacityInternal(size + 1); // 修改elementData数组大小 elementData[size++] = e; //添加元素,修改size值(该值记录ArrayList列表中元素个数) return true; }
private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //判断elemenData类型,具体看构造函数初始化时的设置 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //比较ArrayList元素大小+1与默认值10比较,取大的一个作为参数 } ensureExplicitCapacity(minCapacity); //确定数组的大小,数组最小值为minCapacity } private void ensureExplicitCapacity(int minCapacity) { modCount++; //该字段标记列表修改的次数 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); //修改elementData数组 }
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//原数组长度 int newCapacity = oldCapacity + (oldCapacity >> 1);// 新数组长度,增长大小为oldCapacity >> 1 if (newCapacity - minCapacity < 0) //如果新数组长度小于minCapacity 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); //复制数组 }
第二种在index位置插入元素:
这种插入方法与第一种在elemetData数组扩充调用方法相同,不同点在源码指出
public void add(int index, E element) { rangeCheckForAdd(index); //判断Index是否存在越界,所谓的越界不是数组下标越界,而是与数组中的元素个数进行判断 ensureCapacityInternal(size + 1); // Increments modCount!! 与上一种方法相同 System.arraycopy(elementData, index, elementData, index + 1,//调用native方法进行数组拷贝,从elementData的index位置开始,拷贝到elementData size - index); // index+1位置,拷贝个数为size - index elementData[index] = element; //然后将index位置值设置为element size++; } private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
remove方法:
public E remove(int index) {//该方法根据index位置删除节点 rangeCheck(index);//index是否越界 modCount++; //列表改变次数+1 E oldValue = elementData(index); //被删除元素值 int numMoved = size - index - 1; //删除需要移动数组元素次数 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,//数组elementData的元素从index+1位置都需要前移一位,移动个数为numMoved numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }
第二种remove方法:
该方法是根据元素来删除的,首先判断是否为空,两种处理方式。具体见源码注释
public boolean remove(Object o) { if (o == null) { //删除元素为空 for (int index = 0; index < size; index++) if (elementData[index] == null) { //查找到元素为空的数组index 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,//与上面删除index下的元素相同 numMoved); elementData[--size] = null; // clear to let GC do its work 须设为空,GC更好回收 }
clear()方法:清空ArrayList中的元素,设置size=0; 当时elementData数组的大小不发生改变
public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
lastIndexOf(Object o)方法:获取最后一个包括o元素的数组下标,返回结果。遍历时从数组最后一个元素开始向前遍历,
为什么要分成o==null 和 o!=null, 因为null没有equals方法,而elementData不能保证其中的元素没有null,o也不能保证不为null。
public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
trimToSize()方法:修改elementData数组的大小,是elementData数组大小等于size
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
indexOf(Object o)方法: 查找元素o在ArrayList中的位置,返回该位置。
判断方法还是分成两种,null和非num,当没有找到时返回-1
public int indexOf(Object o) { 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; } return -1; }
关于迭代器问题到时候单独一篇博客来讲解。