Kiedy używać LinkedList zamiast ArrayList w Javie?

Zawsze byłam osobą, która po prostu używa:

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

Używam interfejsu jako nazwy typu dla przenośności , więc kiedy zadaję takie pytania, mogę przerobić mój kod.

Kiedy należy LinkedListstosować na ArrayListodwrót?

Podsumowanie ArrayList z ArrayDequejest lepsze w znacznie większej liczbie przypadków użycia niż LinkedList. Jeśli nie jesteś pewien - zacznij od ArrayList.

LinkedListi ArrayListsą dwiema różnymi implementacjami interfejsu List. LinkedListimplementuje go z podwójnie połączoną listą. ArrayListimplementuje go za pomocą dynamicznie zmieniającej się tablicy.

Podobnie jak w przypadku standardowych połączonych operacji na liście i tablicach, różne metody będą miały różne środowiska uruchomieniowe algorytmu.

Dla LinkedList<E>

• get(int index)to O (n) ( średnio n / 4 kroki), ale O (1), gdy index = 0lub index = list.size() - 1(w tym przypadku możesz także użyć getFirst()i getLast()). Jedną z głównych zalet LinkedList<E>
• add(int index, E element)to O (n) ( średnio z n / 4 krokami), ale O (1), gdy index = 0lub index = list.size() - 1(w tym przypadku można również użyć addFirst()i addLast()/ add()). Jedną z głównych zalet LinkedList<E>
• remove(int index)to O (n) ( średnio n / 4 kroki), ale O (1), gdy index = 0lub index = list.size() - 1(w tym przypadku możesz także użyć removeFirst()i removeLast()). Jedną z głównych zalet LinkedList<E>
• Iterator.remove()oznacza O (1) . Jedną z głównych zalet LinkedList<E>
• ListIterator.add(E element)oznacza O (1) . Jedną z głównych zalet LinkedList<E>

^{Uwaga: wiele operacji wymaga n / 4 średnio kroków, stałej liczby kroków w najlepszym przypadku (np. Indeks = 0) i n / 2 kroków w najgorszym przypadku (środek listy)}

Dla ArrayList<E>

• get(int index)to O (1) . Główną zaletą ArrayList<E>
• add(E element)to O (1) amortyzowane przez , ale w najgorszym przypadku O (n), ponieważ rozmiar tablicy musi zostać zmieniony i skopiowany
• add(int index, E element)to O (n) ( średnio n / 2 kroki)
• remove(int index)to O (n) ( średnio n / 2 kroki)
• Iterator.remove()to O (n) ( średnio n / 2 kroki)
• ListIterator.add(E element)oznacza O (n) (zśrednio n / 2 kroki)

^{Uwaga: wiele operacji wymaga średnio n / 2 kroków, stałych liczby kroków w najlepszym przypadku (koniec listy), n kroków w najgorszym przypadku (początek listy)}

LinkedList<E>pozwala na wstawianie lub usuwanie w stałym czasie za pomocą iteratorów , ale tylko sekwencyjny dostęp do elementów. Innymi słowy, możesz przejść listę do przodu lub do tyłu, ale znalezienie pozycji na liście zajmuje czas proporcjonalny do wielkości listy. Javadoc mówi: „operacje indeksujące listę będą przechodzić przez listę od początku lub końca, w zależności od tego, co jest bliższe” , więc te metody to średnio O (n) ( n / 4 kroki), chociaż O (1) dla index = 0.

ArrayList<E>, z drugiej strony, umożliwia szybki losowy dostęp do odczytu, dzięki czemu można pobrać dowolny element w stałym czasie. Ale dodawanie lub usuwanie z dowolnego miejsca poza końcem wymaga przesunięcia wszystkich ostatnich elementów, aby zrobić otwór lub wypełnić lukę. Ponadto, jeśli dodasz więcej elementów niż pojemność tablicy bazowej, przydzielana jest nowa tablica (1,5 razy większa), a stara tablica jest kopiowana do nowej, więc dodawanie doArrayList jest O (n) w najgorszym przypadek, ale średnio stały.

Dlatego w zależności od operacji, które zamierzasz wykonać, powinieneś odpowiednio wybrać implementacje. Iterowanie po każdym rodzaju listy jest praktycznie równie tanie. (Iteracja ArrayListjest technicznie szybsza, ale jeśli nie robisz czegoś naprawdę wrażliwego na wydajność, nie powinieneś się tym przejmować - oba są stałe.)

Główne zalety używania LinkedListpowstają, gdy ponownie wykorzystujesz istniejące iteratory do wstawiania i usuwania elementów. Operacje te można następnie wykonać w O (1) , zmieniając listę tylko lokalnie. Na liście tablic pozostałą część tablicy należy przenieść (tzn. Skopiować). Z drugiej strony, szukanie w LinkedListsposób podążający za linkami w O (n) ( n / 2 krokach) w najgorszym przypadku, podczas gdy w ArrayListpożądanej pozycji można obliczyć matematycznie i uzyskać dostęp w O (1) .

Kolejna korzyść z używania LinkedListpojawia się, gdy dodajesz lub usuwasz z nagłówka listy, ponieważ te operacje to O (1) , podczas gdy są one O (n) dla ArrayList. Pamiętaj, że ArrayDequemoże to być dobra alternatywa dlaLinkedList dla dodawania i usuwania z głowy, ale nie jest to List.

Ponadto, jeśli masz duże listy, pamiętaj, że użycie pamięci jest również inne. Każdy element a LinkedListma większy narzut, ponieważ przechowywane są również wskaźniki do następnego i poprzednich elementów. ArrayListsnie mam tego narzutu. Jednak,ArrayLists zajmij tyle pamięci, ile jest przydzielone dla pojemności, niezależnie od tego, czy elementy zostały rzeczywiście dodane.

Domyślna początkowa pojemność ArrayListjest dość mała (10 z Java 1.4 - 1.8). Ponieważ jednak podstawową implementacją jest tablica, należy zmienić jej rozmiar, jeśli dodasz wiele elementów. Aby uniknąć wysokich kosztów zmiany rozmiaru, gdy wiesz, że zamierzasz dodać wiele elementów, stwórz ArrayListwiększą pojemność początkową.

Jak dotąd wydaje się, że nikt nie zajął się śladami pamięci każdej z tych list oprócz ogólnego konsensusu, że a LinkedListjest „o wiele więcej” niżArrayList tak, więc zrobiłem pewne chrupanie liczb, aby pokazać dokładnie, ile obie listy zajmują dla zerowych referencji.

Ponieważ referencje mają 32 lub 64 bity (nawet gdy są zerowe) w ich systemach względnych, dołączyłem 4 zestawy danych dla 32 i 64 bitów LinkedListsi ArrayLists.

Uwaga: Rozmiary pokazane dla ArrayListlinii są dla przyciętych list - W praktyce pojemność tablicy podkładowej w ArrayListjest ogólnie większa niż bieżąca liczba elementów.

Uwaga 2: (dzięki BeeOnRope) Ponieważ CompressedOops jest teraz domyślny od połowy JDK6 i wyższych, poniższe wartości dla komputerów 64-bitowych będą w zasadzie pasowały do ​​ich 32-bitowych odpowiedników, chyba że specjalnie je wyłączysz.

Wynik wyraźnie pokazuje, że LinkedListjest to o wiele więcej niż ArrayList, szczególnie przy bardzo dużej liczbie elementów. Jeśli ważna jest pamięć, omijaj ją LinkedLists.

Formuły, których użyłem, są następujące. Daj mi znać, jeśli zrobiłem coś złego, i naprawię to. „b” wynosi 4 lub 8 dla systemów 32- lub 64-bitowych, a „n” oznacza liczbę elementów. Zauważ, że powodem modyfikacji jest to, że wszystkie obiekty w Javie zajmą wielokrotność 8-bajtowej przestrzeni, niezależnie od tego, czy wszystko jest używane, czy nie.

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)

Połączona lista:

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)

ArrayListjest tym, czego chcesz. LinkedListjest prawie zawsze błędem (wydajnościowym).

Dlaczego LinkedListjest do bani:

• Wykorzystuje wiele małych obiektów pamięci, a zatem wpływa na wydajność całego procesu.
• Wiele małych obiektów jest szkodliwych dla lokalizacji pamięci podręcznej.
• Każda operacja indeksowana wymaga przejścia, tzn. Ma wydajność O (n). Nie jest to oczywiste w kodzie źródłowym, co prowadzi do algorytmów O (n) wolniejszych niż w przypadku ArrayListużycia.
• Uzyskiwanie dobrej wydajności jest trudne.
• Nawet jeśli wydajność big-O jest taka sama ArrayList, prawdopodobnie i tak będzie znacznie wolniejsza.
• Widzisz LinkedListw źródle niepokojące, ponieważ prawdopodobnie jest to zły wybór.

Jako ktoś, kto zajmuje się inżynierią wydajności operacyjnej w bardzo dużych serwisach internetowych SOA od około dekady, wolałbym zachowanie LinkedList nad ArrayList. Podczas gdy przepustowość w stanie ustalonym LinkedList jest gorsza, a zatem może prowadzić do zakupu większej ilości sprzętu - zachowanie ArrayList pod presją może prowadzić do rozszerzenia aplikacji w klastrze prawie synchronicznie, a dla dużych rozmiarów macierzy może prowadzić do braku reakcji w aplikacji i przestoju, będąc pod presją, co jest katastrofalnym zachowaniem.

Podobnie, możesz uzyskać lepszą przepustowość w aplikacji z domyślnego dzierżawionego śmietnika, ale gdy otrzymasz aplikacje Java z 10 GB hałdami, możesz skończyć blokowanie aplikacji na 25 sekund podczas pełnych GC, co powoduje przekroczenie limitu czasu i awarie w aplikacjach SOA i zdmuchuje twoje umowy SLA, jeśli występują zbyt często. Chociaż moduł zbierający CMS zajmuje więcej zasobów i nie osiąga tej samej surowej przepustowości, jest o wiele lepszym wyborem, ponieważ ma bardziej przewidywalne i mniejsze opóźnienia.

ArrayList jest lepszym wyborem dla wydajności, jeśli chodzi o przepustowość i można zignorować opóźnienia. Z mojego doświadczenia w pracy nie mogę zignorować opóźnień w najgorszym przypadku.

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algorytmy: Notacja Big-Oh

ArrayLists są dobre dla wielu-dodających-do-odczytu-wielu lub dołączających, ale złe przy dodawaniu / usuwaniu z przodu lub ze środka.

Tak, wiem, to starożytne pytanie, ale wrzucę moje dwa centy:

LinkedList jest prawie zawsze złym wyborem pod względem wydajności. Istnieje kilka bardzo specyficznych algorytmów, do których wzywa się LinkedList, ale są one bardzo, bardzo rzadkie, a algorytm zwykle zależy w szczególności od zdolności LinkedList do stosunkowo szybkiego wstawiania i usuwania elementów na środku listy, gdy już tam przejdziesz z ListIteratorem.

Istnieje jeden typowy przypadek użycia, w którym LinkedList przewyższa ArrayList: kolejka. Jeśli jednak Twoim celem jest wydajność, zamiast LinkedList powinieneś również rozważyć użycie ArrayBlockingQueue (jeśli możesz wcześniej ustalić górną granicę wielkości kolejki i stać Cię na przydzielenie całej pamięci z góry), lub tę implementację CircularArrayList . (Tak, pochodzi z 2001 roku, więc musisz go wygenerować, ale otrzymałem porównywalne wskaźniki wydajności do tego, co jest cytowane w tym artykule w ostatnim JVM)

To pytanie o efektywność. LinkedListjest szybki do dodawania i usuwania elementów, ale powolny dostęp do określonego elementu. ArrayListjest szybki do uzyskiwania dostępu do określonego elementu, ale może być powolny, aby dodać na każdym końcu, a szczególnie wolno, aby usunąć na środku.

Array vs ArrayList vs LinkedList vs Vector idzie głębiej, podobnie jak lista połączona .

Prawidłowe lub niepoprawne: proszę wykonać test lokalnie i sam zdecydować!

Edycja / Usuń jest szybsza LinkedListniż ArrayList.

ArrayList, wspierany przez Array, który musi być dwukrotnie większy, jest gorszy w aplikacjach o dużej objętości.

Poniżej znajduje się wynik testu jednostkowego dla każdej operacji. Czas trwania podano w nanosekundach.

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

Oto kod:

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);
    }
}

ArrayListjest w zasadzie tablicą. LinkedListjest zaimplementowany jako podwójnie połączona lista.

To getjest całkiem jasne. O (1) dla ArrayList, ponieważ ArrayListpozwalają na losowy dostęp przy użyciu indeksu. O (n) dla LinkedList, ponieważ najpierw musi znaleźć indeks. Uwaga: istnieją różne wersje addi remove.

LinkedListjest szybsze w dodawaniu i usuwaniu, ale wolniejsze. W skrócie, LinkedListnależy preferować, jeśli:

1. nie ma dużej liczby losowego dostępu do elementu
2. istnieje duża liczba operacji dodawania / usuwania

=== ArrayList ===

• dodaj (E e)
  • dodaj na końcu ArrayList
  • wymagają kosztu zmiany rozmiaru pamięci.
  • O (n) najgorsze, O (1) amortyzowane
• add (int index, element E)
  • dodaj do określonej pozycji indeksu
  • wymagają przesunięcia i ewentualnego kosztu zmiany rozmiaru pamięci
  • Na)
• usuń (int indeks)
  • usuń określony element
  • wymagają przesunięcia i ewentualnego kosztu zmiany rozmiaru pamięci
  • Na)
• usuń (Obiekt o)
  • usuń pierwsze wystąpienie określonego elementu z tej listy
  • najpierw trzeba wyszukać element, a następnie przesunąć i ewentualny koszt zmiany rozmiaru pamięci
  • Na)

=== LinkedList ===

• dodaj (E e)

  • dodaj na końcu listy
  • O (1)

• add (int index, element E)

  • wstaw w określonej pozycji
  • najpierw musisz znaleźć pozycję
  • Na)
• usunąć()
  • usuń pierwszy element listy
  • O (1)
• usuń (int indeks)
  • usuń element o określonym indeksie
  • najpierw musisz znaleźć element
  • Na)
• usuń (Obiekt o)
  • usuń pierwsze wystąpienie określonego elementu
  • najpierw musisz znaleźć element
  • Na)

Oto rysunek z programcreek.com ( addi removesą pierwszym typem, tj. Dodaj element na końcu listy i usuń element w określonej pozycji na liście.):

Joshua Bloch, autor LinkedList:

Czy ktoś faktycznie korzysta z LinkedList? Napisałem to i nigdy go nie używam.

Link: https://twitter.com/joshbloch/status/583813919019573248

Przepraszam za odpowiedź, że nie jest tak pouczająca jak inne odpowiedzi, ale pomyślałem, że będzie to najbardziej interesujące i zrozumiałe.

ArrayListjest losowo dostępny, a jednocześnie LinkedListjest bardzo tani w rozszerzaniu i usuwaniu elementów. W większości przypadków ArrayListjest w porządku.

Jeśli nie utworzysz dużych list i nie zmierzysz wąskiego gardła, prawdopodobnie nigdy nie będziesz musiał się martwić różnicą.

TL; DR dzięki nowoczesnej architekturze komputerowej ArrayListbędzie znacznie wydajniejszy w prawie każdym możliwym przypadku użycia - i dlatego LinkedListnależy go unikać, z wyjątkiem niektórych bardzo wyjątkowych i ekstremalnych przypadków.

Teoretycznie LinkedList ma O (1) dla add(E element)

Również dodanie elementu na środku listy powinno być bardzo wydajne.

Praktyka jest bardzo inna, ponieważ LinkedList jest strukturą wrogich danych w pamięci podręcznej . Z wydajności POV - w bardzo niewielu przypadkach wydajność LinkedListmoże być lepsza niż w przypadku pamięci podręcznej ArrayList .

Oto wyniki testu porównawczego wstawiania elementów w losowych lokalizacjach. Jak widać - lista tablic jest znacznie bardziej wydajna, chociaż teoretycznie każda wstawka na środku listy będzie wymagała „przesunięcia” n późniejszych elementów tablicy (im niższe wartości, tym lepiej):

Praca na sprzęcie nowej generacji (większe, wydajniejsze pamięci podręczne) - wyniki są jeszcze bardziej rozstrzygające:

LinkedList zajmuje znacznie więcej czasu, aby wykonać tę samą pracę. źródło kod źródłowy

Istnieją dwa główne powody:

1. Głównie - że węzły LinkedListsą rozproszone losowo w pamięci. RAM („Random Access Memory”) nie jest tak naprawdę losowy i bloki pamięci muszą zostać pobrane do pamięci podręcznej. Ta operacja wymaga czasu, a gdy takie pobieranie często się zdarza - strony pamięci w pamięci podręcznej muszą być cały czas wymieniane -> Brak pamięci podręcznej -> Pamięć podręczna nie jest wydajna. ArrayListelementy są przechowywane w ciągłej pamięci - właśnie do tego optymalizuje się nowoczesna architektura procesora.

2. Wtórne LinkedList wymagane do zatrzymania wskaźników do tyłu / do przodu, co oznacza 3-krotne zużycie pamięci na zapamiętaną wartość w porównaniu do ArrayList.

DynamicIntArray , btw, jest niestandardowym holdingiem implementującym ArrayListInt (typ pierwotny), a nie Obiekty - stąd wszystkie dane są naprawdę przechowywane w sąsiedztwie - a więc jeszcze bardziej wydajne.

Kluczowym elementem, o którym należy pamiętać, jest to, że koszt pobrania bloku pamięci jest większy niż koszt dostępu do pojedynczej komórki pamięci. Dlatego czytnik 1 MB pamięci sekwencyjnej jest do 400 razy szybszy niż odczyt tej ilości danych z różnych bloków pamięci:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Źródło: Liczby opóźnień, które powinien znać każdy programista

Aby wyjaśnić sprawę jeszcze bardziej, sprawdź poziom dodawania elementów na początku listy. Jest to przypadek użycia, w którym teoretycznie LinkedListpowinien naprawdę błyszczeć i ArrayListpowinien dawać słabe lub nawet gorsze wyniki:

Uwaga: jest to test porównawczy biblioteki C ++ Std lib, ale moje wcześniejsze doświadczenia wykazały, że wyniki C ++ i Java są bardzo podobne. Kod źródłowy

Kopiowanie sekwencyjną większość pamięci jest operacją optymalizowane przez współczesnych procesorów - zmiana teorii i faktycznie co znowu ArrayList/ Vectordużo bardziej wydajny

Kredyty: Wszystkie opublikowane tutaj testy porównawcze są tworzone przez Kjell Hedström . Jeszcze więcej danych można znaleźć na jego blogu

Jeśli twój kod ma add(0)i remove(0), użyj a LinkedListi jest ładniejsze addFirst()i removeFirst()metod. W przeciwnym razie użyj ArrayList.

I oczywiście, guawa „s ImmutableList jest twoim najlepszym przyjacielem.

Wiem, że to stary post, ale szczerze mówiąc, nie mogę uwierzyć, że nikt nie wspomniał o tym, że to LinkedListimplementuje Deque. Wystarczy spojrzeć na metody w Deque(i Queue); jeśli chcesz sprawiedliwego porównania, spróbuj uruchomić LinkedListprzed ArrayDequei zrobić funkcja-for-funkcji porównania.

Oto zapis Big-O w obu ArrayListi LinkedList, a także CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Połączona lista

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Na tej podstawie musisz zdecydować, co wybrać. :)

Porównajmy LinkedList i ArrayList wrt poniżej parametrów:

1. Wdrożenie

ArrayList to implementacja tablic o zmiennym rozmiarze dla interfejsu list, natomiast

LinkedList to implementacja podwójnie powiązanej listy interfejsu listy.

2. Wydajność

• get (int index) lub operacja wyszukiwania

  Operacja ArrayList get (int index) działa w stałym czasie, tj. O (1) while

  Czas działania operacji LinkedList get (int index) to O (n).

  Powodem, dla którego ArrayList jest szybszy niż LinkedList, jest to, że ArrayList używa systemu opartego na indeksie dla swoich elementów, ponieważ z drugiej strony wewnętrznie wykorzystuje strukturę danych tablicowych,

  LinkedList nie zapewnia dostępu opartego na indeksie dla swoich elementów, ponieważ wykonuje iterację od początku lub końca (w zależności od tego, co jest bliżej), aby pobrać węzeł o określonym indeksie elementu.

• operacja wstawiania () lub dodawania (obiektu)

  Wstawienia w LinkedList są na ogół szybkie w porównaniu do ArrayList. W LinkedList dodawanie lub wstawianie jest operacją O (1).

  Podczas gdy w ArrayList , jeśli tablica jest pełna, czyli w najgorszym przypadku, istnieje dodatkowy koszt zmiany rozmiaru tablicy i kopiowania elementów do nowej tablicy, co powoduje, że środowisko wykonawcze operacji dodawania w ArrayList O (n), w przeciwnym razie jest to O (1) .

• operacja remove (int)

  Operacja usuwania na LinkedList jest zasadniczo taka sama jak ArrayList, tj. O (n).

  W LinkedList istnieją dwie przeciążone metody usuwania. jeden to remove () bez żadnego parametru, który usuwa nagłówek listy i działa w stałym czasie O (1). Inną przeciążoną metodą remove w LinkedList jest remove (int) lub remove (Object), która usuwa Object lub int przekazane jako parametr. Ta metoda przegląda LinkedList, dopóki nie znajdzie obiektu i odłączy go od oryginalnej listy. Dlatego środowisko wykonawcze tej metody to O (n).

  Podczas gdy w ArrayList metoda remove (int) polega na kopiowaniu elementów ze starej tablicy do nowej zaktualizowanej tablicy, stąd jej środowisko wykonawcze to O (n).

3. Iterator wsteczny

LinkedList można iterować w odwrotnym kierunku za pomocą descendingIterator () while

w ArrayList nie ma descendingIterator () , więc musimy napisać własny kod, aby iterować po ArrayList w odwrotnym kierunku.

4. Początkowa pojemność

Jeśli konstruktor nie jest przeciążony, ArrayList tworzy pustą listę początkowej pojemności 10, natomiast

LinkedList konstruuje tylko pustą listę bez początkowej pojemności.

5. Narzut pamięci

Narzut pamięci w LinkedList jest większy w porównaniu do ArrayList, ponieważ węzeł w LinkedList musi utrzymywać adresy następnego i poprzedniego węzła. Podczas

W ArrayList każdy indeks zawiera tylko rzeczywisty obiekt (dane).

Źródło

Zwykle używam jednego nad drugim w oparciu o złożoność czasową operacji, które wykonałbym na tej konkretnej liście.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Oprócz innych dobrych argumentów powyżej, powinieneś zauważyć interfejs ArrayListimplementujący RandomAccess, podczas gdy LinkedListimplementuje Queue.

W jakiś sposób rozwiązują one nieco inne problemy, z różną wydajnością i zachowaniem (zobacz ich listę metod).

To zależy od tego, jakie operacje będziesz wykonywać więcej na liście.

ArrayListjest szybszy dostęp do wartości indeksowanej. Jest znacznie gorzej podczas wstawiania lub usuwania obiektów.

Aby dowiedzieć się więcej, przeczytaj każdy artykuł, który mówi o różnicy między tablicami i połączonymi listami.

Lista tablic jest zasadniczo tablicą z metodami dodawania elementów itp. (Zamiast tego należy użyć listy ogólnej). Jest to zbiór elementów, do których można uzyskać dostęp za pośrednictwem indeksu (na przykład [0]). Oznacza przejście z jednego elementu do drugiego.

Połączona lista określa przejście od jednego elementu do następnego (Pozycja a -> pozycja b). Możesz uzyskać ten sam efekt z listą tablic, ale lista połączona absolutnie mówi, który element powinien następować po poprzedniej.

Zobacz samouczki Java - implementacje list .

Ważną cechą połączonej listy (której nie przeczytałem w innej odpowiedzi) jest połączenie dwóch list. W przypadku tablicy jest to O (n) (+ narzut niektórych ponownych alokacji), a połączona lista to tylko O ​​(1) lub O (2) ;-)

Ważne : w przypadku Javy LinkedListnie jest to prawdą! Zobacz Czy istnieje szybka metoda konkat dla listy połączonej w Javie?

ArrayList i LinkedList mają swoje zalety i wady.

ArrayList używa ciągłego adresu pamięci w porównaniu do LinkedList, który używa wskaźników do następnego węzła. Kiedy więc chcesz wyszukać element w ArrayList, jest to szybsze niż wykonywanie iteracji za pomocą LinkedList.

Z drugiej strony, wstawianie i usuwanie z LinkedList jest znacznie łatwiejsze, ponieważ wystarczy zmienić wskaźniki, podczas gdy ArrayList implikuje użycie operacji shift do dowolnego wstawiania lub usuwania.

Jeśli masz częste operacje pobierania w swojej aplikacji, użyj ArrayList. Jeśli masz częste wstawianie i usuwanie, skorzystaj z LinkedList.

Przeczytałem odpowiedzi, ale jest jeden scenariusz, w którym zawsze używam LinkedList zamiast ArrayList, którym chcę się podzielić, aby usłyszeć opinie:

Za każdym razem, gdy miałem metodę, która zwraca listę danych uzyskanych z DB, zawsze używam LinkedList.

Moim uzasadnieniem było to, że ponieważ nie można dokładnie wiedzieć, ile wyników otrzymuję, nie zostanie zmarnowana pamięć (jak w ArrayList z różnicą między pojemnością a rzeczywistą liczbą elementów) i nie będzie marnowania czasu na próby zduplikuj pojemność.

Jeśli chodzi o ArrayList, zgadzam się, że przynajmniej powinieneś zawsze używać konstruktora z początkową pojemnością, aby zminimalizować powielanie tablic w jak największym stopniu.

ArrayLista LinkedListoba narzędzia, List interface ich metody i wyniki są prawie identyczne. Jednak istnieje kilka różnic między nimi, które sprawiają, że jedna jest lepsza od drugiej w zależności od wymagań.

ArrayList Vs LinkedList

1) Search: ArrayListoperacja wyszukiwania jest dość szybka w porównaniu do LinkedListoperacji wyszukiwania. get(int index)in ArrayListdaje wydajność, O(1)podczas gdy LinkedListwydajność jest O(n).

Reason: ArrayListutrzymuje system oparty na indeksach dla swoich elementów, ponieważ niejawnie wykorzystuje strukturę danych tablicowych, co przyspiesza wyszukiwanie elementu na liście. Z drugiej strony LinkedListimplementuje podwójnie połączoną listę, która wymaga przejścia przez wszystkie elementy w celu wyszukania elementu.

2) Deletion: LinkedListoperacja usuwania daje O(1)wydajność, a wydajność ArrayListzmienną: O(n)w najgorszym przypadku (podczas usuwania pierwszego elementu), O(1)aw najlepszym przypadku (podczas usuwania ostatniego elementu).

Wniosek: usuwanie elementu LinkedList jest szybsze w porównaniu do ArrayList.

Powód: każdy element LinkedList utrzymuje dwa wskaźniki (adresy), które wskazują oba sąsiednie elementy na liście. Dlatego usunięcie wymaga jedynie zmiany położenia wskaźnika w dwóch sąsiednich węzłach (elementach) węzła, który ma zostać usunięty. Podczas gdy w ArrayList wszystkie elementy muszą zostać przesunięte, aby wypełnić przestrzeń utworzoną przez usunięty element.

3) Inserts Performance: LinkedListmetoda add daje O(1)wydajność, aw najgorszym przypadku ArrayListdaje O(n). Powód jest taki sam, jak wyjaśniony dla usunięcia.

4) Memory Overhead: ArrayListutrzymuje indeksy i dane elementu, LinkedListzachowując dane elementu i dwa wskaźniki dla sąsiednich węzłów

stąd zużycie pamięci jest wysokie w LinkedList w porównaniu.

Istnieje kilka podobieństw między tymi klasami, które są następujące:

• Zarówno ArrayList, jak i LinkedList są implementacją interfejsu List.
• Oba zachowują kolejność wstawiania elementów, co oznacza, że ​​podczas wyświetlania elementów ArrayList i LinkedList zestaw wyników będzie miał taką samą kolejność, w jakiej elementy zostały wstawione do listy.
• Obie te klasy nie są zsynchronizowane i można je jawnie zsynchronizować za pomocą metody Collections.synchronizedList.
• Te iteratori listIteratorzwrócone przez te klasy są fail-fast(jeśli lista jest modyfikowana strukturalnie w dowolnym momencie po utworzeniu iteratora, w jakikolwiek sposób poza iterator’swłasnymi metodami usuwania lub dodawania, iterator zrobi throwto ConcurrentModificationException).

Kiedy używać LinkedList, a kiedy ArrayList?

• Jak wyjaśniono powyżej, operacje wstawiania i usuwania dają dobrą wydajność (O(1))w LinkedListporównaniu do ArrayList(O(n)).

  Dlatego jeśli istnieje potrzeba częstego dodawania i usuwania w aplikacji, wówczas LinkedList jest najlepszym wyborem.

• get methodOperacje wyszukiwania ( ) są szybkie w, Arraylist (O(1))ale nie wLinkedList (O(n))

  więc jeśli jest mniej operacji dodawania i usuwania oraz więcej operacji wyszukiwania, ArrayList byłby najlepszym wyborem.

Operacja get (i) w ArrayList jest szybsza niż LinkedList, ponieważ:
ArrayList: Implementacja tablic o zmiennym rozmiarze dla interfejsu List
LinkedList: Podwójnie połączona implementacja list interfejsów List i Deque

Operacje, które indeksują do listy, będą przechodzić przez listę od początku lub na końcu, w zależności od tego, który jest bliżej określonego indeksu.

1) Podstawowa struktura danych

Pierwsza różnica między ArrayList i LinkedList polega na tym, że ArrayList jest wspierany przez Array, podczas gdy LinkedList jest wspierany przez LinkedList. Doprowadzi to do dalszych różnic w wydajności.

2) LinkedList implementuje Deque

Inną różnicą między ArrayList i LinkedList jest to, że oprócz interfejsu List, LinkedList implementuje również interfejs Deque, który zapewnia operacje „pierwsze przy pierwszym” dla funkcji add () i poll () oraz kilku innych funkcji Deque. 3) Dodawanie elementów w ArrayList Dodawanie elementu w ArrayList jest operacją O (1), jeśli nie powoduje zmiany rozmiaru tablicy, w którym to przypadku staje się O (log (n)). Z drugiej strony, dodanie elementu w LinkedList jest operacją O (1), ponieważ nie wymaga nawigacji.

4) Usuwanie elementu z pozycji

Aby usunąć element z określonego indeksu, np. Wywołując remove (index), ArrayList wykonuje operację kopiowania, która zbliża go do O (n), podczas gdy LinkedList musi przejść do tego punktu, co również powoduje, że O (n / 2) , ponieważ może przechodzić z obu kierunków w oparciu o bliskość.

5) Iterowanie po ArrayList lub LinkedList

Iteracja jest operacją O (n) zarówno dla LinkedList, jak i ArrayList, gdzie n jest liczbą elementów.

6) Pobieranie elementu z pozycji

Operacja get (indeks) to O (1) w ArrayList, a O (n / 2) w LinkedList, ponieważ musi przechodzić do tego wpisu. Jednak w zapisie Big O O (n / 2) jest po prostu O (n), ponieważ tam ignorujemy stałe.

7) Pamięć

LinkedList używa obiektu opakowującego, Entry, który jest statycznie zagnieżdżoną klasą do przechowywania danych i dwóch węzłów obok siebie i wcześniej, podczas gdy ArrayList po prostu przechowuje dane w Array.

Zatem zapotrzebowanie na pamięć wydaje się mniejsze w przypadku ArrayList niż LinkedList, z wyjątkiem przypadku, gdy Array wykonuje operację zmiany rozmiaru, gdy kopiuje zawartość z jednej tablicy do drugiej.

Jeśli tablica jest wystarczająco duża, może w tym momencie zająć dużo pamięci i uruchomić zbieranie śmieci, co może spowolnić czas odpowiedzi.

Biorąc pod uwagę wszystkie powyższe różnice między ArrayList a LinkedList, wygląda na to, że ArrayList jest lepszym wyborem niż LinkedList w prawie wszystkich przypadkach, z wyjątkiem przypadków wykonywania częstej operacji add () niż remove () lub get ().

Łatwiej jest zmodyfikować listę połączoną niż ArrayList, szczególnie jeśli dodajesz lub usuwasz elementy od początku lub końca, ponieważ lista połączona wewnętrznie przechowuje odniesienia do tych pozycji i są one dostępne w czasie O (1).

Innymi słowy, nie musisz przechodzić przez połączoną listę, aby osiągnąć pozycję, w której chcesz dodać elementy, w takim przypadku dodawanie staje się operacją O (n). Na przykład wstawianie lub usuwanie elementu na środku połączonej listy.

Moim zdaniem używaj ArrayList zamiast LinkedList do większości praktycznych celów w Javie.

Jeden z testów, które tu widziałem, przeprowadza test tylko raz. Zauważyłem jednak, że musisz uruchamiać te testy wiele razy, a ich czasy w końcu się zbiegną. Zasadniczo JVM musi się rozgrzać. W moim szczególnym przypadku użycia musiałem dodać / usunąć elementy z listy, która rośnie do około 500 elementów. W moich testach LinkedListwyszło szybciej, przy LinkedListokoło 50 000 NS i ArrayListokoło 90 000 NS ... dawaj lub bierz. Zobacz poniższy kod.

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;
}

Zarówno remove (), jak i insert () mają wydajność środowiska wykonawczego O (n) zarówno dla ArrayLists, jak i LinkedLists. Przyczyna liniowego czasu przetwarzania wynika jednak z dwóch bardzo różnych przyczyn:

W ArrayList dostajesz się do elementu w O (1), ale w rzeczywistości usunięcie lub wstawienie czegoś powoduje, że O (n), ponieważ wszystkie poniższe elementy muszą zostać zmienione.

Na LinkedList potrzeba O (n), aby dostać się do pożądanego elementu, ponieważ musimy zacząć od samego początku, aż osiągniemy pożądany indeks. W rzeczywistości usuwanie lub wstawianie jest stałe, ponieważ musimy zmienić tylko 1 referencję dla remove () i 2 referencje dla insert ().

To, który z nich jest szybszy do wstawiania i usuwania, zależy od tego, gdzie to się dzieje. Jeśli jesteśmy bliżej początku, LinkedList będzie szybszy, ponieważ musimy przejść przez stosunkowo niewiele elementów. Jeśli jesteśmy bliżej końca, ArrayList będzie szybszy, ponieważ docieramy tam w stałym czasie i musimy tylko zmienić kilka pozostałych elementów, które za nim podążają. Po wykonaniu dokładnie pośrodku LinkedList będzie szybszy, ponieważ przejście przez n elementów jest szybsze niż przeniesienie n wartości.

Bonus: Chociaż nie ma możliwości zrobienia tych dwóch metod O (1) dla ArrayList, w rzeczywistości istnieje sposób, aby to zrobić w LinkedLists. Powiedzmy, że chcemy przejść przez całą Listę, usuwając i wstawiając elementy po drodze. Zwykle zaczynasz od samego początku dla każdego elementu za pomocą LinkedList, możemy również „zapisać” bieżący element, nad którym pracujemy z Iteratorem. Za pomocą Iteratora uzyskujemy wydajność O (1) dla remove () i insert () podczas pracy na LinkedList. Czyniąc to jedyną korzyścią dla wydajności, o której wiem, gdzie LinkedList jest zawsze lepsza niż ArrayList.

ArrayList rozszerza AbstractList i implementuje interfejs listy. ArrayList to tablica dynamiczna.
Można powiedzieć, że został stworzony w celu przezwyciężenia wad tablic

. Klasa LinkedList rozszerza AbstractSequentialList i implementuje interfejs List, Deque i Queue.
Wydajność
arraylist.get()wynosi O (1), natomiast linkedlist.get()O (n)
arraylist.add()oznacza O (1), a linkedlist.add()0 (1)
arraylist.contains()oznacza O (n) i linkedlist.contains()oznacza O (n)
arraylist.next()oznacza O (1), a linkedlist.next()oznacza O (1)
arraylist.remove()oznacza O (n) podczas gdy linkedlist.remove()jest O (1)
W arraylist
iterator.remove()jest O (n),
podczas gdy w Linkedlist
iterator.remove()jest O (1)