ArrayList与LinkList性能对比新增元素

在聊到 ArrayList 和 LinkList 的时候都会这么说

ArrayList 底层是基于数组实现的内存地址物理上是连续的，新增，删除效率低，查询效率高
LinkList 是基于链表实现的，逻辑地址是连续的内存地址不连续，新增，删除效率高，查询检索效率低

今天我试验了一下

分别从 List 的头部，中间，尾部，插入元素

1万的数量级结果如下图，耗时单位ms

head 消耗时间 arrayList>linkedList

middle 消耗时间 arrayList<linkedList

end 消耗时间 arrayList < linkedList

10万的数量级结果如下图，耗时单位ms

head 消耗时间 arrayList>linkedList

middle 消耗时间 arrayList<linkedList

end 消耗时间 arrayList > linkedList

两个量级对比，可以很明显的看出，linkedList 在添加元素的时候，从头部和尾部的效率都是要高于arrayList，唯独指定下标从中间位置添加元素的效率是低于arrayList而且是远远低于的

先看一下arrayList 的添加指定下标元素的代码

1.第一步校验下标是否非法是否越界抛出 IndexOutOfBoundsException

2.判断数据是否需扩容，如果需要则将数组长度扩为原来的1.5倍

3.整个方法的核心

System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
参数1 this.elementData,原数组

参数2 this.var1,原数组中元数据的起始位置

参数3 this.elementData,目标数组

参数4 var1 + 1,目标数组的起始位置

参数5 this.size - var1,要复制数据的长度

方法执行后的效果如下图

经过System.arraycopy方法后，会得到一个新的数组，而这个数组的var1 下标的元素是空的

4. 将数组中var1 下标赋值新的元素

5.更新数组长度

再看 LinkList 的添加指定下标元素的代码

1.第一步校验下标是否非法是否越界抛出 IndexOutOfBoundsException

2.判断要添加的下标是否和数组长度相等，相等则直接将元素添加到末尾

3.当添加的下标位置和数组长度不相等的时候，则进入 linkBefore 方法，linkLast,linkBefore 这两个方法，只是将尾部和头部的数据中的Node对象进行了替换，同时更新了Node 里面的前节点对象和后节点对象信息

重点就在这个通过下标获取，数组元素的this.node(var1) 方法

1. 判断下标与 this.size >> 1 左移1位可以理解成 this.size/2, 也就是判断下标属于，数组的前半段还是后半段

2. 如果是前半段，则从首个节点开始不停的循环找下去，直到找到符合的下标位置，数据

3. 如果是后半段，则从尾部节点开始不停的循环找下去，直到找到符合的下标位置

上面的2,3步骤，在数据越的情况下，耗时极大，这也是为什么 linkedList 数量级从1万到10万，middle 消耗时间从349---129462 上升到了400倍

总结

arrayList 在新增指定下标的元素的时候，是通过数组复制，空出指定下标位置的内存，在将新增元素保存到数组中
linkedList 在新增指定下标的元素时，要判断下标所属位置，从而确定从头部还是尾部，查找到对应的下标节点对象，进行替换

所以不是所有的场景，linkedList 的新增元素效率高于 arrayList的

后面继续分享，删除和查询检索哈哈哈哈