本版本基于android-19 sdk源码分析
本文章只分析android 中的arraylist源码.如果想看java中arraylist源码，请移步。
Arraylist的原理实现为数组，LinkedLIst的原理实现为链表。
数组的优点为查询快，添加删除慢。
链表的优点为添加删除快，查询慢。
Arraylist 构造方法：
Arraylist 有三个构造方法分别是：
public static final Object[] OBJECT = new Object[0];
public ArrayList() {
array = EmptyArray.OBJECT;
}
此方法给arraylist创建了一个长度为0的数组对象
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
此方法会判断传入的值是否小于0，如果小于0则抛出异常。
如果传入的值为0，则就像间接的调用了无参构造方法，为array赋值了一个长度为0的数组对象。
如果传入的值>0,则为array 创建一个指定长度大小的数组。
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
此方法会传入一个Collection对象，当传入对象为空，会抛出空指针异常。
当不为空，会通过collection.toArray()方法获取一个数组对象。
如果当前对象不是Object数组，需要创建一个大小长度为collection.toArray()的Object数组，并把collection.toArray()中数据copy到新的Object数组中。并把新数组赋值给array，size设置为数组长度。
/**
* The number of elements in this list.
*/
int size;
在看add和remove方法前先说一个值，这个值就是arraylist的size值，这个值我理解为当前列表中元素的数量
Add方法：
- 普通插入方法
@Override
public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
先获取记录的Object数组对象，和当前数组长度。
当现在数组对象大小和当前列表中元素数量相等时，需要进行扩容。
举个栗子：
- 当前数组是0时，s=0，a.length=0，这时候就走进了if里面。
(s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)，0<12/2, 那就创建了一个数组大小为0+12的新数组对象。把以前的数据拷贝到了新的数组对象中。数组的大小完成的扩容。 - 当前数组为12时，s=12,a.length=0,会进入if，
(s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)，12<12,创建了一个数组大小为12+6的新的数组对象，并把以前的数据拷贝到了新的数据对象中，完成了扩容。
s >> n 右移一个位，在原来的基础上除2的n次方。
s << n 左移一个位，在原来的基础上乘2的n次方。
扩容完成过后，把当前对象赋值给a[s]，size加一。
- 在指定位置加入对象
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
//如果当前传入值大于当前列表中元素数量，或者小于0抛出异常
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
//如果列表中元素数量 小于数组长度，不需要扩容
if (s < a.length) {
//index位置到-一个元素都后移一个位置
System.arraycopy(a, index, a, index + 1, s - index);
} else {
//当列表中元素数量大于等于数组长度，需要扩容，创建一个新的数组对象。
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
//先把原来数组从0-index拷贝到新数组
System.arraycopy(a, 0, newArray, 0, index);
//再把index-最后一个元素拷贝到新数组
System.arraycopy(a, index, newArray, index + 1, s - index);
//把新的数组赋值给array
array = a = newArray;
}
//给第index个位置赋值object
a[index] = object;
size = s + 1;
modCount++;
}
变换图如下：
image.png
Remove方法：
- 根据下标移除
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
//如果删除长度大于等于当前列表中元素的数量，抛出异常
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
//获取到第index个数组元素对象
@SuppressWarnings("unchecked")
E result = (E) a[index];
//把a数组的index+1到最后一个元素，拷贝到a数组的从index开始位置。并且s-1
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
- 根据对象移除
这里只分析object不为空的情况，因为原理一样。
@Override
public boolean remove(Object object) {
Object[] a = array;
int s = size;
for (int i = 0; i < s; i++) {
//当数组中存在此obj
if (object.equals(a[i])) {
//把a数组的i+1到最后一个元素，拷贝到a数组的从i开始位置。并且s-1
System.arraycopy(a, i + 1, a, i, --s - i);
//将最后一个元素置为空
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
return false;
}
变换图如下：
image.png
思考：
在源码中并没有看到相关同步锁的代码，Arraylist 不能处理好并发问题呢，如果想要解决数组的并发问题需要用什么类呢？
大家可以看看CopyOnWriteArrayList这个类是否可以满足上述需求！实现原理是什么呢？
网友评论