一、基本概念
arraylist是一个可以添加对象元素，并进行元素的修改查询删除等操作的容器类。arraylist底层是由数组实现的，所以和数组一样可以根据索引对容器对象所包含的元素进行快速随机的查询操作，其时间复杂度为o(1)。但是和数组不同的是，数组对象创建后数组长度是不变的，arraylist对象创建后其长度是可变的，所以arraylist也称为动态数组，那么arraylist的动态数组数据结构又是如何实现的呢?接下来打开arraylist源码看看。
二、源码分析
2.1、arraylist类的继承与实现
图2.1 arraylist类的继承与实现（不包括继承arraylist的类）
《java的四个标记接口serializable、cloneable、randomaccess和remote接口》 进行了总结
2.2、arraylist的属性
我要评论 private static final long serialversionuid = 8683452581122892189l;//用于arraylist对象序列化的版本id
private static final int default_capacity = 10;//arraylist对象的默认容量大小
private static final object[] empty_elementdata = {};//用于null的arraylist对象
private static final object[] defaultcapacity_empty_elementdata = {};//用于创建一个默认容量大小的arraylist对象
transient object[] elementdata; //用于创建动态大小的arraylist对象，这个实例变量引用的数组可以说就是arraylist容器
private int size;//arraylist对象的尺寸
2.3、arraylist类的三个构造函数
一个无参构造函数，一个传入一个int 量指定容量的构造函数和一个传入一个容器对象来进行初始化的构造函数
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);
}
}
//指定arraylist初始容量的构造器
public arraylist() {
this.elementdata = defaultcapacity_empty_elementdata;
}
//一个默认容量的arraylist无参构造器
public arraylist(collection<? extends e> c) {
elementdata = c.toarray();
if ((size = elementdata.length) != 0) {
if (elementdata.getclass() != object[].class)
elementdata = arrays.copyof(elementdata, size, object[].class);
} else {
this.elementdata = empty_elementdata;
}
}
//一个参数为一个容器对象的构造器，将该容器对象转化为一个数组对象后，将arraylist对象内的数组引用elementdata初始化为这个数组对象（object[]）
2.4、arraylist动态数组的具体实现细节
arraylist对象创建后，是怎么改变这个对象的容量实现动态数组的呢，来看看动态数组实现的几个重要方法
private static final int max_array_size = integer.max_value - 8;//int整型的最大值减8
private void grow(int mincapacity) {
int oldcapacity = elementdata.length;//原arraylist对象的容量
int newcapacity = oldcapacity + (oldcapacity >> 1);//新的容量变为原容量+原容量/2,也就是新的容量增大为原来的1.5倍
if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
//新的容量如果还是小于指定容量，则新容量的值更新为指定容量
if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
//如果新容量大于int整数的最大值减8的值，则调用hugecapacity(mincapacity)，新的容量为interger.max_value,即最大的int整数
elementdata = arrays.copyof(elementdata, newcapacity);
//创建一个数组长度为newcapacity，包含所有原arraylist内elementdata所有元素的新的elementdate数组
private static int hugecapacity(int mincapacity) {
if (mincapacity < 0) // overflow
throw new outofmemoryerror();
return (mincapacity > max_array_size) ?
integer.max_value :
max_array_size;
}
public void trimtosize() {
modcount++;
if (size < elementdata.length) {
elementdata = (size == 0)? empty_elementdata: arrays.copyof(elementdata, size);
}
//当size小于elementdata，如果size=0，令elementdata为一个空数组；size>0,使elementdate数组变量指向包含原elememtdata所有元素，且长度为元素个数size的新数组
}
private void ensureexplicitcapacity(int mincapacity) {
modcount++;
if (mincapacity - elementdata.length > 0)
grow(mincapacity);
}
public void ensurecapacity(int mincapacity) {
int minexpand = (elementdata != defaultcapacity_empty_elementdata) ? 0: default_capacity;
if (mincapacity > minexpand) {
ensureexplicitcapacity(mincapacity);
}
}
private void ensurecapacityinternal(int mincapacity) {
ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
private static int calculatecapacity(object[] elementdata, int mincapacity) {
if (elementdata == defaultcapacity_empty_elementdata) {
return math.max(default_capacity, mincapacity);
/*arraylist类调用无参构造器初始化后，elementdata数组初始化为defaultcapacity_empty_elementdata（一个空对象数组object{}），若elementdate为初始化的值这里返回的是默认容量和mincapacity中的较大值*/
}
return mincapacity;//若elementdate不是初始化的值，这个方法直接返回mincapacity的值
}
public void add(int index, e element) {
rangecheckforadd(index);//先检测索引是否越界
ensurecapacityinternal(size + 1); //确保arraylist的容量，即elementdata数组的长度，在添加元素前大于size+1
system.arraycopy(elementdata, index, elementdata, index + 1,
size - index);
//将从index处以及后面的元素的都向后移动一位，索引+1。所以调用这个方法的时间复杂度为o(n)
elementdata[index] = element;
//将元素element添加到索引为index的位置
size++;//元素个数加一
}
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);
//将这个元素后面的元素的前移一位，索引减一，原来index处的元素（要被删除的元素）被后面一位的元素覆盖。所以这个方法的时间复杂度为o(n)
elementdata[--size] = null;
//数组索引为size处没有元素，使其为空，元素个数size-1
return oldvalue;
//将删除的元素作为方法的返回值
}
（arraylist还有很多其他的方法，以上是arraylist实现动态数组的主要方法，arraylist类其他的方法在这里就不一一赘述了）
（小官原创，若有谬误，望各位大佬批评指正）
（转载请注明出处）
如对本文有疑问， 点击进行留言回复！！
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时，滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论