java - studio - list arraylist linkedlist




何時在Java中使用LinkedList over ArrayList? (20)

我一直只是一個人使用:

List<String> names = new ArrayList<>();

我使用接口作為可移植性的類型名稱,因此當我問這些問題時,我可以重新編寫代碼。

何時應該使用LinkedList而不是ArrayList ,反之亦然?


ArrayList並且LinkedList這兩種工具List interface及其方法和結果幾乎相同。然而,它們之間幾乎沒有差別,這取決於要求,使一個優於另一個。

ArrayList與LinkedList

1)與Search: ArrayList搜索操作相比,LinkedList搜索操作非常快。get(int index)ArrayList給出的性能O(1),而LinkedList性能O(n)

Reason: ArrayList維護其元素的基於索引的系統,因為它隱式使用數組數據結構,這使得搜索列表中的元素更快。另一方面LinkedList實現雙向鍊錶,這需要遍歷所有元素以搜索元素。

2)Deletion: LinkedList刪除操作提供O(1)性能同時ArrayList提供可變性能:O(n)在最壞的情況下(在刪除第一個元素時)和O(1)最好的情況下(刪除最後一個元素時)。

結論:與ArrayList相比,LinkedList元素刪除更快。

原因:LinkedList的每個元素都維護著兩個指針(地址),這些指針指向列表中的兩個鄰居元素。因此,移除僅需要改變將要移除的節點的兩個相鄰節點(元素)中的指針位置。在In ArrayList中,需要移動所有元素以填充由remove元素創建的空間。

3)Inserts Performance: LinkedList添加方法給出O(1)的性能,同時ArrayList使O(n)在最壞的情況。原因與刪除時解釋的相同。

4)Memory Overhead: ArrayList維護索引和元素數據,同時LinkedList維護元素數據和鄰居節點的兩個指針

因此,LinkedList中的內存消耗相對較高。

這些類之間幾乎沒有相似之處,如下所示:

  • ArrayList和LinkedList都是List接口的實現。
  • 它們都維護元素的插入順序,這意味著在顯示ArrayList和LinkedList元素時,結果集將具有將元素插入List的相同順序。
  • 這兩個類都是非同步的,可以使用Collections.synchronizedList方法顯式同步。
  • iteratorlistIterator返回的這些類fail-fast(如果名單在任何時間從結構上修改創建迭代器之後,以任何方式,除了通過iterator's自身的remove或add方法,迭代器都將throwConcurrentModificationException)。

何時使用LinkedList以及何時使用ArrayList?

  • 由於插入上述解釋和刪除操作提供良好的性能(O(1))LinkedList相比ArrayList(O(n))

    因此,如果在應用程序中需要頻繁添加和刪除,則LinkedList是最佳選擇。

  • Search(get method)操作很快Arraylist (O(1))但不在LinkedList (O(n))

    因此,如果添加和刪除操作較少以及搜索操作要求較多,則ArrayList將是您最好的選擇。


ArrayList就是你想要的。 LinkedList幾乎總是(性能)錯誤。

為什麼LinkedList糟糕:

  • 它使用大量小內存對象,因此會影響整個過程的性能。
  • 很多小對像都不利於緩存局部性。
  • 任何索引操作都需要遍歷,即具有O(n)性能。 這在源代碼中並不明顯,導致算法O(n)比使用ArrayList時慢。
  • 獲得良好的表現很棘手。
  • 即使big-O性能與ArrayList相同,它也可能會明顯變慢。
  • 在源代碼中看到LinkedList是很不耐煩的,因為它可能是錯誤的選擇。

ArrayList本質上是一個數組。 LinkedList實現為雙鍊錶。

get很清楚。 對於ArrayList ,O(1),因為ArrayList允許使用索引進行隨機訪問。 對於LinkedList ,O(n),因為它需要首先找到索引。 注意:有不同版本的addremove

LinkedList在添加和刪除方面更快,但在get中更慢。 簡而言之,如果出現以下情況,應首選LinkedList

  1. 沒有大量的隨機訪問元素
  2. 有大量的添加/刪除操作

=== ArrayList ===

  • 添加(E e)
    • 在ArrayList的末尾添加
    • 需要內存調整成本。
    • O(n)最差,O(1)攤銷
  • add(int index,E element)
    • 添加到特定的索引位置
    • 需要轉移和可能的內存調整成本
    • 上)
  • remove(int index)
    • 刪除指定的元素
    • 需要轉移和可能的內存調整成本
    • 上)
  • 刪除(對象o)
    • 從此列表中刪除指定元素的第一個匹配項
    • 需要首先搜索元素,然後轉移和可能的內存調整大小成本
    • 上)

=== LinkedList ===

  • 添加(E e)

    • 添加到列表的末尾
    • O(1)
  • add(int index,E element)

    • 插入指定位置
    • 需要先找到位置
    • 上)
  • 去掉()
    • 刪除列表的第一個元素
    • O(1)
  • remove(int index)
    • 刪除具有指定索引的元素
    • 需要先找到元素
    • 上)
  • 刪除(對象o)
    • 刪除指定元素的第一個匹配項
    • 需要先找到元素
    • 上)

這是programcreek.com的圖( addremove是第一種類型,即在列表末尾添加元素並刪除列表中指定位置的元素。):


1)基礎數據結構

ArrayList和LinkedList之間的第一個區別在於ArrayList由Array支持,而LinkedList由LinkedList支持。這將導致性能的進一步差異。

2)LinkedList實現了Deque

ArrayList和LinkedList之間的另一個區別是,除了List接口之外,LinkedList還實現了Deque接口,它為add()和poll()以及其他幾個Deque函數提供先進先出操作。3)在ArrayList中添加元素在ArrayList中添加元素是O(1)操作,如果它不觸發Array的重新大小,在這種情況下它變為O(log(n)),另一方面,添加一個元素LinkedList是O(1)操作,因為它不需要任何導航。

4)從位置移除元素

為了從特定索引中刪除元素,例如通過調用remove(index),ArrayList執行複制操作,使其接近O(n),而LinkedList需要遍歷到該點,這也使得它成為O(n / 2)因為它可以基於接近度從任一方向穿過。

5)迭代ArrayList或LinkedList

迭代是LinkedList和ArrayList的O(n)操作,其中n是元素的數量。

6)從位置檢索元素

get(index)操作在ArrayList中是O(1),而在LinkedList中是O(n / 2),因為它需要遍歷到該條目。雖然,在Big O表示法O(n / 2)只是O(n),因為我們忽略那裡的常數。

7)記憶

LinkedList使用包裝器對象Entry,它是一個靜態嵌套類,用於存儲數據和下一個和上一個節點,而ArrayList只是將數據存儲在Array中。

因此,對於ArrayList而言,內存需求似乎少於LinkedList,除非Array在將內容從一個Array複製到另一個Array時執行重新大小操作。

如果Array足夠大,那麼此時可能需要大量內存並觸發垃圾收集,這會減慢響應時間。

從ArrayList與LinkedList之間的所有上述差異來看,幾乎在所有情況下,看起來ArrayList是比LinkedList更好的選擇,除非你執行頻繁的add()操作而不是remove()或get()。

修改鍊錶比ArrayList更容易,特別是如果要從開始或結束添加或刪除元素,因為鍊錶在內部保留對這些位置的引用,並且可以在O(1)時間內訪問它們。

換句話說,您不需要遍歷鍊錶以到達要添加元素的位置,在這種情況下,添加變為O(n)操作。例如,在鏈接列表的中間插入或刪除元素。

在我看來,對於Java中的大多數實際用途,使用LinkedList而不是LinkedList。


摘要 ArrayListArrayDeque在更多用例中比LinkedList更可取。 如果您不確定 - 只需從ArrayList開始。

LinkedListArrayList是List接口的兩種不同實現。 LinkedList使用雙向LinkedList實現它。 ArrayList使用動態重新調整大小的數組來實現它。

與標準鍊錶和數組操作一樣,各種方法將具有不同的算法運行時。

對於LinkedList<E>

  • get(int index)O(n) (平均n / 4步)
  • add(E element)O(1)
  • add(int index, E element)O(n) (平均n / 4步),但當index = 0O(1) <--- LinkedList<E>主要好處LinkedList<E>
  • remove(int index)O(n) (平均n / 4步)
  • Iterator.remove()O(1) 。 <--- LinkedList<E>主要好處
  • ListIterator.add(E element)O(1)這是LinkedList<E>的主要優點之一

注意:許多操作平均需要n / 4步,最佳情況下需要恆定步數(例如索引= 0),最壞情況下需要n / 2步(列表中間)

對於ArrayList<E>

  • get(int index)O(1) <--- ArrayList<E>主要好處
  • add(E element)O(1)攤銷,但是O(n)最壞情況,因為必須調整和復制數組
  • add(int index, E element)O(n) (平均n / 2步)
  • remove(int index)O(n) (平均n / 2步)
  • Iterator.remove()O(n) (平均n / 2步)
  • ListIterator.add(E element)O(n) (平均n / 2步)

注意:許多操作平均需要n / 2步,最好的情況下是常數步(列表末尾),最壞情況下是n步(列表開頭)

LinkedList<E>允許使用迭代器進行常量時間插入或刪除,但只允許順序訪問元素。 換句話說,您可以向前或向後遍歷列表,但在列表中查找位置需要的時間與列表的大小成比例。 Javadoc說“索引到列表中的操作將從開頭或結尾遍歷列表,以較近者為準” ,因此這些方法平均為O(n)n / 4步),但index = 0 O(1) index = 0

另一方面, ArrayList<E>允許快速隨機讀取訪問,因此您可以在恆定時間內獲取任何元素。 但是,除了末端之外的任何地方添加或移除都需要將所有後面的元素移位,以便打開或填補空白。 此外,如果添加的元素多於底層數組的容量,則會分配一個新數組(大小的1.5倍),並將舊數組複製到新數組,因此添加到ArrayListO(n)最壞的情況,但平均不變。

因此,根據您打算執行的操作,您應該相應地選擇實現。 迭代任何一種List實際上同樣便宜。 (迭代一個ArrayList在技​​術上更快,但除非你做的事情對性能非常敏感,否則你不應該擔心這一點 - 它們都是常量。)

當您重用現有迭代器來插入和刪除元素時,會出現使用LinkedList的主要好處。 然後,可以通過僅在本地更改列表,在O(1)中完成這些操作。 在數組列表中,需要移動 (即復制)數組的其餘部分。 另一方面,在LinkedList意味著在最壞情況下遵循O(n)n / 2步)中的鏈接,而在ArrayList ,可以在數學上計算所需位置並在O(1)中訪問。

當您從列表的頭部添加或刪除時,會出現使用LinkedList另一個好處,因為這些操作是O(1) ,而它們是ArrayList O(n) 。 請注意, ArrayDeque可能是LinkedList一個很好的替代品,用於添加和刪除頭部,但它不是List

此外,如果您有大型列表,請記住內存使用情況也不同。 LinkedList每個元素都有更多的開銷,因為還存儲了指向下一個和前一個元素的指針。 ArrayLists沒有這種開銷。 但是,無論是否實際添加了元素, ArrayLists都會佔用為容量分配的內存。

ArrayList的默認初始容量非常小(Java 1.4中的10個 - 1.8)。 但由於底層實現是一個數組,因此如果添加大量元素,則必須調整數組大小。 當您知道要添加大量元素時,為了避免調整大小的高成本,請構造具有更高初始容量的ArrayList


ArrayList和LinkedList各有利弊。

與使用指向下一個節點的指針的LinkedList相比,ArrayList使用連續的內存地址。因此,當您想要查找ArrayList中的元素比使用LinkedList進行n次迭代更快時。

另一方面,LinkedList中的插入和刪除更容易,因為您只需更改指針,而ArrayList意味著使用shift操作進行任何插入或刪除。

如果您的應用程序中有頻繁的檢索操作,請使用ArrayList。如果頻繁插入和刪除,請使用LinkedList。


作為一個在非常大規模的SOA Web服務上進行操作性能工程大約十年的人,我更喜歡LinkedList相對於ArrayList的行為。 雖然LinkedList的穩態吞吐量更差,因此可能導致購買更多硬件 - ArrayList在壓力下的行為可能導致集群中的應用程序在幾乎同步的情況下擴展其陣列,並且對於大型陣列可能導致缺乏響應性在應用程序和停電,而在壓力下,這是災難性的行為。

類似地,您可以從默認吞吐量終身垃圾收集器中獲得更好的應用程序吞吐量,但是一旦獲得具有10GB堆的Java應用程序,您可以在完整GC期間鎖定應用程序25秒,這會導致SOA應用程序超時和失敗並且如果太頻繁發生,則會破壞您的SLA。 即使CMS收集器佔用更多資源並且無法實現相同的原始吞吐量,但它是一個更好的選擇,因為它具有更可預測和更小的延遲。

如果性能的全部意思是吞吐量,並且您可以忽略延遲,那麼ArrayList只是性能的更好選擇。 根據我的工作經驗,我不能忽視最壞情況的延遲。


到目前為止,似乎沒有人解決這些列表中每個列表的內存佔用情況,除了一般認為LinkedListArrayList “更多”所以我做了一些數字處理以準確地證明兩個列表佔用了多少N個空引用。

由於在它們的相對系統上引用是32位或64位(即使為空),我已經為32位和64位LinkedListsArrayLists包含了4組數據。

注意: ArrayList行顯示的大小用於修剪列表 - 實際上, ArrayList支持數組的容量通常大於其當前元素數。

注2 :( 感謝BeeOnRope)由於CompressedOops現在默認從JDK6中間開始,因此64位機器的下面的值基本上與它們的32位機器相匹配,除非您特別關閉它。

結果清楚地表明LinkedListArrayList更多,特別是元素數量非常多。 如果內存是一個因素,請避開LinkedLists

我使用的公式如下,讓我知道如果我做錯了什麼我會解決它。 對於32位或64位系統,'b'為4或8,'n'是元素的數量。 注意mods的原因是因為java中的所有對象將佔用8個字節空間的倍數,無論它是否全部使用。

ArrayList

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

是的,我知道,這是一個古老的問題,但我會投入兩分錢:

在性能方面,LinkedList 幾乎總是錯誤的選擇。 有一些非常具體的算法需要一個LinkedList,但那些非常非常罕見,並且算法通常特別依賴於LinkedList能夠相對快速地插入和刪除列表中間的元素,一旦你在那裡導航使用ListIterator。

有一個常見的用例,其中LinkedList優於ArrayList:隊列的那個。 但是,如果您的目標是性能,而不是LinkedList,您還應該考慮使用ArrayBlockingQueue(如果您可以提前確定隊列大小的上限,並且可以預先分配所有內存),或者此CircularArrayList實現 。 (是的,它是從2001年開始的,所以你需要對它進行一般化,但我的性能比率與剛剛在最近的JVM中引用的內容相當)


正確或不正確:請在本地執行測試並自行決定!

LinkedList編輯/刪除比ArrayList更快。

Array支持的ArrayList ,需要大小的兩倍,在大容量應用程序中更糟糕。

下面是每個操作的單位測試結果。時間以納秒為單位。

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

這是代碼:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

這取決於您將在列表上執行哪些操作。

ArrayList更快地訪問索引值。插入或刪除對象時要糟糕得多。

要了解更多信息,請閱讀任何討論數組和鏈接列表之間差異的文章。


這是一個效率問題。 LinkedList可以快速添加和刪除元素,但訪問特定元素的速度很慢。 ArrayList可以快速訪問特定元素,但添加到任何一端都很慢,特別是在中間刪除速度很慢。

Array和ArrayList vs LinkedList vs Vector的內容更加深入, Linked List也是如此


ArrayList中的操作get(i)比LinkedList快,因為:
ArrayList: List接口的Resizable-array實現
LinkedList: List和Deque接口的雙鏈接列表實現

索引到列表中的操作將從開頭或結尾遍歷列表,以較接近指定索引為準。


ArrayList擴展了AbstractList並實現了List接口。ArrayList是動態數組。
可以說它基本上是為了克服數組的缺點而創建

的.LinkedList類擴展了AbstractSequentialList並實現了List,Deque和Queue接口。
性能
arraylist.get()是O(1)而linkedlist.get()O(n)
arraylist.add()是O(1)並且linkedlist.add()0(1)
arraylist.contains()是O(n)並且linkedlist.contains()O(n)
arraylist.next()是O(1)並且linkedlist.next()O(1)
arraylist.remove()是O(n)而linkedlist.remove()是O(1)
在arraylist中
iterator.remove()是O(n)
而在鍊錶中
iterator.remove()是O(1)


如果你的代碼有add(0)remove(0),使用a LinkedList和它更漂亮addFirst()removeFirst()方法。否則,請使用ArrayList

當然,GuavaImmutableList是你最好的朋友。


我在這裡看到的其中一項測試只進行了一次測試。但我注意到你需要多次運行這些測試,最終它們的時間會收斂。基本上JVM需要預熱。對於我的特定用例,我需要添加/刪除項目到最後增加到約500項。在我的測試中LinkedList出現得更快,鏈接LinkedList大約50,000 NS並且ArrayList大約90,000 NS ...接受或接受。請參閱下面的代碼。

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

數組列表本質上是一個數組,其中包含添加項等的方法(您應該使用通用列表)。它是可以通過索引器訪問的項目集合(例如[0])。它意味著從一個項目到下一個項目的進展。

鍊錶指定從一個項目到下一個項目的進度(項目a - >項目b)。您可以使用數組列表獲得相同的效果,但鏈接列表絕對說明應該跟隨前一個項目。



鍊錶的一個重要特徵(我在另一個答案中沒有讀到)是兩個列表的串聯。對於數組,這是O(n)(+一些重新分配的開銷),鏈接列表只有O(1)或O(2);-)

重要:對於Java來說,LinkedList這不是真的!請參閱Java中的鍊錶有快速連接方法嗎?


除了上面的其他好的參數,你應該注意ArrayListimplements RandomAccess接口,而LinkedList實現Queue

因此,他們以某種方式解決了稍微不同的問題,效率和行為的差異(參見他們的方法列表)。





linked-list