提高你的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){
