ArrayList是一种以数组实现的列表,而数组的优势在于有角标,因此查询的速度较快,是一种可以动态扩容的数组。我们着重了解添加、获取、替换、删除操作。
1.相关变量信息
//默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
//为空数组实例准备一个空数组{}
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量空元素数据,添加数组是会重新分配容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//元素数据,存放元素的数组,重要,操作数据用的都是它
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList大小
private int size;
//构造一个空的带特定初始化容量的list
public ArrayList(int initialCapacity) {
//如果初始化容量>0,创建一个带特定容量的数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//如果初始化容量为0,空元素数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
//否者抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//构造一个空列表同时带有初始化容量0,默认初始化容量
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//将传入集合的元素初始化到ArrayList中
public ArrayList(Collection<? extends E> c) {
//集合转数组
elementData = c.toArray();
//如果长度不为0
if ((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;
}
}
添加元素:我们可以思考,如果让你添加元素,你会考虑什么?第一考虑容量是否充足,第二是进行元素的添加。
public boolean add(E e) {
//确保容量够
ensureCapacityInternal(size + 1); // Increments modCount!!
//进行元素添加
elementData[size++] = e;
return true;
}
//进行容量确保是否够,不够则进行扩容
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);
}
//否者返回需要的容量
return minCapacity;
}
//进行扩容操作
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//进行扩容操作
private void grow(int minCapacity) {
//老的容量
int oldCapacity = elementData.length;
//新的容量=老容量+老的容量做位运算向右移一位,也即1.5倍
int newCapacity = 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-9
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//将数据转移到新的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
添加元素到指定位置
//添加元素到指定位置
public void add(int index, E element) {
//检查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长度+1
size++;
}
进行addAll操作:
//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
//将传入的集合转换为数组
Object[] a = c.toArray();
//获取集合转成数组之后的长度
int numNew = a.length;
//看容量是否够
ensureCapacityInternal(size + numNew); // Increments modCount
//将c中元素拷贝到arraylist中
System.arraycopy(a, 0, elementData, size, numNew);
//长度+添加元素长度
size += numNew;
return numNew != 0;
}
进行addAll操作添加元素到指定位置:
//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
//将传入的集合转换为数组
Object[] a = c.toArray();
//获取集合转成数组之后的长度
int numNew = a.length;
//看容量是否够
ensureCapacityInternal(size + numNew); // Increments modCount
//将c中元素拷贝到arraylist中
System.arraycopy(a, 0, elementData, size, numNew);
//长度+添加元素长度
size += numNew;
return numNew != 0;
}
进行addAll操作添加元素到指定位置:
//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(int index, Collection<? extends E> c) {
//检查是否越界
rangeCheckForAdd(index);
//将传入的集合c转成数组
Object[] a = c.toArray();
//获取长度
int numNew = a.length;
//进行容量检查,如果容量不够,则进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//需要移动的元素个数
int numMoved = 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;
return numNew != 0;
}
默认的初始容量为10。是否需要扩容,会先计算容量。如果数组为空,则直接返回默认容量10。如果需要容量>数组长度,则进行扩容。如果需要容量比老容量要大,则需要进行扩容1.5倍,采用位运算实现,也就是15。如果新容量比最大容量大,则采用默认的最大容量,为2^31-9。最后将数据转移到新的数组中。而添加元素到指定位置,会先检查是否越界,接着会看容量是否够,不够,则进行扩容,接着进行数据拷贝,空出index位置,将元素放入到指定的index位置,同时size+1。
获取指定位置的元素
public E get(int index) {
//检查是否越界
rangeCheck(index);
//返回指定位置元素
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
//获取元素
return (E) elementData[index];
}
//在特定位置替换你想要替换的元素
public E set(int index, E element) {
//检查越界
rangeCheck(index);
//获取老的元素
E oldValue = elementData(index);
//将其替换成新的元素
elementData[index] = element;
//返回老的值
return oldValue;
}
删除特定元素操作
//删除特定的元素
public E remove(int index) {
//检查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; // clear to let GC do its work
//返回要删除的值
return oldValue;
}
删除第一次出现的元素
//删除指定的第一次出现的元素,如果没有出现,则不做修改
public boolean remove(Object o) {
//是否为空
if (o == null) {
//遍历元素,进行对指定的索引进行置空操作
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//删除元素
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,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
删除包含和特定元素相同的所有元素,类似求差集
//删除包含c集合的元素
public boolean removeAll(Collection<?> c) {
//进行非空校验
Objects.requireNonNull(c);
//不为空,执行批量删除操作
return batchRemove(c, false);
}
//进行批量删除操作
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
//采用双指针 r是读指针,w是写指针
int r = 0, w = 0;
boolean modified = 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 work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
删除包含c集合的元素:首先这里采用了双指针的方法。类似元素匹配。删除不包含c集合的所有元素,类似求交集
//移除不包含特定元素的所有的元素
public boolean retainAll(Collection<?> c) {
//非空校验
Objects.requireNonNull(c);
//进行批量删除操作
return batchRemove(c, true);
}
因此我们可以得到以下信息:
从操作上看,我们可以知道其实际上是在操作数组,而操作完之后将其采用arrayCopy的方式放入到arrayList中。同时我们可以知道其默认容量是10,如果不够的时候,会进行扩容,每次都是扩容成原来的1.5倍,采用位运算(右移动一位)进行扩容。
其进行添加元素的时候,会首先进行越界校验,如果没有越界才继续进行操作。接着查看容量是否够,不够的话,进行扩容操作,而扩容操作是在grow()方法中进行的。同时如果容量大于规定的最大容量2^31-9时,会默认为最大容量。