详解Java中的ArrayList

1 ArrayList实现的接口
ArrayList是动态数组，它其实就是Array的复杂版本。

从图中可以看出，ArrayList直接或间接的实现了Collection(一种无序集合)，List（存储有序），RandomAccess(随机访问)，Seralizable(可序列化），Iterable(可遍历)等接口，因此它的特性也是多种多样的，下面我们就要好好学习一下ArrayList。

2 ArrayList的特点

• 可以随机访问，效率很高。
• 查找速度一般，如果数组未经排序，查找速度和数组成正比。
• 追加元素效率很高。
• 插入和删除元素效率很低，主要原因是需要移动元素。

3 ArrayList的内部结构
要想深入了解ArrayList，必须知道它的成员变量，构造方法及其它方法。

3.1 ArrayList的成员变量

/**
* 默认初始化容量，大小为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
/**
* 实际的元素个数。
*/
private int size;

3.2 ArrayList的构造方法及其摘要

3.3 ArrayList的方法其摘要

4 基本原理
可以看出，ArrayList内部有一个数组elementData，一般会有一些预留的空间，有一个整数size记录实际的元素个数。下面列举几个方法，看看它们是如何实现的。

4.1 add方法的实现
add方法的主要代码为：

public boolean add(E e) {
ensureCapacityInternal(size + 1);
// Increments modCount!!
elementData[size++] = e;
return true;
}

它首先调用ensureCapacityInternal确保数组容量是足够的，ensureCapacityInternal的代码是：

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureCapacityInternal内部调用了 calculateCapacity方法，而calculateCapacity方法先判断数组是不是空的，如果是空的，则首次至少要分配的大小为DEFAULT_CAPACITY，DEFAULT_CAPACITY的值为10，calculateCapacity方法代码如下：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

接下来调用了ensureExplicitCapacity方法，代码为：

private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

如果需要的长度大于当前数组的长度，则调用grow方法，grow方法的代码如下：

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

扩展倍数默认为原数组长度的1.5倍，如果还是小于minCapacity,就扩展为minCapacity。

4.2 remove方法的实现
下面来看一下ArrayList中remove方法是如何实现的，代码如下：

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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

它首先调用了rangeCheck方法，如果参数index大于size，就抛出IndexOutOfBoundsException（数组下标越界异常），rangeCheck代码如下:

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

在remove方法中，实际是调用了System.arraycopy方法来移动元素，然后size减1，并把最后一个位置设为null。

4.3 indexOf方法的实现
下面来看一下ArrayList中indexOf方法是如何实现的，代码如下：

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

这个方法通过通过equals方法来比较集合中和参数(Object)o是否相等，及判断是否含有此元素，并返回该元素的下标，如果不包含就返回-1。

5 迭代
ArrayList有迭代行为，比如：

import java.util.ArrayList;
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> userNameList =new ArrayList<String>();
userNameList.add("步惊云");
userNameList.add("林宝儿");
userNameList.add("桑月");
userNameList.add("赵不凡");
for (String u : userNameList) {
System.out.println(u);
}
}
}

运行结果如下：

步惊云
林宝儿
桑月
赵不凡

5.1 迭代的实现
Array实现了Iterable接口，Iterable代码如下：

public interface Iterable<T> {
/**
*
*返回一个iterator接口。
*/
Iterator<T> iterator();
}

这个方法是实现iterator方法。iterator方法声明如下：

public Iterator< E > iterator()

iterator方法返回一个iterator接口，其接口定义如下：

public interface Iterator< E > {
boolean hasNext();
E next();
void remove;
}

说明

5.2 迭代的补充
ArrayList中还有listIterator方法，它是对iterator方法的补充，listIterator方法实现了ListIterator接口，其接口增加了添加元素、修改元素、向前遍历，前后位置等方法。添加的方法有：

5.3 迭代的原理
下面通过代码来分析一下ArrauyLisst迭代的原理：

public Iterator<E> iterator（） {
return new Itr（）;
}

新建了一个Itr对象，Itr是一个成员内部类，实现了Iterator接口，声明为：

private class Itr implements Iterator<E>

它有三个实例成员变量，为：

int cursor; //下一个要返回的元素位置
int lastRet = -1; //最后一个返回的索引位置，如果没有，为-1
int expectedModCount = modCount;

cursor表示下一个要返回的元素位置，lastRet表示最后一个返回的索引位置，expected-ModCount表示期望的修改次数，初始化为外部类当前的修改次数modCount，回顾一下，成员内部类可以直接访问外部类的实例变量。每次发生结构性变化的时候modCount都会增加，而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同，这样就能检测出结构性变化。

我们来具体看下，它是如何实现Iterator接口中的每个方法的，先看hasNext（），代码为：

public boolean hasNext（） {
return cursor！= size;
}

cursor与size比较，比较直接，看next方法：

public E next（） {
checkForComodification（）;
int i = cursor;
if（i >= size）
throw new NoSuchElementException（）;
Object［］elementData = ArrayList.this.elementData;
if（i >= elementData.length）
throw new ConcurrentModificationException（）;
cursor = i ＋ 1;
return （E） elementData［lastRet = i］;
}

首先调用了checkForComodification，它的代码为：

final void checkForComodification（） {
if（modCount！= expectedModCount）
throw new ConcurrentModificationException（）;
}

所以，next前面部分主要就是在检查是否发生了结构性变化，如果没有变化，就更新cursor和lastRet的值，以保持其语义，然后返回对应的元素。remove的代码为：

public void remove（） {
if（lastRet < 0）
throw new IllegalStateException（）;
checkForComodification（）;
try {
ArrayList.this.remove（lastRet）;
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch （IndexOutOfBoundsException ex） {
throw new ConcurrentModificationException（）;
}
}

它调用了ArrayList的remove方法，但同时更新了cursor、lastRet和expectedModCount的值，所以它可以正确删除。不过，需要注意的是，调用remove方法前必须先调用next，比如，通过迭代器删除所有元素，直觉上，可以这么写：

public static void removeAll（ArrayList<Integer> list）{
Iterator<Integer> it = list.iterator（）;
while（it.hasNext（））{
it.remove（）;
}
}

实际运行，会抛出异常java.lang.IllegalStateException，正确写法是：

public static void removeAll（ArrayList<Integer> list）{
Iterator<Integer> it = list.iterator（）;
while（it.hasNext（））{
it.next（）;
it.remove（）;
（）;
}
}

当然，如果只是要删除所有元素，ArrayList有现成的方法clear（）。
listIterator（）的实现使用了另一个内部类ListItr，它继承自Itr，基本思路类似，我们就不赘述了。

最后

以上就是殷勤咖啡豆为你收集整理的详解Java中的ArrayList的全部内容，希望文章能够帮你解决详解Java中的ArrayList所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。