arrayList & linkedList

ArrayList和LinkedList的大致区别：

1. ArrayList基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问的get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
3. 对于新增add和删除remove操作，LinkedList优于ArrayList，因为ArrayList要移动数据。

接下来看下具体的demo，来比较下两者的性能。

public class ListDemo {
    public static final int N=50000;

    public static List values;

    public static void main(String args[]){
        create();
        System.out.println("ArrayList消耗时间："+removeTime(new ArrayList(values)));
        System.out.println("LinkedList消耗时间："+removeTime(new LinkedList(values)));
    }

    static void create(){
        Integer vals[]=new Integer[N];

        Random r=new Random();

        for(int i=0,currentVal=0;i<N;i++){
            vals[i] = currentVal;
            currentVal+=r.nextInt(100)+1;
        }

        values=Arrays.asList(vals);
    }

    /**
     * 比较 get随机访问 arrayList 优于 linkedList
     * 二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的
     * @param lst
     * @return
     */
    static long getTime(List lst){
        long start=System.currentTimeMillis();
        for(int i=0;i<N;i++){
            int index=Collections.binarySearch(lst, values.get(i));
            if(index!=i)
                System.out.println("***错误***");
        }
        return System.currentTimeMillis()-start;
    }

    /**
     * 比较 重复的在一个列表的开端插入一个元素 linkedList 优于 arrayList
     * 利用Collections.reverse方法对列表进行反转时，linkedList性能就要好些。
     * 当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。
     * @param list
     * @return
     */
    static long addTime(List list){
        long start=System.currentTimeMillis();
        Object o = new Object();
        for(int i=0;i<N;i++){
            list.add(0, o);
        }
        return System.currentTimeMillis()-start;
    }

    static long removeTime(List list){
        long start=System.currentTimeMillis();
        Object o = new Object();
        for(int i=0;i<N;i++){
            list.remove(0);
        }
        return System.currentTimeMillis()-start;
    }

}

从demo数据的比较，可以看到arrayList & linkedList在性能上各有优缺点。

1. 两者在列表末尾增加一个元素，所花的开销都是固定的。对ArrayList而言，会在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；对LinkedList而言，这个开销是统一的，会分配一个内部Entry对象。
2. 在ArrayList的中间插入或删除一个元素时，这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3. LinkedList不支持高效的随机元素访问。
4. ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个单元都需要消耗相当的空间。