ArrayList源码学习-阿里云开发者社区

ArrayList是一种以数组实现的列表，而数组的优势在于有角标，因此查询的速度较快，是一种可以动态扩容的数组。我们着重了解添加、获取、替换、删除操作。

一、相关变量信息

//默认初始化容量为10privatestaticfinalintDEFAULT_CAPACITY=10;
//为空数组实例准备一个空数组{}privatestaticfinalObject[] EMPTY_ELEMENTDATA= {};
//默认容量空元素数据，添加数组是会重新分配容量privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA= {};
//元素数据，存放元素的数组，重要，操作数据用的都是它transientObject[] elementData; // non-private to simplify nested class access//ArrayList大小privateintsize;

二、构造函数

//构造一个空的带特定初始化容量的listpublicArrayList(intinitialCapacity) {
//如果初始化容量>0，创建一个带特定容量的数组if (initialCapacity>0) {
this.elementData=newObject[initialCapacity];
//如果初始化容量为0，空元素数组    } elseif (initialCapacity==0) {
this.elementData=EMPTY_ELEMENTDATA;
    } else {
//否者抛异常thrownewIllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}
//构造一个空列表同时带有初始化容量0，默认初始化容量publicArrayList() {
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//将传入集合的元素初始化到ArrayList中publicArrayList(Collection<?extendsE>c) {
//集合转数组elementData=c.toArray();
//如果长度不为0if ((size=elementData.length) !=0) {
/*** 如果c.toArray()不是数组的话，* 采用arrays中的方法copyOf(U[] original, int newLength, Class<? extends T[]> newType)* 将其转成数组**/if (elementData.getClass() !=Object[].class)
elementData=Arrays.copyOf(elementData, size, Object[].class);
    } else {
//否者size=0,将c.toArray()替换成空数组this.elementData=EMPTY_ELEMENTDATA;
     }
  }

三、方法

(1)元素添加操作

添加元素：我们可以思考，如果让你添加元素，你会考虑什么？第一考虑容量是否充足，第二是进行元素的添加。

publicbooleanadd(Ee) {
//确保容量够ensureCapacityInternal(size+1);  // Increments modCount!!//进行元素添加elementData[size++] =e;
returntrue;
}
//进行容量确保是否够，不够则进行扩容privatevoidensureCapacityInternal(intminCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量privatestaticintcalculateCapacity(Object[] elementData, intminCapacity) {
//如果数组为空，则直接返回默认容量if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
returnMath.max(DEFAULT_CAPACITY, minCapacity);
    }
//否者返回需要的容量returnminCapacity;
}
//进行扩容操作privatevoidensureExplicitCapacity(intminCapacity) {
modCount++;
//进行扩容if (minCapacity-elementData.length>0)
grow(minCapacity);
}
//进行扩容操作privatevoidgrow(intminCapacity) {
//老的容量intoldCapacity=elementData.length;
//新的容量=老容量+老的容量做位运算向右移一位，也即1.5倍intnewCapacity=oldCapacity+ (oldCapacity>>1);
//如果新容量比需要的容量小，则将新容量变为需要容量if (newCapacity-minCapacity<0)
newCapacity=minCapacity;
//如果新容量比最大容量，则使用最大容量// MAX_VALUE=>@Native public static final int   MAX_VALUE = 0x7fffffff;  //2^31-1//private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; =>2^31-9if (newCapacity-MAX_ARRAY_SIZE>0)
newCapacity=hugeCapacity(minCapacity);
//将数据转移到新的数组中elementData=Arrays.copyOf(elementData, newCapacity);
}

添加元素到指定位置

//添加元素到指定位置publicvoidadd(intindex, Eelement) {
//检查index索引是否越界rangeCheckForAdd(index);
//看容量是否够，确保容量够用ensureCapacityInternal(size+1);  // Increments modCount!!/*** public static native void arraycopy(*          Object src,  int  srcPos,Object dest, int destPos,int length);* 进行数据拷贝，这样做的目的是为了将index的位置空出来，添加元素*/System.arraycopy(elementData, index, elementData, index+1,
size-index);
//在index位置添加元素elementData[index] =element;
//list长度+1size++;
}

进行addAll操作：

//将集合c中所有元素添加到当前ArrayList中publicbooleanaddAll(Collection<?extendsE>c) {
//将传入的集合转换为数组Object[] a=c.toArray();
//获取集合转成数组之后的长度intnumNew=a.length;
//看容量是否够ensureCapacityInternal(size+numNew);  // Increments modCount//将c中元素拷贝到arraylist中System.arraycopy(a, 0, elementData, size, numNew);
//长度+添加元素长度size+=numNew;
returnnumNew!=0;
}

进行addAll操作添加元素到指定位置：

//将集合c中所有元素添加到当前ArrayList中publicbooleanaddAll(Collection<?extendsE>c) {
//将传入的集合转换为数组Object[] a=c.toArray();
//获取集合转成数组之后的长度intnumNew=a.length;
//看容量是否够ensureCapacityInternal(size+numNew);  // Increments modCount//将c中元素拷贝到arraylist中System.arraycopy(a, 0, elementData, size, numNew);
//长度+添加元素长度size+=numNew;
returnnumNew!=0;
}

进行addAll操作添加元素到指定位置：

//将集合c中所有元素添加到当前ArrayList中publicbooleanaddAll(intindex, Collection<?extendsE>c) {
//检查是否越界rangeCheckForAdd(index);
//将传入的集合c转成数组Object[] a=c.toArray();
//获取长度intnumNew=a.length;
//进行容量检查，如果容量不够，则进行扩容ensureCapacityInternal(size+numNew);  // Increments modCount//需要移动的元素个数intnumMoved=size-index;
//如果需要移动的个数大于0，则需要移动元素，并进行添加操作，size加上移动的数量if (numMoved>0)
System.arraycopy(elementData, index, elementData, index+numNew,
numMoved);
//将元素拷贝到index位置System.arraycopy(a, 0, elementData, index, numNew);
size+=numNew;
returnnumNew!=0;
}

默认的初始容量为10。是否需要扩容，会先计算容量。如果数组为空，则直接返回默认容量10。如果需要容量>数组长度，则进行扩容。如果需要容量比老容量要大，则需要进行扩容1.5倍，采用位运算实现，也就是15。如果新容量比最大容量大，则采用默认的最大容量,为2^31-9。最后将数据转移到新的数组中。而添加元素到指定位置，会先检查是否越界，接着会看容量是否够，不够，则进行扩容，接着进行数据拷贝，空出index位置，将元素放入到指定的index位置，同时size+1。

(2)get操作

获取指定位置的元素

publicEget(intindex) {
//检查是否越界rangeCheck(index);
//返回指定位置元素returnelementData(index);
}
@SuppressWarnings("unchecked")
EelementData(intindex) {
//获取元素return (E) elementData[index];
}

(3)替换操作

//在特定位置替换你想要替换的元素publicEset(intindex, Eelement) {
//检查越界rangeCheck(index);
//获取老的元素EoldValue=elementData(index);
//将其替换成新的元素elementData[index] =element;
//返回老的值returnoldValue;
}

(4)删除操作

删除特定元素操作

//删除特定的元素publicEremove(intindex) {
//检查index是否越界rangeCheck(index);
modCount++;
//获取要删除的值EoldValue=elementData(index);
//需要进行移动数据的个数intnumMoved=size-index-1;
//进行移动操作,将其之后的元素都向前移动一位if (numMoved>0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] =null; // clear to let GC do its work//返回要删除的值returnoldValue;
}

删除第一次出现的元素

//删除指定的第一次出现的元素，如果没有出现，则不做修改publicbooleanremove(Objecto) {
//是否为空if (o==null) {
//遍历元素，进行对指定的索引进行置空操作for (intindex=0; index<size; index++)
if (elementData[index] ==null) {
//删除元素fastRemove(index);
returntrue;
            }
    } else {
//遍历元素，进行对指定的索引进行删除for (intindex=0; index<size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
returntrue;
            }
    }
returnfalse;
}
//删除元素privatevoidfastRemove(intindex) {
modCount++;
//删除元素的个数intnumMoved=size-index-1;
//进行移位操作if (numMoved>0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] =null; // clear to let GC do its work    }

删除包含和特定元素相同的所有元素，类似求差集

//删除包含c集合的元素publicbooleanremoveAll(Collection<?>c) {
//进行非空校验Objects.requireNonNull(c);
//不为空，执行批量删除操作returnbatchRemove(c, false);
}
//进行批量删除操作privatebooleanbatchRemove(Collection<?>c, booleancomplement) {
finalObject[] elementData=this.elementData;
//采用双指针 r是读指针，w是写指针intr=0, w=0;
booleanmodified=false;
try {
for (; r<size; r++)
//如果集合c中包含元素，如果是true，则true==true则进行写入if (c.contains(elementData[r]) ==complement)
elementData[w++] =elementData[r];
    } finally {
//保留与AbstractCollection的行为兼容性，// 即使c.contains（）抛出异常也是如此。if (r!=size) {
//如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后System.arraycopy(elementData, r,
elementData, w,
size-r);
w+=size-r;
        }
if (w!=size) {
//将写指针之后的元素置置空，方便GC操作// clear to let GC do its workfor (inti=w; i<size; i++)
elementData[i] =null;
modCount+=size-w;
size=w;
modified=true;
        }
    }
returnmodified;
}

删除包含c集合的元素：首先这里采用了双指针的方法。类似元素匹配。删除不包含c集合的所有元素，类似求交集

//移除不包含特定元素的所有的元素publicbooleanretainAll(Collection<?>c) {
//非空校验Objects.requireNonNull(c);
//进行批量删除操作returnbatchRemove(c, true);
}

四、总结

因此我们可以得到以下信息：

从操作上看，我们可以知道其实际上是在操作数组，而操作完之后将其采用arrayCopy的方式放入到arrayList中。同时我们可以知道其默认容量是10，如果不够的时候，会进行扩容，每次都是扩容成原来的1.5倍，采用位运算（右移动一位）进行扩容。

其进行添加元素的时候，会首先进行越界校验，如果没有越界才继续进行操作。接着查看容量是否够，不够的话，进行扩容操作，而扩容操作是在grow()方法中进行的。同时如果容量大于规定的最大容量2^31-9时，会默认为最大容量。

ArrayList源码学习