1，兩個(gè)list簡(jiǎn)單概括。

ArrayList數(shù)據(jù)結(jié)構(gòu)就是數(shù)組（更確切的說(shuō)是動(dòng)態(tài)數(shù)組）

LinkedList數(shù)據(jù)結(jié)構(gòu)是雙向鏈表。

其他信息各位自行了解，隨便在哪都能搜到。這篇文章注重對(duì)性能對(duì)比。

2，添加元素

(建議大家實(shí)測(cè))

（1）從第一個(gè)位置添加

ArrayList<Integer> arrayList=new ArrayList<>();
        LinkedList<Integer> linkedList=new LinkedList<>();
        int times=100000;
        long t1=System.nanoTime();
        for (int i = 0; i < times; i++) {
            arrayList.add(0,i);
        }
        long t2=System.nanoTime();
        for (int i=0;i<times;i++){
            linkedList.addFirst(i);
        }
        long t3=System.nanoTime();

        System.out.println("arrayList:"+(t2-t1)/1000+"    linkedlist:"+(t3-t2)/1000);

結(jié)果

截屏2020-04-11下午5.42.05.png

很明顯，arraylist和linkedlist相比，在第一個(gè)位置添加元素 linkedlist要快很多。
分析：
linkedlist在頭部添加最終是執(zhí)行的這塊代碼

private void linkFirst(E e) {
       final Node<E> f = first;
       final Node<E> newNode = new Node<>(null, e, f);
       first = newNode;
       if (f == null)
           last = newNode;
       else
           f.prev = newNode;
       size++;
       modCount++;
   }

由于Linked維護(hù)了頭結(jié)點(diǎn)（first），代碼內(nèi)容無(wú)非就是改變引用的指向?qū)崿F(xiàn)插入節(jié)點(diǎn)。插入一個(gè)元素時(shí)間復(fù)雜度為O（1）。
而arrayList在頭部添加代碼實(shí)現(xiàn)：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

方法內(nèi)第一行代碼是檢查index位置是否合法，第三行則是檢查是否要擴(kuò)容。第四行代碼是通過(guò)arrayCopy方法實(shí)現(xiàn)插入位置及插入位置之后的的元素后移一位。第五行代碼則是插入元素。由于第四行代碼源碼我找不到，不過(guò)既然要后移一位，插入一個(gè)時(shí)間復(fù)雜度是O（n）。
由此便可知原因。

（2），在中間隨機(jī)添加元素。

測(cè)試代碼：

System.out.println("隨機(jī)插入測(cè)試");
        //testNanoTime();
        //testMillinsTime();
//        ArrayList<Integer> arrayList=new ArrayList<>();
//        LinkedList<Integer> linkedList=new LinkedList<>();
        //先填充五個(gè)元素
        for (int i = 0; i < 5; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        //次數(shù)
        int times=150000;

        //開(kāi)始進(jìn)行中間插入測(cè)試
        long t1=System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            arrayList.add(arrayList.size()/2,i);
        }
        long t2=System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            linkedList.add(linkedList.size()/2,i);
        }
        long t3=System.currentTimeMillis();

        System.out.println("arraylist:"+(t2-t1)+"  linkedlist:"+(t3-t2)+"  兩者倍數(shù)："+(t3-t2)/((t2-t1)*1.0));

結(jié)果

截屏2020-04-15上午12.59.22.png

分析：
(如果你自己嘗試的話你會(huì)驚奇的發(fā)現(xiàn)當(dāng)插入的數(shù)量越大時(shí)，耗時(shí)倍數(shù)越趨近于40倍)
很明顯arraylist在中間插入相同數(shù)量的元素反而比linkedlist快，很奇怪是嗎？當(dāng)我們學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候常識(shí)告訴我們鏈表插入比數(shù)組快。但是注意，數(shù)據(jù)結(jié)構(gòu)中的插入是單純的考慮插入這個(gè)動(dòng)作，而linkedlist，執(zhí)行remove，要通過(guò)這個(gè)方法：

截屏2020-04-15上午1.04.08.png

而這個(gè)方法的源碼是：

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

if判斷條件是根據(jù)index與長(zhǎng)度的二分之一比較，以此根據(jù)使用頭結(jié)點(diǎn)或者尾結(jié)點(diǎn)來(lái)定位元素位置。以此來(lái)盡可能提高效率。這個(gè)過(guò)程每定位一個(gè)元素，時(shí)間復(fù)雜度為O(n).
而arraylist依然是通過(guò)arrayCopy進(jìn)行移位，然后插入。對(duì)于每次操作時(shí)間復(fù)雜度依然為O(n)。雖然時(shí)間復(fù)雜度差不多，但是，arrayCopy方法的性能比linkedList中的定位過(guò)程效率高，如果你細(xì)心測(cè)試，你會(huì)發(fā)現(xiàn)插入的節(jié)點(diǎn)越多兩者耗時(shí)倍數(shù)越接近40倍。以此得出結(jié)論，在中間插入arraylist比Linkedlist效率高。

（3）, 在尾結(jié)點(diǎn)進(jìn)行插入。

貼上測(cè)試代碼：

public static void endAddtest(){
        System.out.println("尾部插入測(cè)試");
        testNanoTime();
        testMillinsTime();
        ArrayList<Integer> arrayList=new ArrayList<>();
        LinkedList<Integer> linkedList=new LinkedList<>();
        int times=10000000;
        long t1=System.nanoTime();
        for (int i = 0; i < times; i++) {
            arrayList.add(i);
        }
        long t2=System.nanoTime();
        for (int i=0;i<times;i++){
            linkedList.addLast(i);
        }
        long t3=System.nanoTime();

        System.out.println("arrayList:"+(t2-t1)/1000+"    linkedlist:"+(t3-t2)/1000);
    }

截屏2020-04-15上午1.23.53.png

兩者差距不大（通過(guò)多次嘗試依然是arraylist較快），具體原因通過(guò)以上分析很容易理解。
arraylist，里面首先判斷是否擴(kuò)容，然后進(jìn)行插入。linkedlist直接在尾結(jié)點(diǎn)插入。
貼上源碼，不做過(guò)多贅述。
arraylist:

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

linkedlist:

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;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

總結(jié)：arraylist在尾結(jié)點(diǎn)插入比linkedlist速度略快。

3,刪除節(jié)點(diǎn)。

刪除節(jié)點(diǎn)與添加節(jié)點(diǎn)一樣。不做過(guò)多贅述。
刪除第一個(gè)節(jié)點(diǎn)，arraylist比linekdlist慢
刪除中間節(jié)點(diǎn)和在中間添加節(jié)點(diǎn)結(jié)論一樣，arraylist比linkedlist快。
刪除最后一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度時(shí)間復(fù)雜度雖然一樣，但是arraylist比linkedlist略快。

4，遍歷

實(shí)測(cè)，結(jié)論，
arraylist中的遍歷方式耗時(shí)比較：
fori<foreach<itreator，注意，這里foreach位置不一定，有時(shí)快有時(shí)慢，與環(huán)境和list長(zhǎng)度有關(guān)。

linkedlist遍歷耗時(shí)：
fori>foreach>iterator,注意foreach同上，耗時(shí)不穩(wěn)定。

（網(wǎng)上有種說(shuō)話：foreach底層也是用迭代器。對(duì)此我沒(méi)有深入研究，先且相信這個(gè)結(jié)論）

最后貼上總結(jié)論：

image.png