前言
List相信大家都使用得很多，其中ArrayList和LinkedList是使用最多的2個(gè)窖贤，本文將從源碼角度解讀2者的異同砖顷，效率和使用場(chǎng)景。如有疏忽之處赃梧，還請(qǐng)多指教滤蝠。
正文
存儲(chǔ)結(jié)構(gòu)
- LinkedList是靠一個(gè)名為Node的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)和前后元素的指針，和雙向鏈表類似授嘀。first和last分別存儲(chǔ)了第一個(gè)和最后一個(gè)元素
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
其中item存儲(chǔ)了實(shí)際的元素?cái)?shù)據(jù)物咳，next是指向了下一個(gè)元素，prev指向了前一個(gè)元素
- 而ArrayList直接通過(guò)
transient Object[] elementData一個(gè)Object的數(shù)組存儲(chǔ)數(shù)據(jù)
插入
- ArrayList在插入之前需要通過(guò)ensureCapacityInternal方法先計(jì)算下加入一個(gè)元素后蹄皱，elementData數(shù)組的大小和當(dāng)前所需要的大小览闰，若大于于當(dāng)前數(shù)組的大小芯肤，則需要進(jìn)行resize和arrayCopy操作。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
resize和arrayCopy主要通過(guò)下面的grow方法執(zhí)行的
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
一般情況下压鉴，ArrayList的插入操作是O(1)的時(shí)間復(fù)雜度崖咨，但是當(dāng)需要resize的時(shí)候?yàn)镺(n)；類似晴弃，add(int index, E element)的時(shí)間復(fù)雜度一般是O(n/2)掩幢，需要相應(yīng)挪動(dòng)插入的位置之后的元素。
- LinkedList的插入操作即在鏈表后加一個(gè)元素上鞠，先創(chuàng)建一個(gè)Node际邻，當(dāng)前插入的元素的prev指向last Node，將last賦值為當(dāng)前插入Node芍阎。如果插入前的last不為null世曾，則將last Node的next指向當(dāng)前插入的元素；反之則將first也賦值為當(dāng)前插入的Node（即空LinkedList插入元素后谴咸，last和first都指向同一個(gè)元素）
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList的插入操作的時(shí)間復(fù)雜度是O(1)轮听；相應(yīng)的add(int index, E element)的一般時(shí)間復(fù)雜度是O(n/4)，從鏈表前后同時(shí)搜索岭佳，如果index=linkedlist.size()/2血巍，那么是最壞情況，為O(n/2)
取元素
- ArrayList直接根據(jù)數(shù)組下標(biāo)獲取相應(yīng)的元素珊随，所以時(shí)間復(fù)雜度為O(1)述寡，這也是ArrayList的最大的好處
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
- 而LinkedList需要從第一個(gè)或最后一個(gè)Node往中間遍歷，所以其時(shí)間復(fù)雜度和
add(int index, E element)類似叶洞，一般時(shí)間復(fù)雜度是O(n/4)鲫凶，最壞為O(n/2)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// 判斷從首還是尾開(kāi)始遍歷
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
刪除
-
當(dāng)刪除某個(gè)元素時(shí)
remove(int index)，ArrayList需要進(jìn)行resize和arrayCopy操作衩辟，所以時(shí)間復(fù)雜度也為O(n/2)螟炫。只有當(dāng)刪除的是最后一個(gè)元素時(shí)，不用進(jìn)行上述操作艺晴。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = 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;
}
- LinkedList刪除操作和取元素的時(shí)間復(fù)雜度一樣昼钻，因?yàn)橐彩且韧ㄟ^(guò)node方法來(lái)找到要被刪除的元素，再進(jìn)行改變其前后元素的prev和next指針财饥，所以其時(shí)間復(fù)雜度是O(n/4)换吧，最壞為O(n/2)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Iterator
- 使用Iterator迭代器循環(huán)時(shí)，可以進(jìn)行add和remove操作钥星。
List<String> listA = new ArrayList<>();
//List<String> listB = new LinkedList<>();
ListIterator<String> iteratorA = listA.listIterator();
while (iteratorA.hasNext()) {
String temp = iteratorA.next();
// iteratorA.add("some string");iteratorA.remove()
}
System.out.println(listA.toString());
- ArrayList在迭代遍歷時(shí)，add和remove操作的時(shí)間復(fù)雜度都為O(n/2)满着，因?yàn)槠湫枰獙⒉僮鞯脑刂蟮乃性剡M(jìn)行數(shù)組移位操作谦炒，即resize和arrayCopy
- LinkedList在迭代遍歷時(shí)贯莺，add和remove操作的時(shí)間復(fù)雜度都為O(1)，這也是LinkedList的主要優(yōu)勢(shì)
總結(jié)
- ArrayList的優(yōu)勢(shì)在于隨機(jī)快速讀取宁改，其直接在末尾插入元素的效率也很高缕探。唯一需要注意的是，其resize的時(shí)候还蹲，需要一定的開(kāi)銷爹耗。所以如果你提前能預(yù)估ArrayList的大小，你可以在實(shí)例化時(shí)谜喊，給他賦一個(gè)initialCapacity潭兽，可以減小resize的次數(shù)。
- LinkedList的優(yōu)勢(shì)在于利用Iterator迭代器循環(huán)時(shí)斗遏，其插入和刪除的效率都是最高的山卦。
- 在存儲(chǔ)空間上，LinkedList相比ArrayList的每個(gè)元素都有更多的開(kāi)銷诵次，因?yàn)檫€存儲(chǔ)了指向下一個(gè)和前一個(gè)元素的指針账蓉。所以如果你的list很大的話，這一點(diǎn)也需要考慮進(jìn)去逾一。
