1.ArrayList与LinkedList区别
| | ArrayList| LinkedList |
| :---: | :----: | :---: |
| 数据结构| Object数组| 双向链表|
| 线程安全| 否| 否|
| add时间复杂度| O（n）| O（1）|
| delete时间复杂度 | O（n）| O（1）|
| get时间复杂度| O（1）| O（n）|
| 快速访问| 支持| 不支持|
| 存储空间|默认空余一些空间|保存数据&前后指针|
RandomAccess
首先抛出一个问题，让我们带着问题，去了解真相。
1.数据结构是否有随机访问功能，是如何实现的？
2.数据结构是否有随机访问功能，取决于该接口？
3.该接口实现了具体的随机访问功能？
然而，事实好像并未如此，查看JDK源码，可知此接口中什么都没有定义和实现。
package java.util;
public interface RandomAccess {
}由此可知，RandomAccess 并非具体实现，而只是一个标识而已，标识实现了这个接口的类，具有随机访问的功能。
2.ArrayList 扩容机制
2.1 ArrayList 重要变量定义
//默认的容量大小
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
//arraylist的大小，并非是elementData大小
private int size;
//默认arraylist最大的容量，为int最大值减去8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2.2 ArrayList 初始化
无参初始化
//初始化为空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}含参（指定容量大小）初始化-
//initialCapacity想要初始化的大小
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果initialCapacity大于0，则直接以期望的大小，创建数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果initialCapacity等于0，则直接空数组赋值
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果initialCapacity小于0，则抛出初始化异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}含参（指定已有list数据）初始化
public ArrayList(Collection<? extends E> c) {
//将已知list转为array，直接赋值数组
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//规避已知的list不是对象数组，则强转为对象数组赋值
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}2.3 ArrayList 扩容
想要知道如何真正去实现扩容，我们需要抽丝剥茧，从最初的add看起
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}每次add时，都会去调用ensureCapacityInternal进行容量扩容检测，传入的期望的最小容量是当前arraylist大小+1
private void ensureCapacityInternal(int minCapacity) {
//如果当前对象数组就是空的，则最小的扩容大小应该是DEFAULT_CAPACITY，即10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果想要扩容的大小，大于当前对象数组的实际大小，则调用grow进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}如果想要扩容的大小，大于当前对象数组的实际大小，则调用grow进行扩容
private void grow(int minCapacity) {
// 得到现有数组的大小，将现有数组的大小除以2，然后加上当前大小，也就是现有数组大小的1.5倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容1.5倍之后的容量，依然达不到用户期望的大小，则直接用期望大小赋值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果扩容的大小，大于了MAX_ARRAY_SIZE ，则调用hugeCapacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将元素进行copy
elementData = Arrays.copyOf(elementData, newCapacity);
}由上诉代码分析可知，扩容首先默认扩容为当前容量的1.5倍，但是如果扩展之后的容量依然达不到期望的大小，则会直接以期望的大小去扩容。
当然了，在真正扩容之前，还需判断一下，目前得到的最终大小是否超过了arraylist的限制MAX_ARRAY_SIZE ，如果超过了，则直接赋值为Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE 。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}3.ArrayList 与 Vector区别和联系
老规矩，先上源码，通过源码对比一下，ArrayList 和 Vector源码类的定义
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{***}
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{***}由上可知，ArrayList和Vector都是list实现，而且实现的接口和拥有的功能几乎一致。
接下来，我们对比一下，具体功能的实现是否一致，以add举例
Vector add方法实现
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}ArrayListadd方法实现
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}对比可知，实现代码几乎一致，但是有一个细微区别，Vector 的方法上都加了synchronized 关键字，由此可知，Vector 是线程安全，ArrayList是非线程安全，其他功能和接口完全一致。
4.ArrayList ConcurrentModificationException异常
final void checkForComodification() {
if (ArrayList.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}我们看到在ArrayList的内部类Itr中（实现了Iterator接口），有一个检测方法，iterator遍历过程中，add、remove、next方法都会先调用这个函数，检测ArrayList.this.modCount != this.expectedModCount，问题来了，modCount是做什么的？
我们依然是通过源码来探究原因，看一下这个遍历在哪里调用了？
public E remove(int var1) {
this.rangeCheck(var1);
++this.modCount;
Object var2 = this.elementData(var1);
int var3 = this.size - var1 - 1;
if (var3 > 0) {
System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
}
this.elementData[--this.size] = null;
return var2;
}
private void ensureExplicitCapacity(int var1) {
++this.modCount;
if (var1 - this.elementData.length > 0) {
this.grow(var1);
}
}
public boolean add(E var1) {
this.ensureCapacityInternal(this.size + 1);
this.elementData[this.size++] = var1;
return true;
}我们看到在ArrayList的add、remove方法中，都对这个遍历进行了++操作，那立意就显而易见了，这个变量是为了记录ArrayList内部数组操作次数的。
那么为什么会报出这个异常呢？expectedModCount又是怎么来的，我们看到expectedModCount实际上是迭代器里面的一个变量，在通过迭代器进行list的操作时，expectedModCount = modCount，
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount;
Itr() {
this.expectedModCount = ArrayList.this.modCount;
}
public boolean hasNext() {
return this.cursor != ArrayList.this.size;
}
public E next() {
this.checkForComodification();
int var1 = this.cursor;
if (var1 >= ArrayList.this.size) {
throw new NoSuchElementException();
} else {
Object[] var2 = ArrayList.this.elementData;
if (var1 >= var2.length) {
throw new ConcurrentModificationException();
} else {
this.cursor = var1 + 1;
return var2[this.lastRet = var1];
}
}
}
public void remove() {
if (this.lastRet < 0) {
throw new IllegalStateException();
} else {
this.checkForComodification();
try {
ArrayList.this.remove(this.lastRet);
this.cursor = this.lastRet;
this.lastRet = -1;
this.expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException var2) {
throw new ConcurrentModificationException();
}
}
}
public void forEachRemaining(Consumer<? super E> var1) {
Objects.requireNonNull(var1);
int var2 = ArrayList.this.size;
int var3 = this.cursor;
if (var3 < var2) {
Object[] var4 = ArrayList.this.elementData;
if (var3 >= var4.length) {
throw new ConcurrentModificationException();
} else {
while(var3 != var2 && ArrayList.this.modCount == this.expectedModCount) {
var1.accept(var4[var3++]);
}
this.cursor = var3;
this.lastRet = var3 - 1;
this.checkForComodification();
}
}
}
final void checkForComodification() {
if (ArrayList.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
}通过上面迭代器的源码可以验证我们上面的猜想。那么这个异常怎么出现的，就显而易见了，一般出现在，我们通过Iterator遍历list、map的时候，而同时又通过list、map的remove、add操作去操作数组，导致ArrayList.this.modCount != this.expectedModCount
总结
1.ArrayList、LinkedList、Vendor的区别和联系，主要从底层数据结构实现不同、add：remove：get相应的时间复杂度不一样、是否线程安全。
2.ArrayList如果不指定大小，默认初始容量为0，第一次添加元素时，初始容量开始为初始化为10，之后每次添加元素，进行扩容检测机制（如果size+1，大于当前数组大小，则进行扩容，首先扩容为1.5倍，如果依然不能满足，则扩充为Int最大值-8），ArrayList每次扩容，都会进行数组copy。
3.ConcurrentModificationException发生是因为我们在使用迭代器遍历List的同时，还使用了List相应的remove、add进行元素增加或删除，导致不一。
