上一篇我们知道了ArrayList的自动扩容的逻辑，并且知道如何创建ArrayList比较合理。
这一篇我们来看ArrayList的优缺点，以及分析适合的使用场景。
因为ArrayList底层使用数组实现，所以优缺点与数组类似。国际惯例，先上结论。
优缺点
优点：
- add(E) 添加元素，直接在后面添加，时间复杂度O(1)，而且在循环调用还会有内联优化，节省大量函数调用开销
- get() 直接根据下标访问元素效率最高，时间复杂度 O(1)。
- 根据下标遍历元素效率高，时间复杂度 O(N)
- 在数组的基础上封装了对元素操作的方法。
- 可以自动扩容，每次扩容50%。
缺点：
- 插入效率低。add(index, E) 插入元素，在第几个元素后面插入，后面的元素需要向后移动，时间复杂度O(n)。
- 根据内容查找元素的效率低，例如
contains(Object o)、indexOf(Object o)，时间复杂度O(N)。- 删除效率低。remove()删除元素，后面的元素需要逐个移动，时间复杂度O(n)。
适用场景（以下其一）
- 经常遍历数据
- 插入顺序与读取顺序相同
- 需要大量随机访问数据
- 极少甚至没有随机插入删除操作形成v
优缺点源码级解读
一、添加元素public boolean add(E e)
public boolean add(E e) {
// 操作次数递增
modCount++;
// 调用私有函数 add(E e, Object[] elementData, int s) 添加元素
add(e, elementData, size);
return true;
}
原来，add(E e) 调用私有函数 add(E e, Object[] elementData, int s)
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
原来，如果数组空间足够，add方法就直接在最末端添加元素e即可，就这一句代码elementData[s] = e。时间复杂度只有O(1)，最快。
重点来了！
注释提到，为什么要提取这么个私有函数呢？
因为要保证add(E e)方法代码足够少，编译后字节码字在35字节以下。
为什么要保证add方法代码足够少？
因为JVM会自动地识别热点方法，并对它们使用方法内联优化。
这样使得频繁调用的add被内联为代码，嵌入我们的业务代码中，极大节省调用函数浪费的开销。
二、获取元素public E get(int index)
/**
* 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) {
Objects.checkIndex(index, size);
return elementData(index);
}
又是2句代码，估计也是用于内联优化的。再跳过去看E elementData(int index)函数。
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
就是简单一句通过下标访问数组元素。时间复杂度只有O(1)，最快。
另外注意到，出现一句注解@SuppressWarnings("unchecked")，告诉编译器忽略 unchecked 警告信息，如使用List，ArrayList等未进行参数化产生的警告信息。
三、插入元素public void add(int index, E element)
/**
* Inserts the specified element at the specified position in this
* 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);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
插入的逻辑是：先判断是否需要扩容，如果需要就扩容。然后移动当前处于该位置的后面所有元素，最后才插入新元素。最坏情况是插入第一个，那得移动整个数组，非常慢，O(N)。
ArrayList添加与插入示意图
四、内容查找public int indexOf(Object o)
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
查找的核心逻辑中indexOfRange函数。
用一个循环从头到尾找到需要查找的元素，最慢，O(N)。
五、删除元素public E remove(int index)和public boolean remove(Object o)
删除元素有2个函数，一个按数组索引删除，一个按内容查找删除。
按数组索引删除，根据上面插入元素可以推断出，按照数组索引快速找到对应位置后，把后面所有元素往前移动一格即可，非常慢，O(N)。
/**
* 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) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
逻辑在私有函数 fastRemove。把后面的元素往前移动一格。
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
而按内容查找删除，先按内容查找，然后再删除，也是非常慢，O(N)。这里就不详述了。
最后，根据我们分析的结论加以汇总，就得到我们文章开头的ArrayList的优缺点以及适用场景 。
网友评论