1700443986
1700443987
}
1700443988
1700443989
这是一个典型的双向链表插入算法，把自己插入到链表，然后再把前节点的next和后节点的previous指向自己。想想看，这样一个插入元素（也就是Entry对象）的过程中，没有任何元素会有拷贝过程，只是引用地址改变了，那效率当然就高了。
1700443990
1700443991
经过实际测试得知，LinkedList的插入效率比ArrayList快50倍以上。
1700443992
1700443993
（2）删除元素
1700443994
1700443995
插入了解清楚了，我们再来看删除动作。ArrayList提供了删除指定位置上的元素、删除指定值元素、删除一个下标范围内的元素集等删除动作，三者的实现原理基本相似，都是找到索引位置，然后删除。我们以最常用的删除指定下标的方法（remove方法）为例来看看删除动作的性能到底如何，源码如下：
1700443996
1700443997
public E remove（int index）{
1700443998
1700443999
//下标校验
1700444000
1700444001
RangeCheck（index）；
1700444002
1700444003
//修改计数器+1
1700444004
1700444005
modCount++；
1700444006
1700444007
//记录要删除的元素值
1700444008
1700444009
E oldValue=（E）elementData[index]；
1700444010
1700444011
//有多少个元素向前移动
1700444012
1700444013
int numMoved=size-index-1；
1700444014
1700444015
if（numMoved＞0）
1700444016
1700444017
//index后的元素向前移动一位
1700444018
1700444019
System.arraycopy（elementData, index+1，elementData, index, numMoved）；
1700444020
1700444021
//列表长度减1，并且最后一位设为null
1700444022
1700444023
elementData[—size]=null；
1700444024
1700444025
//返回删除的值
1700444026
1700444027
return oldValue；
1700444028
1700444029
}
1700444030
1700444031
注意看，index位置后的元素都向前移动了一位，最后一个位置空出来了，这又是一次数组拷贝，和插入一样，如果数据量大，删除动作必然会暴露出性能和效率方面的问题。ArrayList其他的两个删除方法与此相似，不再赘述。
1700444032
1700444033
我们再来看看LinkedList的删除动作。LinkedList提供了非常多的删除操作，比如删除指定位置元素、删除头元素等，与之相关的poll方法也会执行删除动作，下面来看最基本的删除指定位置元素的方法remove，源代码如下：
1700444034
1700444035
private E remove（Entry＜E＞e）{
[
上一页 ]
[ :1.700443986e+09 ]
[
下一页 ]