iT邦幫忙

0

常見的Java List疑問 (ArrayList/LinkedList/Vector)

常見的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;
        }
    }
  1. Add & Delete

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

    • 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


1 則留言

0
obelisk0114
iT邦新手 5 級 ‧ 2019-11-23 16:58:30

List & LinkedList
差別
實作
List的底層結構是Object陣列
LinkedList是LinkedList資料結構

所有的 List 都要改為 ArrayListListinterface
LinkedList 同時也實作 Deque,因此有 polloffer

我要留言

立即登入留言