数组在增删方面比链表效率高？？？

        数组和链表在增删查改方面谁的效率高呢， 这个问题相信很多人都遇到过，但更多的人只是记住两句口诀：数组查改方便，链表增删效率高。

        无论是书本，老师，还是许多的前辈都告诉我们，这是对的。理由如下：

        在查改方面数组可以通过索引迅速确定位置，而链表只能依次寻找，所以数组有着无法匹敌的优势。而在增删方面，数组每次插入元素都要将该元素后面的所有元素向后挪动一位，删除则将该元素之后所有元素向前移动一位。而链表在插入元素的时候，只需将该元素前驱的指针指向本身，将本身的指针指向后驱，删除则将该元素的前驱指向该元素的后驱。相比之下，链表确实优势挺大。

        首先，笔者想说，上面的理由全是对的，但是忽略了一个很严重的问题。那就是增删其实不仅仅是增删，它还包括查，增删的过程如下：

        增：找到插入该元素的位置，插入该元素

        删：找到删除该元素的位置，删除该元素

        既然增删包括了查，而在查这一方面，数组效率比链表高，又怎么能肯定地说链表增删效率比数组高呢，所以这个结果还有待争议，笔者为此特地做了个实验（这里只列出插入的实验，删除的也同理）：

import java.util.ArrayList;
import java.util.LinkedList;


public class LinkedAndArray {
	/*
	 * 比较数组和链表执行插入数据时花费的时间
	 * len    定义数组的长度
	 * num    循环插入的次数(插入一次时间太短难比较)
	 * index  每次插入的位置
	 */
	public static void printTime(int len,int num,int index){
		LinkedList<Integer> link=new LinkedList<Integer>();//定义链表
		ArrayList<Integer> arr=new ArrayList<Integer>();//定义数组
		//为数组赋初值
		for (int i = 0; i < len; i++) {
			arr.add(i);
			link.add(i);
		}
		//计算数组执行操作花费的时间
		long startTime=System.currentTimeMillis();
		for (int i = 0; i < num; i++) {
			arr.add(index,2);
		}
		long endTime=System.currentTimeMillis();
		System.out.println("数组花费时间："+(endTime-startTime)+"毫秒");
		//计算链表执行相同操作花费的时间
		long sTime=System.currentTimeMillis();
		for (int i = 0; i < num; i++) {
			link.add(index,2);
		}
		long eTime=System.currentTimeMillis();
		System.out.println("链表花费时间："+(eTime-sTime)+"毫秒");
	}
	
	public static void main(String[] args) {
		printTime(10000,5000,1000);
	}
}

          最后输出结果是：

         好多人一看，诶，对啊，跟我们往常的结论是一样的。别急，下面还有。当我们把插入的位置更改为数组的一半，也就是5000时，输出结果如下：

          当我们将数组长度变大时，这个差异更加明显：

        按照上面的这个数据可以粗略的计算出：链表每查询一个位置花费时间为0.000006毫秒（五个0），数组每移动一个位置花费时间为：0.00000088毫秒（六个0），以上计算是在忽略链表插入过程和忽略数组查询过程的情况下进行的。

        经过笔者反复试验，可以得出一个结论：在靠前的位置插入数据，链表效率较高，在靠后位置插入数据，数组效率较高

        那哪里是靠前，哪里是靠后呢，笔者又反复试验了好多次，然后有了如下结论：比如有一个长度都为n的数组、链表，当n长度小于一万时，有略高于0.2n的位置是属于靠前的，当n的长度越大，达到百万级别时，只有大概0.1n的长度算是靠前的了。

        所以综合来说，在增删方面的效率比较上，数组有八九成胜算，而链表只有一到两成。