ArrayList和LinkedList的大致區(qū)別：

1. ArrayList基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
2. 對于隨機(jī)訪問的get和set，ArrayList優(yōu)于LinkedList，因?yàn)長inkedList要移動指針。
3. 對于新增add和刪除remove操作，LinkedList優(yōu)于ArrayList，因?yàn)锳rrayList要移動數(shù)據(jù)。

接下來看下具體的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隨機(jī)訪問 arrayList 優(yōu)于 linkedList
     * 二分查找法使用的隨機(jī)訪問(random access)策略，而LinkedList是不支持快速的隨機(jī)訪問的。對一個LinkedList做隨機(jī)訪問所消耗的時間與這個list的大小是成比例的。而相應(yīng)的，在ArrayList中進(jìn)行隨機(jī)訪問所消耗的時間是固定的
     * @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;
    }

    /**
     * 比較 重復(fù)的在一個列表的開端插入一個元素 linkedList 優(yōu)于 arrayList
     * 利用Collections.reverse方法對列表進(jìn)行反轉(zhuǎn)時，linkedList性能就要好些。
     * 當(dāng)一個元素被加到ArrayList的最開端時，所有已經(jīng)存在的元素都會后移，這就意味著數(shù)據(jù)移動和復(fù)制上的開銷。相反的，將一個元素加到LinkedList的最開端只是簡單的未這個元素分配一個記錄，然后調(diào)整兩個連接。在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數(shù)據(jù)的比較，可以看到arrayList & linkedList在性能上各有優(yōu)缺點(diǎn)。

1. 兩者在列表末尾增加一個元素，所花的開銷都是固定的。對ArrayList而言，會在內(nèi)部數(shù)組中增加一項(xiàng)，指向所添加的元素，偶爾可能會導(dǎo)致對數(shù)組重新進(jìn)行分配；對LinkedList而言，這個開銷是統(tǒng)一的，會分配一個內(nèi)部Entry對象。
2. 在ArrayList的中間插入或刪除一個元素時，這個列表中剩余的元素都會被移動；而在LinkedList的中間插入或刪除一個元素的開銷是固定的。
3. LinkedList不支持高效的隨機(jī)元素訪問。
4. ArrayList的空間浪費(fèi)主要體現(xiàn)在list列表的結(jié)尾會預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個單元都需要消耗相當(dāng)?shù)目臻g。