Kiedy używać LinkedList zamiast ArrayList w Javie?

3122

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?

sdellysse
źródło
4
Zobacz także: Tablica kontra połączona lista
Hawkeye Parker
1
Wystarczy przeczytać cytat autora LinkedList stackoverflow.com/a/42529652/2032701, a uzyskasz praktyczne zrozumienie problemu.
Ruslan

Odpowiedzi:

3371

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ą.

Jonathan Tran
źródło
182
Zapomniałem wspomnieć o kosztach wprowadzenia. W przypadku LinkedList, gdy masz prawidłową pozycję, wstawianie kosztuje O (1), podczas gdy w ArrayList idzie w górę do O (n) - wszystkie elementy poza punktem wstawiania muszą zostać przesunięte.
David Rodríguez - dribeas
26
Jeśli chodzi o użycie Vector: naprawdę nie ma potrzeby wracać do Vector. Można to zrobić za pomocą preferowanej implementacji listy i wywołania funkcji synchronizedList w celu uzyskania zsynchronizowanego opakowania. Zobacz: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox
69
Nie, dla LinkedList, get jest nadal O (n), nawet jeśli znasz pozycję, ponieważ aby dostać się do tej pozycji, podstawowa implementacja musi przejść przez „następne” wskaźniki połączonej listy, aby dostać się do wartości tej pozycji. Nie ma czegoś takiego jak dostęp losowy. Dla pozycji 2 chodzenie po wskazówkach może być tanie, ale dla pozycji 1 miliona wcale nie tak tanie. Chodzi o to, że jest proporcjonalny do pozycji, co oznacza, że ​​jest to O (n).
Jonathan Tran
53
@Kevin Może mieć znaczenie to, że pamięć jest „blisko siebie”. Sprzęt będzie buforował ciągłe bloki pamięci (dynamiczna pamięć RAM) do szybszej statycznej pamięci RAM w pamięci podręcznej L1 lub L2. Teoretycznie i przez większość czasu praktycznie pamięć można traktować jako dostęp losowy. Ale w rzeczywistości sekwencyjne czytanie pamięci będzie nieco szybsze niż w przypadkowej kolejności. W przypadku pętli krytycznej dla wydajności może to mieć znaczenie. Nazywają to „lokalizacją przestrzenną” lub lokalizacją odniesienia .
Jonathan Tran
92
Nie ma czegoś takiego jak O(n/2)lub O(n/4). Duża notacja O mówi, jak skaluje się operacja z większym n . a operacja wymagająca n/2kroków jest skalowana dokładnie tak, jak operacja wymagająca nkroków, co jest powodem, dla którego usuwane są stałe sumy lub czynniki. O(n/2)i O(n/4)oba są sprawiedliwe O(n). LinkedListi tak ArrayListczy inaczej mają różne stałe czynniki, więc nie byłoby sensu porównywać O(n/2)jednego z O(n/4)drugim, oba oznaczają po prostu operacje skalowania liniowego.
Holger
630

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.


Wykres LinkedList i ArrayList Liczba elementów x bajtów


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)

Numeron
źródło
2
Całkiem interesujące jest to, że LinkedList wymaga tyle samo pamięci co ArrayList do przechowywania pojedynczego elementu. Jak mało intuicyjne! Co się stanie, jeśli uruchomisz przykład z opcją -XX: + UseCompressedOops?
jontejj
215
Problem z matematyką polega na tym, że wykres bardzo wyolbrzymia wpływ. Modelujesz obiekty, z których każdy zawiera tylko int4 lub 8 bajtów danych. Na połączonej liście znajdują się zasadniczo 4 „słowa” narzutu. Twój wykres sprawia więc wrażenie, że połączone listy używają „pięciokrotnie” miejsca do przechowywania list tablic. To jest źle. Narzut wynosi 16 lub 32 bajty na obiekt, co stanowi korektę addytywną, a nie współczynnik skalowania.
Heath Hunnicutt
6
Żaden z obiektów ArrayList / LinkedList / Node nie zawiera tylko int, więc nie rozumiem, co tam mówisz. Zmieniłem nazwę „narzutu obiektu” na „nagłówek obiektu” na clarfy - 8-bajtowy nagłówek dla każdego obiektu niezależnie od systemu, i tak, obejmuje wszystkie obiekty Node w LinkedList, które są liczone poprawnie, o ile mogę powiedzieć. Nawiasem mówiąc, patrząc na to ponownie, znalazłem kilka innych problemów z moją matematyką na LinkedList, co w rzeczywistości pogarsza podział i ArrayList . Z przyjemnością kontynuuję aktualizację, więc nie wahaj się wyjaśnić i dopracować.
Numeron
6
Należy zauważyć, że CompressedOopsjest teraz domyślny we wszystkich najnowszych pakietach JDK (7, 8 i aktualizacjach 6 przez kilka lat), więc 64-bit nie będzie różnił się ArrayListani LinkedListrozmiarami, chyba że jawnie wyłączyłeś skompresowane ups dla jakiś powód.
BeeOnRope
1
@ jontejj domyślny wzrost pojemności wynosi 50%, więc po wypełnieniu go ArrayListbez określenia początkowej pojemności nadal będzie zużywał znacznie mniej pamięci niż a LinkedList.
Holger,
243

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.
Tom Hawtin - tackline
źródło
236
Przepraszam. oznaczył cię w dół. LinkedList nie jest do kitu. Istnieją sytuacje, w których LinkedList jest właściwą klasą do użycia. Zgadzam się, że nie ma wielu sytuacji, w których jest to lepsze niż arraylist, ale one istnieją. Edukuj ludzi, którzy robią głupie rzeczy!
David Turner
40
Przykro nam, że masz za to wiele głosów negatywnych. Rzeczywiście jest bardzo mały powód, aby korzystać z LinkedList Java. Oprócz złej wydajności wykorzystuje również dużo więcej pamięci niż inne konkretne klasy List (każdy węzeł ma dwa dodatkowe wskaźniki, a każdy węzeł jest oddzielnym obiektem otoki z towarzyszącymi im dodatkowymi bajtami napowietrznymi).
Kevin Brock
42
To jedna z najbardziej przydatnych odpowiedzi tutaj. Szkoda, że ​​wielu programistów nie rozumie (a) różnicy między abstrakcyjnymi typami danych a konkretnymi implementacjami oraz (b) rzeczywistego znaczenia stałych czynników i obciążenia pamięci w określaniu wydajności.
Porculus,
50
-1: To raczej mrugający widok. Tak, to prawda, że ​​ArrayList jest bardzo wszechstronnym narzędziem. Ma jednak swoje ograniczenia. Są przypadki, w których spowoduje to problemy i będziesz musiał użyć LinkedList. Oczywiście jest to bardzo wyspecjalizowane rozwiązanie i, jak każde wyspecjalizowane narzędzie, w większości przypadków ma lepsze wyniki niż narzędzie wszechstronne. Ale to nie znaczy, że „jest do bani” lub coś w tym rodzaju, wystarczy wiedzieć, kiedy go użyć.
Malcolm,
27
@DavidTurner: Istnieją, ale myślę, że Tom miał na myśli to, że jeśli musisz zapytać, prawdopodobnie chcesz ArrayList.
user541686,
139

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.

Lamont
źródło
8
Czy innym rozwiązaniem nie byłoby programowe zarządzanie rozmiarem listy za pomocą metody zapewniającej ArCapacity () ArrayList? Moje pytanie brzmi: dlaczego tak wiele rzeczy jest przechowywanych w wiązce kruchych struktur danych, skoro można je lepiej przechowywać w mechanizmie buforowania lub db? Pewnego dnia miałem wywiad, w którym przeklinali na temat zła ArrayList, ale przychodzę tutaj i stwierdzam, że analiza złożoności jest ogólnie lepsza! WIELKI PUNKT DO DYSKUSJI, TYM. DZIĘKI!
ingyhere
22
po otrzymaniu aplikacji Java ze stertami 10 GB możesz skończyć blokowanie aplikacji na 25 sekund podczas pełnego GC, co powoduje przekroczenie limitu czasu. W rzeczywistości z LinkedList zamordujesz śmietnik podczas pełnych GC, musi on iterować zbyt dużą LinkedList z brakującą pamięcią podręczną każdy węzeł.
bestsss,
5
To ... okropne rozwiązanie. jesteś w zasadzie zależny od sprzątania GC, co jest niezwykle drogie, gdy zamiast tego możesz po prostu wywołać sureCapacity () na arraylist ...
Philip Devine
5
@Andreas: A LinkedList zawsze przydziela pięciokrotnie pamięć niż zwykła tablica referencji, więc ArrayListczasowe wymaganie 2,5 razy nadal zużywa znacznie mniej pamięci, nawet jeśli pamięć nie jest odzyskana. Ponieważ przydział dużych tablic omija przestrzeń Eden, nie mają one żadnego wpływu na zachowanie GC, chyba że naprawdę nie ma wystarczającej ilości pamięci, w którym to przypadku LinkedListwybuchło znacznie wcześniej…
Holger
5
@Andreas Innym problemem jest sposób przydzielania pamięci. LinkedListpotrzebuje tylko niewielkiej ilości wolnej pamięci, aby przydzielić na następny element. ArrayListbędzie potrzebował dużego i ciągłego wolnego bloku miejsca, aby przydzielić zmienioną tablicę. Jeśli sterty ulegną fragmentacji, GC może skończyć z kolejnością całej sterty, aby zwolnić odpowiedni pojedynczy blok pamięci.
Piotr Kusmierczyk
128
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.

Michael Munsey
źródło
42
Nie można bezpośrednio porównywać dużych wartości O bez myślenia o stałych czynnikach. W przypadku małych list (a większość list jest małych), O (N) tablicy ArrayList jest szybsze niż O (1) LinkedList.
Porculus,
4
Nie dbam o wydajność małych list, podobnie jak mój komputer, chyba że w jakiś sposób jest używany w pętli.
Maarten Bodewes,
45
LinkedList nie może tak naprawdę wstawiać w środkowej części O(1). Musi przebiegać przez połowę listy, aby znaleźć punkt wstawiania.
Thomas Ahle,
8
LinkedList: wstaw w środku O (1) - jest NIEPRAWIDŁOWY! Dowiedziałem się, że nawet wstawienie do 1/10 pozycji rozmiaru LinkedList jest wolniejsze niż wstawienie elementu do 1/10 pozycji ArrayList. Co gorsza: koniec kolekcji. wstawianie do ostatnich pozycji (nie ostatniej) ArrayList jest szybsze niż do ostatnich pozycji (nie ostatniej) LinkedList
kachanov
14
@kachanov Wstawianie w a LinkedList jest, O(1) jeśli masz iterator do pozycji wstawiania , tzn. ListIterator.addjest podobno O(1)dla LinkedList.
Ma ZAKOŃCZENIE - Anony-Mousse,
107

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)

Daniel Martin
źródło
39
Z Java 6 możesz korzystać ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle
1
ArrayDequejest wolniejszy niż, LinkedListchyba że wszystkie operacje są na tym samym końcu. Jest OK, gdy jest używany jako stos, ale nie tworzy dobrej kolejki.
Jeremy List
2
Nieprawdziwe - przynajmniej dla implementacji Oracle w jdk1.7.0_60 i w poniższym teście. Stworzyłem test, w którym zapętlam 10 milionów razy i mam Deque 10 milionów losowych liczb całkowitych. Wewnątrz pętli odpytuję jeden element i oferuję stały element. Na moim komputerze LinkedList jest ponad 10 razy wolniejszy niż ArrayDeque i zużywa mniej pamięci). Powodem jest to, że w przeciwieństwie do ArrayList, ArrayDeque utrzymuje wskaźnik do nagłówka tablicy, aby nie musiał przesuwać wszystkich elementów po usunięciu nagłówka.
Henno Vermeulen
6
ArrayDequeprawdopodobnie będzie szybszy niż w Stackprzypadku użycia go jako stosu i szybciej niż w LinkedListprzypadku użycia go jako kolejki.
akhil_mittal
3
Zauważ, że komentarz akhil_mittal jest cytatem z ArrayDequedokumentacji.
Stuart Marks
65

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 .

zdeterminowany
źródło
54

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);
    }
}
Popiół
źródło
1
ArrayList nie musi być podwojony, by być precyzyjnym. Najpierw sprawdź źródła.
Żeglarz naddunajski
Należy zauważyć, że twój przykład jest wadliwy ... Usuwasz z ciągu od: 18 + [2, 12] bajtów („true0false”, „true500000false”), średnio 25 bajtów, które są wielkościami elementów pośrodku. Wiadomo, że wraz ze wzrostem wielkości bajtu elementu połączona lista działa lepiej, wraz ze wzrostem wielkości listy, ciągła tablica (lista) będzie działać lepiej. Co najważniejsze, wykonujesz .equals () na ciągach - co nie jest tanią operacją. Jeśli zamiast tego użyjesz liczb całkowitych, myślę, że byłaby różnica.
Centril,
2
„... jest gorszy w przypadku aplikacji o dużej objętości ”: To nieporozumienie. LinkedListma o wiele więcej pamięci, ponieważ dla każdego elementu istnieje obiekt węzła z pięcioma polami. W wielu systemach powoduje to obciążenie 20 bajtów. Średni narzut pamięci przypadający na element ArrayListwynosi półtora słowa, co daje 6 bajtów i 8 bajtów w najgorszym przypadku.
Lii
1
Zrobiłem tutaj lepszą wersję twojego testu porównawczego , z wynikami - wydajność dołączania do arraylisty jest sztucznie niska dla ciebie, ponieważ addAll daje tablicę pamięci o DOKŁADNIE początkowym rozmiarze, więc pierwsza wstawka zawsze wyzwala arraycopy. Obejmuje to także cykle rozgrzewania, aby umożliwić kompilację JIT przed zebraniem danych.
BobMcGee
4
@BillK od Java 8, możesz użyć, removeIf(element -> condition)gdzie pasuje, co może być znacznie szybsze ArrayList, w porównaniu do zapętlania i usuwania za pomocą iteratora, ponieważ nie jest wymagane przesunięcie całej reszty dla każdego elementu. To, czy działa to lepiej, czy gorzej niż LinkedListzależy od konkretnego scenariusza, ponieważ a LinkedListjest teoretycznie O (1), ale usunięcie tylko jednego węzła wymaga kilku dostępów do pamięci, które mogą łatwo przekroczyć liczbę potrzebną do ArrayListusunięcia znacznej liczby elementów .
Holger
50

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.):

wprowadź opis zdjęcia tutaj

Ryan
źródło
3
„LinkedList jest szybszy niż dodawanie / usuwanie”. Źle, sprawdź odpowiedź powyżej stackoverflow.com/a/7507740/638670
Nerrve,
49

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.

Ruslan
źródło
34

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ą.

Dustin
źródło
15
LinkedList nie jest tani w dodawaniu elementów. Prawie zawsze szybsze jest dodanie miliona elementów do ArrayList niż dodanie ich do LinkedList. Większość list w kodzie rzeczywistym nie ma nawet miliona elementów.
Porculus,
10
W dowolnym momencie znasz koszt dodania elementu do listy LinkedList. ArrayList, której nie masz (ogólnie). Dodanie pojedynczego elementu do ArrayList zawierającej milion elementów może zająć bardzo dużo czasu - jest to operacja O (n) plus podwojenie pamięci, chyba że wstępnie przydzielono miejsce. Dodanie elementu do LinkedList to O (1). Moje ostatnie oświadczenie jest ważne.
Dustin
4
Dodanie pojedynczego elementu do ArrayList to O (1) bez względu na to, czy jest to 1 milion czy 1 miliard. Dodanie elementu do LinkedList to także O (1). „Dodawanie” oznacza DODAWANIE DO KOŃCA.
kachanov
Musisz przeczytać implementację inaczej niż ja. Z mojego doświadczenia wynika, że ​​kopiowanie tablicy o wartości 1 miliarda elementów zajmuje dłużej niż kopiowanie tablicy o wartości 1 miliona elementów.
Dustin
6
@kachanov musisz źle zrozumieć Dustina. O ile nie zadeklarowałeś tablicy 1 miliarda przedmiotów, ostatecznie będziesz musiał zmienić rozmiar tablicy, w takim przypadku będziesz musiał skopiować wszystkie elementy do nowej, większej tablicy, dlatego czasami otrzymasz O (N), jednak z połączoną listą zawsze będziesz dostać O (1)
Stan R.
28

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):

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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:

wprowadź opis zdjęcia tutaj

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

Lior Bar-On
źródło
Nie nazwałbym kolejki wyjątkową ani ekstremalną! Kolejka fifo jest znacznie łatwiejsza do zaimplementowania na LinkedList zamiast ArrayList. To właściwie koszmar na tablicy ArrayList, ponieważ musisz śledzić swój początek, zatrzymać i dokonać własnej alokacji, równie dobrze możesz użyć tablicy, ale lista połączona JEST fifo. Nie jestem pewien co do implementacji Java, ale LinkedList może wykonać O (1) zarówno dla operacji kolejkowania, jak i usuwania z kolejki (wymaga specjalnego wskaźnika do elementu tail w celu usunięcia, które, jak zakładam, ma Java, ale nie sprawdziłem jeszcze dwukrotnie .)
Bill K
24

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.

Jesse Wilson
źródło
3
W przypadku małych list ArrayList.add (0) nadal będzie zawsze szybszy niż LinkedList.addFirst ().
Porculus,
1
@Porculus Ciągle słyszę ten argument, że w przypadku małych list ArrayList.add (0) będzie szybszy, ten mały jest o ile mały? 10 elementów, 10 milionów,?
garg10may
1
@ garg10 może być mniejszy niż 10.
Jesse Wilson
@Porculus small oznacza mniej niż maksymalna pojemność wewnętrznej tablicy leżącej u podstaw ArrayList.
Janac Meena
21

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.

Ajax
źródło
18

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ć. :)

Rajith Delantha
źródło
9
>>>> ArrayList add -> O (1) <- not tru. W niektórych przypadkach ArrayList będzie musiał urosnąć, aby dodać jeszcze jeden element
kachanov
1
LinkedList remove to nie O (1), musiałby szukać elementu do usunięcia, dlatego najgorszy przypadek O (n) i średniego O (n / 2)
garg10may
Nie jest tak LinkedList.add(), chociaż większość odpowiedzi tutaj tak mówi.
user207421,
18

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

Abhijeet Ashok Muneshwar
źródło
18

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    |
|--------------------------------------|
Gayan Weerakutti
źródło
ArrayDeque równoważy rzeczy bardziej w kierunku tablic, ponieważ wstawianie / usuwanie przodu / tyłu są wszystkie O (1) jedyną rzeczą, do której dołączona lista wciąż wygrywa, to dodawanie / usuwanie podczas przechodzenia (operacje iteratora).
Bill K
14

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).

PhiLho
źródło
10

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.

Matthew Schinckel
źródło
2
Aby dowiedzieć się więcej, nie czytaj, po prostu napisz kod. a przekonasz się, że implementacja ArrayList jest szybsza niż LinkedList we wstawianiu i usuwaniu.
kachanov
8

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.

kemiller2002
źródło
8

Zobacz samouczki Java - implementacje list .

chharvey
źródło
2
Cześć @chharvey, Link tylko odpowiedzi otrzymują 6 głosów poparcia? Dodaj kilka punktów, które mogłyby obsługiwać link. Co jeśli wyrocznia zmieni swój link?
7

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?

Karussell
źródło
2
W jaki sposób? Może tak być w przypadku struktur danych z połączonymi listami, ale nie obiektu Java LinkList. Nie można po prostu wskazać nextz jednej listy pierwszego węzła na drugiej liście. Jedynym sposobem jest użycie addAll()sekwencyjnego dodawania elementów, chociaż jest to lepsze niż zapętlenie i wywołanie add()każdego elementu. Aby to zrobić szybko w O (1), potrzebujesz klasy kompozycyjnej (takiej jak org.apache.commons.collections.collection.CompositeCollection), ale wtedy działałoby to dla dowolnego rodzaju List / Collection.
Kevin Brock
tak, prawda. Odpowiednio zredagowałem odpowiedź. ale zobacz tę odpowiedź na „jak” zrobić to z LinkedList: stackoverflow.com/questions/2494031/…
Karussell
7

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.

Nesan Mano
źródło
6

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.

gaijinco
źródło
5

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.

Real73
źródło
5

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.

Amitabha
źródło
5

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.

Anjali Suman
źródło
1
Myślę, że jest to najlepiej podana odpowiedź całej grupy tutaj. Jest dokładny i pouczający. Sugerowałbym zmianę ostatniej linii - na końcu dodaj „oprócz kolejek”, które są bardzo ważnymi strukturami, które tak naprawdę nie mają sensu dla listy połączonej.
Bill K
3

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;
}
Jose Martinez
źródło
2

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.

pietz
źródło
1

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)

Randhawa
źródło