提高你的Java代碼質量吧：頻繁插入和刪除時使用LinkedList
JavaLinkedListArrayList插入刪除一、分析
前面有文章分析了列表的表裡方式，也就是“讀”的操作。本文將介紹表的“寫”操作：即插入、刪除、修改動作。
二、場景
1.插入元素
列表中我們使用最多的是ArrayList，下面看看他的插入（add方法）算法，源代碼如下：
[Java] public void add(int index,E element){
/*檢查下標是否越界，代碼不在拷貝*/
//若需要擴容，則增大底層數組的長度
ensureCapacity(size + 1);
//給index下標之後的元素（包括當前元素）的下標加1，空出index位置（將elementData從index起始，復制到index+1的職位
System.arraycopy(elementData,index,elementData,index + 1,size - index);
//賦值index位置元素
elementData[index] = element;
//列表的長度+1
size++;
}
public void add(int index,E element){
/*檢查下標是否越界，代碼不在拷貝*/
//若需要擴容，則增大底層數組的長度
ensureCapacity(size + 1);
//給index下標之後的元素（包括當前元素）的下標加1，空出index位置（將elementData從index起始，復制到index+1的職位
System.arraycopy(elementData,index,elementData,index + 1,size - index);
//賦值index位置元素
elementData[index] = element;
//列表的長度+1
size++;
}
注意看arraycopy方法，只要是插入一個元素，其後的元素就會向後移動一位，雖然arraycopu是一個本地方法，效率非常高，但頻繁的插入，每次後面的元素都需要拷貝一遍，效率變低了，特別是在頭位置插入元素時。
那麼開發過程中確實會遇到插入元素的情況，我們一般使用LinkedList類即可。LinkedList是一個雙向的鏈表，它的插入只是修改相鄰元素next和previous引用，插入算法（add方法）如下：
[Java] public void add(int index,E element){
addBefore(element,(index==size?header:entry(index)));
}
public void add(int index,E element){
addBefore(element,(index==size?header:entry(index)));
}
這裡調用了私有addBefore方法，該方法實現在entry元素之前插入元素e的算法，代碼如下：
[Java] private Entry<E> addBefore(E e,Entry<E> entry){
//組裝一個新的節點，previous指向原節點的前節點，next指向原節點
Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
//前節點的next指向自己
newEntry.previous.next = newEntry;
//後節點的previous指向自己
newEntry.next.previous = newEntry;
//長度+1
size++;
//修改計數器+1
modCount ++;
return newEntry;
}
private Entry<E> addBefore(E e,Entry<E> entry){
//組裝一個新的節點，previous指向原節點的前節點，next指向原節點
Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
//前節點的next指向自己
newEntry.previous.next = newEntry;
//後節點的previous指向自己
newEntry.next.previous = newEntry;
//長度+1
size++;
//修改計數器+1
modCount ++;
return newEntry;
}
這是一個典型的雙向鏈表插入算法，把自己插入到鏈表，然後把前節點的next和後節點的previous指向自己。
經過實際測試得知，LinkedList的插入效率比ArrayList塊50倍以上。
且慢，增加元素還有一個add()方法(無參數)，該方法增加元素性能上基本沒有什麼差別，區別在於LinkedList生成一個新的Entry元素，其previous指向倒數第二個Entry，next置空；而ArrayList則是把元素追加到了數組末尾而已。差別非常微小。
2.刪除元素
ArrayList刪除指定位置上的元素、刪除指定值元素，刪除一個下標范圍內的元素集等刪除動作，三者的實現原理基本相似，都是找到索引位置，然後刪除。我偶們常用的刪除下標的方法（remove方法）為例來看看刪除動作的性能到底如何，
源碼如下：
[Java] public E remove(int index){
//下標校驗
RangeCheck(index);
//修改計數器+1
modCount++;
//記錄要刪除的元素
E oldValue = (E)elementData(index);
//有多少個元素向前移動
int numMoved = size - index - 1;
if(numMoved > 0)
//index後的元素向前移動一位
System.arraycopy(elementData,index + 1,elementData,index,numMoved);
//列表長度減1，並且最後一位設為null
elementData[--size] = null;
//返回刪除的值
return oldValue;
}
public E remove(int index){
//下標校驗
RangeCheck(index);
//修改計數器+1
modCount++;
//記錄要刪除的元素
E oldValue = (E)elementData(index);
//有多少個元素向前移動
int numMoved = size - index - 1;
if(numMoved > 0)
//index後的元素向前移動一位
System.arraycopy(elementData,index + 1,elementData,index,numMoved);
//列表長度減1，並且最後一位設為null
elementData[--size] = null;
//返回刪除的值
return oldValue;
}
注意看,index位置後的元素都向前移動了一位，最後一個位置空出來了，這又是一次數組拷貝，和插入一樣，如果數據量大，刪除動作必然會暴露出性能和效率方面的問題。
我們再來看看LinkedList的刪除動作，比如刪除指定位置元素，刪除頭元素等。我們看看最基本的刪除指定位置元素的方法remove，源代碼如下：
[Java] private E remove(Entry<E> e){
//取得原始值
E result = e.element;
//前節點next指向當前節點的next
e.previous.next = e.next;
//後節點的previouse指向當前節點的previous
e.next.previous = e.previous;
//置空當前節點的next和previous
e.next = e.previous= null;
//當前元素置空
e.element = null;
//列表長度減1
size --;
//修改計數器+1
modCount++;
return result;
}
private E remove(Entry<E> e){
//取得原始值
E result = e.element;
//前節點next指向當前節點的next
e.previous.next = e.next;
//後節點的previouse指向當前節點的previous
e.next.previous = e.previous;
//置空當前節點的next和previous
e.next = e.previous= null;
//當前元素置空
e.element = null;
//列表長度減1
size --;
//修改計數器+1
modCount++;
return result;
}
這也是雙向鏈表的標准刪除算法，沒有任何耗時的操作，全部是引用指針的改變，效率自然就更高了。
實際測試可知，處理大批量的刪除操作，LinkedList比ArrayList塊40倍以上。
3.修改元素
寫操作還有一個動作：修改元素，在這點上LinkedList輸給了ArrayList，這是因為，LinkedList是順序存取的，因此定位元素必然是一個遍歷的過程，效率大大折扣。
我們來開set方法的代碼：
[Java] public E set(int index,E element){
//定位節點
Entry<E> e = entry(index);
E oldVal = e.element;
//節點元素替換
e.element = element;
return oldVal;
}
public E set(int index,E element){
//定位節點
Entry<E> e = entry(index);
E oldVal = e.element;
//節點元素替換
e.element = element;
return oldVal;
}
看似很簡潔，這裡使用了entry方法定位元素。而LinkedList這種順序取列表的元素定位方式會折半遍歷，這是一個極其耗時的操作。而ArrayList的修改動作則是數組元素的直接替換，簡單高效。
在修改動作上，LinkedList比ArrayList慢的多，特別是進行大量修改的時候，完全不是在一個數量級上。
三、建議
經過上面的源碼分析完成了LinkedList與ArrayList之間的PK，其中LinkedList勝兩局：刪除和插入效率高；ArrayList勝一局：修改元素效率高。
如果有大量的寫操作（更多的插入和刪除動作），推薦使用LinkedList。不過何為少量，何為大量呢？
這就依賴於正在開發的
系統了，如果是一個實時的交易系統，即使寫操作少，，使用LinkedList也比ArrayList合適，因為此類系統爭分奪秒，多N個毫秒就可能會造成交易數據不准確。如果對於一個批量系統來說，幾十毫秒、幾百毫秒，甚至是幾千毫秒的差別意義並不大，這時使用LinkedList還是ArrayList就看個人愛好了。當然，如果系統處於性能臨界點，那就必須使用LinkedList。
