大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 如何提高Java代码质量:频繁插入和删除时使用LinkedList

如何提高Java代码质量:频繁插入和删除时使用LinkedList


[摘要]本文主要是对如何提高Java代码质量:频繁插入和删除时使用LinkedList的讲解,希望对大家学习如何提高Java代码质量:频繁插入和删除时使用LinkedList有所帮助。

  一、分析

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

  二、场景

  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 addBefore(E e,Entry entry){

  //组装一个新的节点,previous指向原节点的前节点,next指向原节点

  Entry newEntry = new Entry(e,entry,entry.previous);

  //前节点的next指向自己

  newEntry.previous.next = newEntry;

  //后节点的previous指向自己

  newEntry.next.previous = newEntry;

  //长度+1

  size++;

  //修改计数器+1

  modCount ++;

  return newEntry;

  }

  private Entry addBefore(E e,Entry entry){

  //组装一个新的节点,previous指向原节点的前节点,next指向原节点

  Entry newEntry = new Entry(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 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 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 = entry(index);

  E oldVal = e.element;

  //节点元素替换

  e.element = element;

  return oldVal;

  }

  public E set(int index,E element){

  //定位节点

  Entry 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。



相关评论