较真，ArrayList和LinkList增加，插入速度比较，代码详解

网上有很多ArrayList和LinkList的各种对比，以前学习这两个集合的时候老师讲的是：查询ArrayList快，新增和删除LinkLink快。需要频繁查询用ArrayList，需要频繁增删用LinkLink。
但是网上百度的话说法又不一样。
下面就上代码测试吧：（测试是使用的JDK1.8其他版本结论可能不同，不做版本更变测试）

//先测试新增速度，使用add()方法 先插入10000条数据比较
//比较速度的时候为了不影响 要单独跑 不能两个列表同时插入
public static void main(String[] args){List<String> array = new ArrayList<String>();LinkedList<String> link = new LinkedList<String>();//array 插入long startlist = System.currentTimeMillis();for(int i = 0; i < 10000; i ++){array.add("123"+i);}long endTime = System.currentTimeMillis();System.out.println("array="+(endTime-startlist));//link插入/** long startlist2 = System.currentTimeMillis();for(int i = 0; i <10000; i ++){link.add("123"+i);}long endTime2 = System.currentTimeMillis();System.out.println("link="+(endTime2-startlist2));*/}//分别运行3次//array=10 array=9 array=10// link=10 link=10 link=10


可以得出结论 在添加10000条数据的时候 两个数组几乎没差别。
继续测试，还是刚才代码，把for循环里面参数改为1000000，

一样 分别运行3次得出结果
array=577 array=518 array=537
link=778 link=752 link=691
得出结果 arrayList在新增百万数据时要快一点，但是差别也不大


再加大数据(我IDEA跑的 再加到1000W循环是保存内存溢出 加大了JVM内存空间再战！！！)：

一样 分别运行3次得出结果
link=6628 link=6873 link=6469
array=5934 array=5725 array=5767实际证明 千万数据新增还是ArrayList要快一点。


是不是感觉已经推翻了以前学到的东西，不急，下面来分别研究两个集合在新增的时候到底做了什么操作，上源码：

在这里插入代码片


结论 在不修改指针的时候，就算ArrayList发生了扩容copy操作，在往数据末尾新增的时候速度还是比LinkList速度快。

//ArrayList源码：
public boolean add(E e) {//增加数组大小（指针移动） 如果需要就扩容ensureCapacityInternal(size + 1); //元素赋值elementData[size++] = e;return true;}//ensureCapacityInternal方法 判断是否小于数组初始值10private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}//当前数组+1 如果大于当前数组长度就进行扩容
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}//这个就是扩容的最本质方法了 新建一个1.5倍长度的数组，在把老数组拷贝过来。copyOf方法使用的是 native void arraycopy 效率很快private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}

下面是LinkList源码分析：

//linkList的add方法看起来就简单了很多public boolean add(E e) {linkLast(e);return true;}
//找到最好一个参数 创建一个新的Node对象直接新增，修改前一个Node对象，看上去很简单，但是实际上新增了一个对象，修改了一个对象。void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}


继续测试，测试插入方法，一样的测试代码

public static void main(String[] args){ArrayList<String> array = new ArrayList<String>();LinkedList<String> link = new LinkedList<String>();//先创建数据for(int i = 0; i < 10000; i ++){link.add("123"+i);}//插入新数据long startlist2 = System.currentTimeMillis();for(int i = 0; i < 100000; i ++){link.add(0,"123"+i);}long endTime2 = System.currentTimeMillis();System.out.println("link="+(endTime2-startlist2));//还是分别执行 互不影响/* for(int i = 0; i <10000; i ++){array.add("123"+i);}long startlist = System.currentTimeMillis();for(int i = 0; i <100000; i ++){array.add(0,"123"+i);}long endTime = System.currentTimeMillis();System.out.println("array="+(endTime-startlist));*/}//分别执行3次 看结果//link=63 link=58 link=65//array=3469 array=3398 array=3244


插入速度通过测试得出，linkList直接完爆ArrayList，
这又是为什么呢？？？
上源码：

//ArrayList 插入方法
public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1); // Increments modCount!!//这里可以看出 插入的时候 是直接调用的arraycopy copy了一个新的数组System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}


ArrayList很粗暴的每次插入都在复制新的数组，

//linkList 先判断是不是最后一个，最好一个调用和刚才新增一样的方法创建对象，不是最后一个
public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}
//不是最后一个 使用插入方法，新增对象，修改所以对象指针。
void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev;final Node<E> newNode = new Node<>(pred, e, succ);succ.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}


可以得出最终结论，在新增对象的时候两个集合ArrayList要快一点，但是基本没什么区别。
但是在插入操作的时候，LinkList效率完爆ArrayList。

最后在补充一下两个数组删除remove方法的效率差距：

//这是ArrayList的remove源码 这里可以看出 删除方法也是调用arraycopy
public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}//而LinkList依旧只是在对节点对象进行操作public E remove(int index) {checkElementIndex(index);return unlink(node(index));}E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}


由此可见，LinkList在删除的效率上依旧完爆ArrayList。
注：以上源码只针对JDK1.8！！