[改善Java代码]频繁插入和删除时使用LinkedList

　一、分析

前面有文章分析了列表的表里方式，也就是“读”的操作。本文将介绍表的“写”操作：即插入、删除、修改动作。

二、场景

　1.插入元素

　列表中我们使用最多的是ArrayList，下面看看他的插入(add方法)算法，源代码如下：

 1     public void add(int index,E element){
 2       　　/*检查下标是否越界，代码不在拷贝*/
 3       　　//若需要扩容，则增大底层数组的长度
 4       　　ensureCapacity(size + 1);
 5       　　//给index下标之后的元素(包括当前元素)的下标加1，空出index位置(将elementData从index起始，复制到index+1的职位
 6       　　System.arraycopy(elementData,index,elementData,index + 1,size - index);
 7       　　//赋值index位置元素
 8       　　elementData[index] = element;
 9       　　//列表的长度+1
10       　　size++;
11       　　}
12       }

注意看arraycopy方法，只要是插入一个元素，其后的元素就会向后移动一位，虽然arraycopy是一个本地方法，效率非常高，但频繁的插入，每次后面的元素都需要拷贝一遍，效率变低了，特别是在头位置插入元素时。

现在的问题是,开发中确实会遇到要插入元素的情况,那有什么更好的方法来解决此效率问题吗?

有....使用LinkedList类即可,我们知道,LinkedList是一个双向链表,它的插入只是修改相邻元素的next和previous引用,其插入算法(add方法)如下:

1 public void add(int index,E element){
2 　　addBefore(element,(index==size?header:entry(index)));
3 }

这里调用了私有的addBefore方法,改方法实现了在一个元素之前插入元素的算法,代码如下:

 1 private Entry addBefore(E e,Entry entry){
 2 　　//组装一个新的节点，previous指向原节点的前节点，next指向原节点
 3 　　Entry newEntry = new Entry(e,entry,entry.previous);
 4 　　//前节点的next指向自己
 5 　　newEntry.previous.next = newEntry;
 6 　　//后节点的previous指向自己
 7 　　newEntry.next.previous = newEntry;
 8 　　//长度+1
 9 　　size++;
10 　　//修改计数器+1
11 　　modCount ++;
12 　　return newEntry;
13 }

这是一个典型的双向链表的插入算法,把自己插入到链表,然后把前节点的next和后节点的previous指向自己。这样一个插入元素(也就是一个Entry对象)的过程中,没有任何元素会有拷贝过程,只是引用地址改变了.效率当然就高了.

经过实际测试得知,LinkedList的插入效率比ArrayList快50倍以上.

(2)删除元素

ArrayList删除指定位置上的元素、删除指定值元素，删除一个下标范围内的元素集等删除动作，三者的实现原理基本相似，都是找到索引位置，然后删除。我偶们常用的删除下标的方法(remove方法)为例来看看删除动作的性能到底如何，源码如下：

 1 public E remove(int index){
 2 　　//下标校验
 3 　　RangeCheck(index);
 4 　　//修改计数器+1
 5 　　modCount++;
 6 　　//记录要删除的元素
 7 　　E oldValue = (E)elementData(index);
 8 　　//有多少个元素向前移动
 9 　　int numMoved = size - index - 1;
10 　　if(numMoved > 0)
11 　　//index后的元素向前移动一位
12 　　System.arraycopy(elementData,index + 1,elementData,index,numMoved);
13 　　//列表长度减1，并且最后一位设为null
14 　　elementData[--size] = null;
15 　　//返回删除的值
16 　　return oldValue;
17 }

注意看,index位置后的元素都向前移动了一位，最后一个位置空出来了，这又是一次数组拷贝，和插入一样，如果数据量大，删除动作必然会暴露出性能和效率方面的问题。

我们再来看看LinkedList的删除动作，比如删除指定位置元素，删除头元素等。我们看看最基本的删除指定位置元素的方法remove，源代码如下：

 1 private E remove(Entry e){
 2 　　//取得原始值
 3 　　E result = e.element;
 4 　　//前节点next指向当前节点的next
 5 　　e.previous.next = e.next;
 6 　　//后节点的previouse指向当前节点的previous
 7 　　e.next.previous = e.previous;
 8 　　//置空当前节点的next和previous
 9 　　e.next = e.previous= null;
10 　　//当前元素置空
11 　　e.element = null;
12 　　//列表长度减1
13 　　size --;
14 　　//修改计数器+1
15 　　modCount++;
16 　　return result;
17 }

这也是双向链表的标准删除算法，没有任何耗时的操作，全部是引用指针的改变，效率自然就更高了。

实际测试可知，处理大批量的删除操作，LinkedList比ArrayList块40倍以上。

(3)修改元素

写操作还有一个动作：修改元素，在这点上LinkedList输给了ArrayList，这是因为，LinkedList是顺序存取的，因此定位元素必然是一个遍历的过程，效率大大折扣。

我们来开set方法的代码：

1 public E set(int index,E element){
2 　　//定位节点
3 　　Entry e = entry(index);
4 　　E oldVal = e.element;
5 　　//节点元素替换
6 　　e.element = element;
7 　　return oldVal;
8 }

看似很简洁，这里使用了entry方法定位元素。而LinkedList这种顺序取列表的元素定位方式会折半遍历，这是一个极其耗时的操作。而ArrayList的修改动作则是数组元素的直接替换，简单高效。

在修改动作上，LinkedList比ArrayList慢的多，特别是进行大量修改的时候，完全不是在一个数量级上。

上面通过源代码分析完成了ArrayList和LinkedList之间的PK,其中LinkedList胜两局:删除和插入效率更高;ArrayList胜一局,修改效率更高.

总体上来说,在"写"方面LinkedList占优势,而且在实际使用中,修改上一个比较少的动作.因此,如果有大量写的操作(更多的是插入和删除操作),推荐使用LinkedList.

不过何为少量,何为大量..

这就需要依赖于开发的系统了..一个实时的交易系统,即使写的操作再少,使用LinkedList也比ArrayList合适.因为此类系统是争分夺秒的,多N个毫秒可能就会造成交易数据的不准确.

而对于一个批量系统来说,几十毫秒,几百毫秒,甚至是几千毫秒的差别和意义都不大,这时候使用LinkedList和ArrayList就看个人的爱好了,当然,如果系统已经处于性能临界点了那就必须使用LinkedList.