常見的Java List疑問

前言

在學時還有工作初期，看了市面上的Java教科書發現都沒有深入探討這些List底層與關鍵要素，都只教如何使用。但這個坑常常會在面試或是追蹤效能上體現出自己的不足，所以寫一篇文章鞏固自己的觀念

目標

搞清楚List中ArrayList & LinkedList & Vector

List

我目前開發最常使用的資料結構，因為ArrayList的方便性可以儲存各種物件。而真的只能用ArrayList去做這些處理嗎?如果遇到瓶頸還有甚麼解決方法呢?
接下來會以下方兩個討論去做比較

1. ArrayList & LinkedList
2. ArrayList & Vector

List & LinkedList

差別

1. 實作
   • List的底層結構是Object陣列
   • LinkedList是LinkedList資料結構，
     • 也就是在搜尋時是透過Node的連結做移動
2. 快速隨機存取
   • ArrayList實作RandomAccess而LinkedList沒有
     • 透過物件導向的概念這代表的ArrayList支持隨機存取但LinkedList沒有
   • LinkedList的資料結構本身是不支援隨機存取的，需要遍歷的方式才能找到元素
     • 可以看到LinkedList原始碼繼承AbstractSequentialList就可知道它需要遍歷抓取元素
   • ，而ArrayList只需要給index並且直接去找出陣列中的記憶體位置就可以取得元素，可以透過下方的程式碼觀察出差別。
   • 所以在get(index)方法中 ArrayList在正常條件下會優於LinkedList

ArratList

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

LinkedList

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
        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;
        }
    }

3. Add & Delete

   • ArrayList在一般add()的情況下複雜度是O(1)因為直接於陣列後方新增，但如果是要在第i個位置新增或刪除add(i, element)或是delete(i)那複雜度就會是O(n-i)，因為必須將新增或刪除後方的元素做位置上的調整。
   • LinkedList因為是Linked List資料結構，因此在位置上都不需做到位置的調整所以複雜度為O(1)

4. 記憶體空間

   • ArrayList需要彈性的新增，所以都會在固有長度上預留一定的空間
   • LinkedList儲存元素為node需要額外儲存上下節點的資訊所以每個元素都會花費較多的記憶體

段落Memo

1. 實作RandomAccess的資料結構，那可以優先考慮for迴圈的方式去搜尋資料，因為他是支援快速隨機存取的。
2. 未實作RandomAccess介面的資料結構，則優先選擇iterator遍歷的方式也就是現在常用的foreach方法（foreach底層也是透過iterator去對資料做處理）

ArrayList & Vector

1. Vector與ArrayList的操作大致上大同小異，不過最大的差別在於，Vector支持同步化操作(也就是若在多執行序處理資料時確保資料的一致性)，而ArrayList沒有支持同步化操作，
2. 同步化操作雖然可以確保一致性，但若是在沒有必要的時候使用(單執行序時)則會降低資料處理速度
3. 有興趣觀察Vector的朋友們可以到原始碼觀看Vector.class中的ListItr這個final class。

結論

其實還有許多的差異與使用場景可以去探討，但就等之後如果有遇到或使用到在來補充此文章搂!

參考

https://dotblogs.com.tw/jerryhuang0306/2016/01/30/020303
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md