提高你的Java代码质量吧：频繁插入和删除时使用LinkedList

一、分析

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

二、场景

1.插入元素

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

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

那么开发过程中确实会遇到插入元素的情况，我们一般使用LinkedList类即可。LinkedList是一个双向的链表，它的插入只是修改相邻元素next和previous引用，插入算法（add方法）如下：

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

这里调用了私有addBefore方法，该方法实现在entry元素之前插入元素e的算法，代码如下：

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方法）为例来看看删除动作的性能到底如何，源码如下：

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，源代码如下：

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方法的代码：

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。