LinkedList 和 ArrayList 是最常用的集合,两者是 List 的实现类。我们知道LinkedList便于插入、删除,却不便于获取指定位置的元素,而ArrayList恰恰相反。基于这些特性,我发现所接触的代码中需要优化的还有很多。

追加元素

  ArrayList 和 LinkedList 都实现了方法 add(E e),用于在集合末端追加元素。我从实现逻辑个实际使用来阐述两者区别。

实现逻辑

  • ArrayList
  1. 调用ensureCapacityInternal(size + 1),判断是否需要扩容
  2. 需要扩容则调用grow(minCapacity)进行扩容
  3. 使用 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)) 复制数组,完成扩容操作
  4. 最后赋值给末端元素 elementData[size++] = e
  • LinkedList
  1. 定义一个新节点,该节点的prev是List的last,next指向null
  2. 声明新节点为last

实际使用

  分别追加相同数量元素,记录耗时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void main(String[] args) {

int size = 10000000;
String str = "abc";
long startTime = System.currentTimeMillis();
List<String> linkedList = new LinkedList<>();
for (int i = 0; i < size; i++) {
linkedList.add(i + str);
}
long endTime = System.currentTimeMillis();
System.out.println("LinkedList,耗时:" + (endTime - startTime));

str = "xyz";
startTime = System.currentTimeMillis();
//未指定size
List arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) {
arrayList.add(i + str);
}
endTime = System.currentTimeMillis();
System.out.println("ArrayList 未指定size,耗时:" + (endTime - startTime));

str = "opq";
startTime = System.currentTimeMillis();
//指定size
arrayList = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
arrayList.add(i + str);
}
endTime = System.currentTimeMillis();
System.out.println("ArrayList 指定size,耗时:" + (endTime - startTime));
}
元素数量 LinkedList ArrayList 未指定size ArrayList 指定size
1kw 9643 4714 758
100w 212 202 66
1w 6 4 4
1k 1 1 1
100 0 0 0

  整体来看,ArrayList 完胜,初始化合适的size时效果最佳。

插入元素

  add(int index, E element) 在指定地方插入元素。

  • ArrayList
  1. 调用rangeCheckForAdd(index)校验待插入的位置是否越界,越界则抛异常IndexOutOfBoundsException
  2. 调用ensureCapacityInternal(size + 1),判断是否需要扩容
  3. 调用System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 复制数组
  4. 在index处赋值element
  • LinkedList

定位元素

读取元素

移除元素