大话顺序结构之ArrayList

上篇回顾

上一篇中讲解了线性表的相关概念，通过上一篇文章，希望可以对线性表有一个基本的认识。本篇开始讲述线性表的顺序表是怎么实现的。

先来看一下顺序表的继承关系，这是一个简图。

image.png

1. ArrayList

首先试想一下，我们如此熟悉的ArrayList,如果要你去实现， 你会怎么做？
答案是用数组。那么数组和集合的区别是什么呢？
1） 数组的长度是固定的，我们初始化一个数组，或者指定长度或者指定元素（同样指定了长度）
2） 集合的长度是动态规范的， 我们初始化一个集合，从来不需要处理长度相关的问题
3）数组是没法添加元素的， 集合可以无限制的从尾部添加新元素

其实仔细对比一下，可以发现， 删除一个元素， 修改一个元素， 查询一个元素等功能无论在数组还是ArrayList中实现方式都是一样的，什么？别告诉我在数组里怎么实现你不会。那么就剩下了添加一个元素，从以上的3条对比可以发现， ArrayList与数组的主要区别就在于添加一个元素，如何实现在尾部添加？ 如何实现扩容？ 其实ArrayList的核心可以讲的东西有两点扩容和移位。

这里我们把查询与修改的实现一笔带过；添加与删除涉及到移位，先讲移位再将删除；添加涉及到扩容，最后讲添加。至于最后的判空啊， 获取长度啊，我相信是不用说的。

ArrayList的实现

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
// Android-note: Also accessed from java.util.Collections
transient Object[] elementData; // non-private to simplify nested class access


上面提到过， ArrayList的内部数据存储采用数组的形式｛$elementData｝，而当我们初始化一个ArrayList时，我们会得到一个默认长度是10的数组。

ArrayList的查询

/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}


查询的实现从看到源码的瞬间就不用说了，谁不会的话，自己去打屁屁吧。 这里第一步是参数的校验， 这是一个优秀的编码习惯，值得我们去学习。一个全面的，有效的参数校验可以一定程度上保证代码的健康。什么时候需要抛异常，什么时候返回默认值也是个值得推敲的问题。

ArrayList的修改

/**
* 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) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}


同查询，普普通通的赋值操作，不值一提。不过可以稍微注意下，返回的值，是未修改之前的原值。

移位

ArrayList是线性表中顺序表的经典结构之一，顺序表的特点是连续的顺序的空间；因此当一个元素添加或删除后，ArrayList会如何做呢？删除之后，对应位置的元素会是空？ 当然不是； 一个数组元素已经排位完毕，如何插入一个元素？答案是移位。

1.什么是移位？

当ArrayList插入或移除一个元素时， 指定元素之后的元素会统一向前或向后移动一个位置，称之为移位。那么先官方的解释一下！ 假设有一个数组，如下

[0, 1, 2, 3, 4, 5, 6]


对应的位置存储着对应的数字， 此时我想在位置[4]处插入一个元素7,那么插入后的数组是

[0, 1, 2, 3, 7, 4, 5, 6]


我们根据这个现象观察ArrayList的插入操作。首先， 找到位置[4], 然后[4]后面的元素统一后移1位，最后在位置[4]插入指定的元素7。通俗的解释就是像我们日常排队，我们已经排好了一个队伍，这时候领导来了，当然让领导先嘛是不是，这时候我们要所有人往后退一步，腾出第一个位置，领导插进来，皆大欢喜。如图

image.png

再看来下删除操作。如果我想删除元素4，那么删除后的数组是

[0, 1, 2, 3, 5, 6]


我们根据这个现象观察ArrayList的删除操作。首先，找到元素4,位于位置[4]，然后删除4， 最后[4]后面的元素统一往前移。还是以排队为例，我们已经排好了一个队伍，忽然队伍中的小王来大姨妈了，要去一趟卫生室。那么后面的人肯定要往前占据小王的位置的，不要说你的生活中不是这样的，你说了我也不信。如图

image.png

通过以上两个例子，我想应该都明白了什么是移位吧。那么我们开始来撸一下代码。

ArrayList的删除

/**
* 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) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(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; // clear to let GC do its work
return oldValue;
}


我们直接来看一下核心的删除实现。首先取到待删除值，这个是要返回的； numMoved是什么鬼？看名字就知道了吧，移动的数量，用于判断是否需要执行移位操作；如果没有需要移动的，比如删除最后一个元素，那么很明显就不用移位了嘛，因为移动的位置是从index + 1开始的。

上面提过，数组是长度是固定不变的，如果我想加一个元素到数组，你是怎么做的？ 重新创建一个length+1的数组。 这里是通过arraycopy方法来将index(待删除元素的位置) + 1到最后一个元素复制到一个新书组中。
解析下这个API

public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
src: 现有的数组
srcPos: 从现有数组第几个开始复制
dest: 目标数组，要复制到哪个数组下
destPos: 复制到目标数组的开始位置
length: 复制多少个元素


总结一下以上方法，就是把现在数组从index+1开始到最后一个元素；整体复制到本数组中，复制元素从index开始。不好理解？还是以上面数组为例，原数组是

[0, 1, 2, 3, 4]


我想删除元素2， 那么我就把位置[2]后面的元素[3,4]复制到本数组中，从位置[2]开始放，如下
[0,1,3,4,2]
可以看出3和4从原来的位置[3]与位置[4], 移动到了位置[2]和位置[3]。 也就是把2后面的元素前移了一位。

再看源码的最后一句，最后一个元素置空。size是ArrayList的长度，删除后长度-1。 顺便看一下官方注释， 置空是为了释放最后一个元素的资源，因为最后一个元素不是ArrayList的有效元素了嘛。

好了，删除就说这么多，移位也不再多说了。添加元素是从尾部插入的，因此不需要位移的，前面提过；如果你需要向指定位置添加元素，OK, 还是需要移位的，不过方向与删除相反，也好理解。

ArrayList的添加与扩容

ArrayList的添加是从尾部开始的，因此不需要移位，这也是ArrayList比数组方便的原因之一。前面提到过，数组的长度是固定的，因此在添加元素时，我们要对数组进行扩容。那么扩容的策略如何，接下来看源码

/**
* 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) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}


一看啊呀代码怎么这么多，别慌！ 先看add方法，add方法只有两步： 1） 扩容 2） 扩容好了，尾插一个元素 我相信从数组最后插入一个元素不是困难的问题，size++, 扩容之后，数组的长度是+1的，无异议吧，因为插入一个元素。这个size++和之前的&＃8211;size可是不同的， 前者是后运算， 因此扩容后的数组长度成了size+1,而插入的位置是size, 也就是size++在调用的时候，尚未执行++操作。 而&＃8211;size正好相反，先运算，再调用。好的，来说下扩容

扩容

从以上添加代码可以看出，最终的扩容策略是在grow()中执行的。

int oldCapacity = elementData.length;


取出原数组的长度

int newCapacity = oldCapacity + (oldCapacity >> 1);


先执行系统的自动扩容， 扩容因子是(oldCapacity >> 1)。 这是一个位移运算，意思是右移1位。在二进制中，右移一位的意思自然是 / 2，因为二进制从左到右的位数越来越低。从右到左分别是2的0次方，2的1次方&＃8230;那如果左移也就是很明显是x2了。从这句话得出，系统的扩容因子是原数组长度的一半。

if (newCapacity - minCapacity <0)
newCapacity = minCapacity;


如果系统扩容后，还不足以插入新元素，别忘了ArrayList是有addAll()的， 插入一个军队，这就非同小可了。这时候扩容后的长度就是旧的数组长度 + 新增元素的长度。 再往下一句是一个边界判断，不用解释了吧。

elementData = Arrays.copyOf(elementData, newCapacity);


到了最后的最后，哎？还是这个套路， 把我现在的数组elementData扩展成为一个长度为newCapacity的数组，我们的扩容就完成了。

面试中可能对扩容策略有提问，所以最好记住这个系统的扩容因子以及最终是如何实现扩容的。ArrayList还有一个add(Element, index)的方法，无非是先实现扩容，然后再进行移位。以上两个核心点搞明白了，这些都不是事儿。

好了，ArrayList篇到这了，是不是很简单呢？ 这可是最简单的数据结构了。