ArrayList 和 LinkedList 是 List 接口的两种不同实现,并且两者都不是线程安全的。但初学者往往搞不清楚它们两者之间的区别,不知道什么时候该用 ArrayList,什么时候该用 LinkedList,那这篇文章就来传道受业解惑一下。
ArrayList 内部使用的动态数组来存储元素,LinkedList 内部使用的双向链表来存储元素,这也是 ArrayList 和 LinkedList 最本质的区别。
注:本文使用的 JDK 源码版本为 14,小伙伴如果发现文章中的源码和自己本地的不同时,不要担心,不是我源码贴错了,也不是你本地的源码错了,只是版本不同而已。
由于 ArrayList 和 LinkedList 内部使用的存储方式不同,导致它们的各种方法具有不同的时间复杂度。先来通过维基百科理解一下时间复杂度这个概念。
在计算机科学中,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n 0 n_0 n
0
大)的输入,它至多需要 5 n 3 + 3 n 5n^3 + 3n 5n
3
+3n 的时间运行完毕,那么它的渐近时间复杂度是 O ( n 3 ) O(n3^) O(n3
)
。
对于 ArrayList 来说:
1)get(int index) 方法的时间复杂度为 O ( 1 ) O(1) O(1),因为是直接从底层数组根据下标获取的,和数组长度无关。
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
这也是 ArrayList 的最大优点。
2)add(E e) 方法会默认将元素添加到数组末尾,但需要考虑到数组扩容的情况,如果不需要扩容,时间复杂度为 O ( 1 ) O(1) O(1)。
public boolean add(E e) { modCount++; add(e, elementData, size); return true; } private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; }
如果需要扩容的话,并且不是第一次(oldCapacity > 0)扩容的时候,内部执行的 Arrays.copyOf() 方法是耗时的关键,需要把原有数组中的元素复制到扩容后的新数组当中。
private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }
3)add(int index, E element) 方法将新的元素插入到指定的位置,考虑到需要复制底层数组(根据之前的判断,扩容的话,数组可能要复制一次),根据最坏的打算(不管需要不需要扩容,System.arraycopy() 肯定要执行),所以时间复杂度为 O ( n ) O(n) O(n)。
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; }
来执行以下代码,把沉默王八插入到下标为 2 的位置上。
ArrayList<String> list = new ArrayList<>();
list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");
list.add("沉默王五");
list.add("沉默王六");
list.add("沉默王七");
list.add(2, "沉默王八");
System.arraycopy() 执行完成后,下标为 2 的元素为沉默王四,这一点需要注意。也就是说,在数组中插入元素的时候,会把插入位置以后的元素依次往后复制,所以下标为 2 和下标为 3 的元素都为沉默王四。
之后再通过 elementData[index] = element 将下标为 2 的元素赋值为沉默王八;随后执行 size = s + 1,数组的长度变为 7。
4)remove(int index) 方法将指定位置上的元素删除,考虑到需要复制底层数组,所以时间复杂度为 O ( n ) O(n) O(n)。
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; } 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; }
对于 LinkedList 来说:
1)get(int index) 方法的时间复杂度为 O ( n ) O(n) O(n),因为需要循环遍历整个链表。
public E get(int index) { checkElementIndex(index); return node(index).item; } LinkedList.Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { LinkedList.Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { LinkedList.Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }