L
L
LearnJava
Search…
Java集合之ArrayList
从源码看初始化以及增删查改,学习ArrayList。
先来看下ArrayList定义的几个属性:
1
private static final int DEFAULT_CAPACITY = 10;
2
private static final Object[] EMPTY_ELEMENTDATA = {};
3
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
4
transient Object[] elementData; // 保存对象
5
private int size; // ArrayList的长度
Copied!
从这里可以看到ArrayList内部使用数组实现的。

一. 初始化

1. ArrayList()
无参的构造器:
1
/**
2
* Constructs an empty list with an initial capacity of ten.
3
*/
4
public ArrayList() {
5
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6
}
Copied!
可以看到这个构造器初始化了一个空数组。这里有个疑问,就是注释明明说是构造了一个长度为10的数组,其实这是在添加第一个元素的时候才进行的扩充。
2. ArrayList(int initialCapacity)
指定长度的构造器:
1
/**
2
* Constructs an empty list with the specified initial capacity.
3
*
4
* @param initialCapacity the initial capacity of the list
5
* @throws IllegalArgumentException if the specified initial capacity
6
* is negative
7
*/
8
public ArrayList(int initialCapacity) {
9
if (initialCapacity > 0) {
10
this.elementData = new Object[initialCapacity];
11
} else if (initialCapacity == 0) {
12
this.elementData = EMPTY_ELEMENTDATA;
13
} else {
14
throw new IllegalArgumentException("Illegal Capacity: "+
15
initialCapacity);
16
}
17
}
Copied!
这个构造器显式的指明了数组的长度,其实如果小于10的话,在添加第一个元素的时候还是会扩充到长度为10的数组。

二. 增加元素

1. add(E e)
1
/**
2
* Appends the specified element to the end of this list.
3
*
4
* @param e element to be appended to this list
5
* @return <tt>true</tt> (as specified by {@link Collection#add})
6
* 添加指定的元素到List的末尾
7
*/
8
public boolean add(E e) {
9
ensureCapacityInternal(size + 1); // 扩充数组长度
10
elementData[size++] = e; // 最后一个赋值为e
11
return true;
12
}
Copied!
那么它是如何扩充数组长度的呢?追踪代码来到grow(int minCapacity)方法:
1
/*
2
* 可以看到它是通过Arrays.copyOf方法将原数组拷贝到了一个数组长度为newCapacity的新数组里面
3
*/
4
private void grow(int minCapacity) {
5
// overflow-conscious code
6
int oldCapacity = elementData.length;
7
int newCapacity = oldCapacity + (oldCapacity >> 1);
8
if (newCapacity - minCapacity < 0)
9
newCapacity = minCapacity;
10
if (newCapacity - MAX_ARRAY_SIZE > 0)
11
newCapacity = hugeCapacity(minCapacity);
12
// minCapacity is usually close to size, so this is a win:
13
elementData = Arrays.copyOf(elementData, newCapacity);
14
}
Copied!
2. add(int index, E element)
1
/**
2
* 在指定的位置添加一个元素
3
*/
4
public void add(int index, E element) {
5
rangeCheckForAdd(index); // 检查index是否合法
6
7
ensureCapacityInternal(size + 1); // 扩充数组长度
8
System.arraycopy(elementData, index, elementData, index + 1,
9
size - index); // 通过拷贝返回一个新数组
10
elementData[index] = element;
11
size++;
12
}
Copied!
这里用到了System类的arraycopy方法,它的用法如下:
System. arraycopy(Object src, int srcPos, Object dest, int destPos,int length)
src:原数组;
srcPos:源数组要复制的起始位置;
dest:目标数组;
destPos:目标数组放置的起始位置;
length:复制的长度
这个方法也可以实现自身的复制。上面的就是利用了自身赋值的特性进行数组的拷贝。相当于将index后面的所有元素后移了一位,将新元素插入到index位置。

三. 删除元素

1. remove(int index)
1
/*
2
* 和add(int index, E element)类似,使用System.arraycopy进行自身拷贝,相当于将index后面的元素
3
* 像前移动了一位,覆盖掉需要删除的元素,将最后一个元素置位null,等待JVM自动回收
4
*/
5
public E remove(int index) {
6
rangeCheck(index);
7
8
modCount++;
9
E oldValue = elementData(index);
10
11
int numMoved = size - index - 1;
12
if (numMoved > 0)
13
System.arraycopy(elementData, index+1, elementData, index,
14
numMoved);
15
elementData[--size] = null; // clear to let GC do its work
16
17
return oldValue;
18
}
Copied!
2. remove(Object o)
1
/*
2
* 先通过for循环找到o所在的位置,再通过fastRemove(index)移除,实现方法和remove(int index)一样
3
*/
4
public boolean remove(Object o) {
5
if (o == null) {
6
for (int index = 0; index < size; index++)
7
if (elementData[index] == null) {
8
fastRemove(index);
9
return true;
10
}
11
} else {
12
for (int index = 0; index < size; index++)
13
if (o.equals(elementData[index])) {
14
fastRemove(index);
15
return true;
16
}
17
}
18
return false;
19
}
Copied!

四. 查找元素

1
/*
2
* 查找元素就比较简单了,直接通过数组的下角标进行返回
3
*/
4
public E get(int index) {
5
rangeCheck(index);
6
7
return elementData(index);
8
}
Copied!

五. 修改元素

1
/*
2
* 修改元素也比较简单,直接通过数组的下角标进行赋值
3
*/
4
public E set(int index, E element) {
5
rangeCheck(index);
6
7
E oldValue = elementData(index);
8
elementData[index] = element;
9
return oldValue;
10
}
Copied!

总结

从源码可以看到,ArrayList以数组方式实现,查找和修改的性能比较好,增加和删除的性能就比较差了。
Last modified 1yr ago