Java ArrayList底层的数据结构是数组，但是Java的数组需要提前知道大小，这也是我们不用数组的原因，ArrayList位于包java.util，这也是我们用的最多的包之一。
我们使用idea打开ArrayList源码，并按ALT+7会看到ArrayList所有的方法，如下图所示：
这里针对JDk1.8讲解ArrayList的源码，其它版本会略有不同。
ArrayList初始化
transient Object[] elementData; // non-private to simplify nested class access
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 构造一个初始容量为initialCapacity参数的数组，且initialCapacity大于0
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 构造一个初始容量为10的初始数组。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}在上面的代码中我们发现，ArrayList的初始化就是Java的数组elementData，其中elementData 定义为数组Object[] elementData。
- 无参数初始化：虽然注解里面说的是初始化容量为10的数组，但是我们发现初始值是{}，后面会动态扩容，当首次添加数组元素时，它才会扩容为10。
- 有参数初始化：initialCapacity必须>=0,否则会抛出IllegalArgumentException异常。
ArrayList扩容
//判断容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY
}
return minCapacity;
}
//扩展函数的入口
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正的扩展数组的函数
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//位移运算扩展为1.5倍
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);
}在上面代码中，ensureCapacityInternal 是扩展函数的入口方法，真正的扩容方法是grow()，它使用Arrays.copyOf(elementData, newCapacity)函数扩容。
Arrays的copyOf()方法传回的数组是新的数组对象，改变传回数组中的元素值，不会影响原来的数组。
- 通过Math.max(DEFAULT_CAPACITY, minCapacity)知道，当第一次即空数组的时候容量设置为10。
- 扩容的函数的Array.copyOf()，由公式代码 newCapacity=oldCapacity + (oldCapacity >> 1) 得出，每次增加1.5倍。
这里面试的时候可能会问到ArrayList数组增加的效率和ArrayList是否可以作为队列？
ArrayList增加
ArrayList增加元素有两种方法：
/**
*将指定的元素追加到此列表的末尾。
*
* @param 要附加到此列表的e元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 在指定位置插入指定元素
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} 上面是ArrayList添加元素的代码，它有两种方式。
- 第一种情况是将元素添加到ArrayList末尾，这种情况很简单就是数组的元素的添加操作，通过ensureCapacityInternal函数判断添加元素后是否操作数组的大小。
- 第二种情况是在指定位置添加元素，而它是通过函数System.arraycopy来实现的，关于Java中System.arraycopy函数意义请参考这里。或者直接参考例子：Java System.arraycopy函数例子
ArrayList移除
ArrayList移除有多种方法。
/**
* 删除此列表中指定位置的元素。
* 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 = 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;
}
/**
* 从该列表中删除第一次出现的指定元素 * if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
/**
* 删除此列表中的所有元素。
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}从上面的代码中我们看到ArrayList移除元素有3种方法。
- 删除此列表中指定位置的元素，它和添加元素一样，是通过函数System.arraycopy来实现的，关于Java中System.arraycopy函数意义请参考这里。
- 从该列表中删除第一次出现的指定元素，同样是使用System.arraycopy函数来实现。
- 删除所有元素，它使用的方法是直接置为null;
总结
以上是ArrayList代码中的简单讲解，通过查看ArrayList源码，我们可以解决Java中一些ArrayList面试题。更多函数可以使用idea打开ArrayList源码查看。