线性表
定义：一个线性表是n个具有相同特性的数据元素的有限序列。
存储结构：线性表按存储结构划分主要分为顺序表和链表。
今天我们要分析的就是顺序表：
什么叫顺序表，举个简单的例子：我们去窗口买票，都是按先来后到排队，如果后来的人想要插队，那么后面的人的位置都得后移一位对不对。这种就是典型的顺序表，通过这个例子，大家有没有想到Java中哪种集合属于顺序表？没错，最典型的就是ArrayList。今天我们就要来分析一下ArrayList的源码。
在这里，我们主要分析ArrayList的增删改查方法。
首先我们分析一下它的数据结构：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
通过观察add方法，我们可以发现，ArrayList底层的数据结构是一个数组。我们知道，数组是需要指定长度的，而且数组的长度是固定的。那么，ArrayList的初始容量是多大呢？它又是如何实现扩容的呢？这是我在以往面试的过程中经常会被问到的问题。下面我们就来分析一下。
一.构造及add系列方法：
先看一下ArrayList的构造方法：
ArrayList有三个构造方法，先看一下无参构造：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
从上面可以看出，当我们new一个ArrayList的时候，实际上它是一个空集合。那么当我们向其中添加一个元素的时候，底层数组的容量变成多大了呢？
protected transient int modCount = 0;
private static final int DEFAULT_CAPACITY = 10;
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);
}
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
从上面可以看出，当开始为空list的时候，向其中添加一个元素，默认将数组扩容为10。然后将数组的第一个元素设为我们要添加的元素。
那么，当超过10的时候又是怎么扩容的呢？
int newCapacity = oldCapacity + (oldCapacity >> 1);
很简单，就是按照上面的公式来扩容的。
另外两种构造方法就不一一介绍了，原理其实是差不多。
分析了构造，我们再来分析一下ArrayList的增删改查方法：
add系列的方法上面在扩容的时候，基本上算是分析过了，
add系列有四个方法：
image.png
前面我们已经分析了第一个了，现在我们分析add（int，E）这个方法：
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
和之前一样，先确定一下数组数组的扩容，然后将对应index后面的元素往后移一位，然后将需要添加的元素放置在指定的index上。
剩下的addAll系列方法其实和add一样，只不过是先将对应的集合转换成数组，然后再添加。
二.remove系列方法：
前面分析了add方法，现在分析remove系列方法：
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;
}
可以看出，ArrayList移除对应索引元素的主要方式是将数组的元素分为两节，一节是index之前的元素，另一节是index之后的元素。copy一个相同的数组，然后将原数组后一节元素copy到新数组的对应的前一个索引位置，并将最后一个元素置空，然后将新数组赋给原数组。
再看一下remove（object）方法：
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;
}
可以看出，这个方法就是遍历数组中是否存在对应object，如果存在通过fastRemove方法移除对应索引元素并返回true，否则返回false。
三.set方法以及get方法：
set和get方法相对就简单一些，因为不涉及到数组的大小改变。这里就不介绍了，太简单了。
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;
}
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
小结：
通过上述源码分析，我们可以发现ArrayList具有一下特点：
优点：尾插效率高，支持随机访问。
缺点：中间插入或者删除效率低。
下一篇，我们将分析链表，并手写单链表。
网友评论