- public class ArrayList extends AbstractList implements List,
- 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:
- *
- *
- for (int i=0, n=list.size(); i < n; i++)
- * list.get(i);
- *
- * runs faster than this loop:
- *
- *
- for (Iterator i=list.iterator(); i.hasNext(); )
- * i.next();
- *
第一种的效率大于第二种遍历效率。
而 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(Collectionextends 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;
- }
关于迭代器问题到时候单独一篇博客来讲解。
来源: http://www.cnblogs.com/huangyichun/p/6547804.html