Java源码分析 - ArrayList动态数组列表源码分析

所谓的ArrayList就是传说中的动态数组了,这个类提供了动态增减元素的功能。List 接口的大小可变数组的实现,而ArrayList则实现了这个接口。

接下来我们就找几个ArrayList中的方法的源代码进行分析。

查看ArrayList的构造函数:

public ArrayList() {
this(10);
}

这里继续调用:

public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException(“Illegal Capacity: “+
initialCapacity);
this.elementData = new Object[initialCapacity];
}

这里的elementData为ArrayList中定义的一个数组:

private transient Object[] elementData;

可以发现:ArrayList本质上是一个Object类型的数组。

继续查看set(int, E)方法的源代码:

/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
RangeCheck(index);

E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}

这个函数中首先调用了RangeCheck():

private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
“Index: “+index+”, Size: “+size);
}

此函数用于检查当前请求插入的位置是否越界了,如果越界则抛出异常;如果没越界则继续执行,给elementData数组赋值并返回插入位置原来的值。

这里使用了泛型,返回原来的值时先进行了转换。这是因为在JDK1.5之后引入了泛型,所以在使用泛型限定ArrayList中存放的对象具体类型。如果不使用泛型,则可以存放任何类型的对象。这里推荐使用泛型。使用了泛型之后,下面的代码将会提示错误:

ArrayList list = new ArrayList();
list.add(new Integer(1));
list.add(“arthinking”);

可以发现:使用泛型后的ArrayList只能存放同一类型的对象(也可以不适用泛型存放不同类型的对象)。

继续查看ArrayList的add(E)方法:

/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return true (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

这里首先调用了ensureCapacity()函数:

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}

首先移动数组下标到需要插入的位置:modCount++;

然后判断插入位置的下标值是否越界了,如果越界则扩充数组size*3/2+1,然后使用copyOf(Object[] original, int newLength);把旧的数组复制到新的数组中。

接下来执行:elementData[size++] = e;把对象存入elementData[size],然后再执行size+1操作。

可以发现:ArrayList的容量是动态扩充的。当数组容量不足是,则使用(oldCapacity * 3)/2 + 1;规则扩充原来的数组为原来的1.5倍加1。

继续查看ArrayList的contains(Object):

/**
* Returns true if this list contains the specified element.
* More formally, returns true if and only if this list contains
* at least one element e such that
* (o==null ? e==null : o.equals(e)).
*
* @param o element whose presence in this list is to be tested
* @return true if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

这里简单的调用了indexOf(Object)函数:

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;
}

如果查找的是null时,如果elementData中含有null的话也会返回下标值。如果没有找到则返回-1。

可以得出:可以查找ArrayList是否包含null。如果没有查找到元素则返回-1。

继续查看ArrayList的remove(int):

/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
RangeCheck(index);

modCount++;
E oldValue = (E) elementData[index];

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[–size] = null; // Let gc do its work

return oldValue;
}

首先仍然是调用RangeCheck(iint)方法判断需要删除的位置是否越界,如果越界则抛出异常。

接下来是先保存需要删除位置的值,然后计算删除元素后需要往前移动的元素个数:size - index – 1,然后调用void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法把删除元素的后面的所有元素依次往前移动一个位置。

ArrayList的删除元素的时间开销是比较大的,每删除一个元素都要调整整个数组,总的时间复杂度为O(n)。

可以发现Arraylist的删除元素时间开销比较大。

继续查看ArrayList的addAll(Collection<? extends E>):

/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection’s Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return true if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

首先把需要附加的Collection转化为数组,然后调用ensureCapacity(int)动态扩充elementData数组。

最后通过void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法把数组复制elementData数组的后面。更新size变量。返回值为是否插入了元素。

这里调用了.Arrays.copyOf(Object[] original, int newLength, Class<? extends Object[]> newType)和void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length),时间开销比较大。

可以发现ArrayList添加整个数组的时候时间开销比较大。

★ ArrayList本质上是一个Object类型的数组。 ★ 使用泛型后的ArrayList只能存放同一类型的对象(也可以不适用泛型存放不同类型的对象)。 ★ ArrayList在当遇到容量不足时动态扩充。 ★ 可以查找ArrayList是否包含null。如果没有查找到元素则返回-1。 ★ Arraylist的删除元素时间开销比较大。 ★ ArrayList添加整个数组的时候时间开销比较大。

arthinking wechat
欢迎关注itzhai公众号