Java谣言终结者之Arraylist和Linkedlist到底谁快

Arraylist和Linkedlist是我们常用的两个集合类，他们都是实现了list接口并且都可以序列化，此外实现了list接口的还有vector和stack。这里我们暂时不做讨论。Arraylist和Linkedlist从名字就可以看出他们一个基于数组实现一个基于链表实现。所以他们可能存在以下的区别： 1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 3.对于新增和删除操作add和remove，，LinedList比较占优势，因为ArrayList要移动数据。 下面我们来对他们的性能进行对比测试：首先我们对他们进行查找测试,我们这里进行二分查找测试：

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.List;import java.util.Random;{N=50000;public static List values;static{Integer[] vals=new Integer[N];Random r=new Random();for(int i=0,currval=0;i<N;i++){vals[i]=new Integer(currval);currval+=r.nextInt(100)+1;}values=Arrays.asList(vals);}static long timeList(List lst){long start=System.currentTimeMillis();for(int i=0;i<N;i++){@SuppressWarnings(“unchecked”)int index=Collections.binarySearch(lst, values.get(i));if(index!=i)System.out.println(“***错误***”);}return System.currentTimeMillis()-start;}(String args[]){System.out.println(“ArrayList消耗时间：”+timeList(new ArrayList(values)));System.out.println(“LinkedList消耗时间：”+timeList(new LinkedList(values)));} }

结果为：

由此可见第二条是对的。 下面我们来看看第三条对不对 第一种在首部插入

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.List;import java.util.Random;{N=50000;public static List values;static{Integer[] vals=new Integer[N];Random r=new Random();for(int i=0,currval=0;i<N;i++){vals[i]=new Integer(currval);currval+=r.nextInt(100)+1;}values=Arrays.asList(vals);}static long timeList(List lst){long start=System.currentTimeMillis();for(int i=0;i<N;i++){lst.add(0, N);}return System.currentTimeMillis()-start;}(String args[]){System.out.println(“ArrayList消耗时间：”+timeList(new ArrayList(values)));System.out.println(“LinkedList消耗时间：”+timeList(new LinkedList(values)));} }

结果

从插入第一个元素看的确是linkedlist更快，但是我们接着看插入到追后一个元素：

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.List;import java.util.Random;{N=50000;public static List values;static{Integer[] vals=new Integer[N];Random r=new Random();for(int i=0,currval=0;i<N;i++){vals[i]=new Integer(currval);currval+=r.nextInt(100)+1;}values=Arrays.asList(vals);}static long timeList(List lst){long start=System.currentTimeMillis();for(int i=0;i<N;i++){lst.add(N, N);//改为插入到追后一个元素}return System.currentTimeMillis()-start;}(String args[]){System.out.println(“ArrayList消耗时间：”+timeList(new ArrayList(values)));System.out.println(“LinkedList消耗时间：”+timeList(new LinkedList(values)));} }

结果：

现在反而是arrylist速度更快，而且快了好多。相差几乎十倍。 接下来我们再看随机插入：

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.List;import java.util.Random;{N=50000;public static List values;static{Integer[] vals=new Integer[N];Random r=new Random();for(int i=0,currval=0;i<N;i++){vals[i]=new Integer(currval);currval+=r.nextInt(100)+1;}values=Arrays.asList(vals);}static long timeList(List lst){Random r=new Random();long start=System.currentTimeMillis();for(int i=0;i<N;i++){lst.add(r.nextInt(N), N);}return System.currentTimeMillis()-start;}(String args[]){System.out.println(“ArrayList消耗时间：”+timeList(new ArrayList(values)));System.out.println(“LinkedList消耗时间：”+timeList(new LinkedList(values)));} } 不论你在什么时候开始，重要的是开始之後就不要停止