Pytanie Kiedy używać LinkedList over ArrayList?


Zawsze używałem po prostu:

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

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

Kiedy powinien LinkedList być używane powyżej ArrayList i wzajemnie?


2568
2017-11-27 01:36


pochodzenie


Zobacz też: Array versus linked-list - Hawkeye Parker
Zobacz cytat z autora LinkedList stackoverflow.com/a/42529652/2032701 i dostaniesz praktyczny sens tego problemu. - Ruslan


Odpowiedzi:


Podsumowanie  ArrayList z ArrayDeque są preferowane w dużo więcej przypadków użycia niż LinkedList. Nie jestem pewien - po prostu zacznij od ArrayList.


LinkedList i ArrayList są dwiema różnymi implementacjami interfejsu List. LinkedList implementuje go z podwójnie połączoną listą. ArrayList implementuje go z dynamicznie zmieniającą się tablicą.

Podobnie jak w przypadku standardowych połączonych operacji list i tablic, różne metody będą miały różne algorytmiczne środowiska wykonawcze.

Dla LinkedList<E>

  • get(int index) jest Na) (z n / 4 kroki średnio)
  • add(E element) jest O (1)
  • add(int index, E element) jest Na) (z n / 4 kroki średnio), ale O (1) gdy index = 0  <--- główna korzyść z LinkedList<E>
  • remove(int index) jest Na) (z n / 4 kroki średnio)
  • Iterator.remove() jest O (1). <--- główna korzyść z LinkedList<E>
  • ListIterator.add(E element) jest O (1)  Jest to jedna z głównych korzyści LinkedList<E>

Uwaga: Wiele operacji wymaga n / 4 kroki średnio, stały liczba kroków w najlepszym przypadku (np. index = 0) oraz n / 2 kroki w najgorszym przypadku (środkowa lista)

Dla ArrayList<E>

  • get(int index) jest O (1)  <--- główna korzyść z ArrayList<E>
  • add(E element) jest O (1) amortyzowany, ale Na) najgorszy przypadek, ponieważ tablica musi być zmieniana i kopiowana
  • add(int index, E element) jest Na) (z n / 2 kroki średnio)
  • remove(int index) jest Na) (z n / 2 kroki średnio)
  • Iterator.remove() jest Na) (z n / 2 kroki średnio)
  • ListIterator.add(E element) jest Na) (z n / 2 kroki średnio)

Uwaga: Wiele operacji wymaga n / 2 kroki średnio, stały liczba kroków w najlepszym przypadku (koniec listy), n kroki w najgorszym przypadku (początek listy)

LinkedList<E> umożliwia stałe wstawianie lub usuwanie za pomocą iteratorów, ale tylko sekwencyjny dostęp elementów. Innymi słowy, możesz przejść do przodu lub do tyłu, ale znalezienie pozycji na liście wymaga czasu proporcjonalnego do wielkości listy. Javadoc mówi "operacje indeksu na liście będą przechodzić przez tę listę od początku do końca, w zależności od tego, która z nich jest bliższa", więc te metody są Na) (n / 4 kroki) O (1) dla index = 0.

ArrayList<E>, z drugiej strony, pozwalają na szybki losowy dostęp do odczytu, dzięki czemu można chwycić dowolny element w stałym czasie. Ale dodanie lub usunięcie z dowolnego miejsca, ale koniec wymaga przesunięcia wszystkich ostatnich elementów, aby otworzyć lub wypełnić lukę. Ponadto, jeśli dodasz więcej elementów niż pojemność podstawowej tablicy, przydzielana jest nowa tablica (1,5-krotność rozmiaru), a stara tablica jest kopiowana do nowej, więc dodanie do ArrayList jest Na) w najgorszym przypadku, ale na stałym poziomie.

Dlatego w zależności od operacji, które zamierzasz wykonać, należy odpowiednio wybrać implementacje. Iteracja na obu rodzajach list jest praktycznie równie tania. (Iterowanie nad ArrayList jest technicznie szybszy, ale jeśli nie robisz czegoś naprawdę wrażliwego na wydajność, nie powinieneś się o to martwić - obie są stałymi).

Główne zalety korzystania z LinkedList powstają podczas ponownego użycia istniejących iteratorów do wstawiania i usuwania elementów. Te operacje można następnie wykonać w O (1) poprzez zmianę listy tylko lokalnie. Na liście tablic musi pozostać reszta tablicy przeniósł (tj. skopiowany). Po drugiej stronie, szukając w LinkedList oznacza następujące linki w Na) (n / 2 kroki) w najgorszym przypadku, natomiast w przypadku ArrayList pożądana pozycja może być obliczona matematycznie i dostępna w O (1).

Kolejna korzyść z używania a LinkedList powstają, gdy dodajesz lub usuwasz z nagłówka listy, ponieważ te operacje są O (1), chociaż są Na) dla ArrayList. Zauważ, że ArrayDeque może być dobrą alternatywą dla LinkedList do 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 również jest inne. Każdy element a LinkedList ma więcej narzutów, ponieważ zapisywane są również wskaźniki do następnego i poprzedniego elementu. ArrayLists nie masz tego narzut. Jednak, ArrayLists zajmują tyle pamięci, ile jest przydzielone na pojemność, niezależnie od tego, czy elementy zostały faktycznie dodane.

Domyślna początkowa pojemność pliku ArrayList jest dość mały (10 z Javy 1.4 - 1.8). Ale ponieważ podstawową implementacją jest tablica, należy zmienić rozmiar tablicy, jeśli dodasz wiele elementów. Aby uniknąć wysokich kosztów zmiany rozmiaru, gdy wiesz, że zamierzasz dodać wiele elementów, skonstruuj ArrayList o wyższej początkowej pojemności.


2847
2017-10-06 06:46



Zapomniałem wspomnieć o kosztach wstawienia. W LinkedList, gdy masz poprawną pozycję, koszty wstawienia O (1), podczas gdy w ArrayList idzie ona do O (n) - wszystkie elementy poza punktem wstawienia muszą zostać przeniesione. - David Rodríguez - dribeas
Odnośnie korzystania z Vector: Naprawdę nie ma potrzeby, aby powracać do Vector. Aby to zrobić, użyj preferowanej implementacji List i wywołaj metodę synchronizedList, aby nadać jej zsynchronizowane opakowanie. Widzieć: java.sun.com/docs/books/tutorial/collections/implementations/... - Ryan Cox
Nie, dla listy typu LinkedList, get jest nadal O (n), nawet jeśli znasz pozycję, ponieważ aby uzyskać tę pozycję, podstawowa implementacja musi przejść "następne" wskaźniki listy dołączonej, aby uzyskać wartość tej pozycji. Nie ma czegoś takiego jak dostęp losowy. Dla pozycji 2 chodzenie na wskaźniki może być tanie, ale dla pozycji 1 milion, nie tak tanie. Chodzi o to, że jest proporcjonalna do pozycji, co oznacza, że ​​jest to O (n). - Jonathan Tran
@Kevin Może mieć znaczenie, że pamięć jest "blisko siebie". Sprzęt będzie buforował sąsiednie bloki pamięci (dynamiczna pamięć RAM) w szybszą statyczną pamięć RAM w pamięci podręcznej L1 lub L2. Teoretycznie i praktycznie przez większość czasu pamięć można traktować jako dostęp losowy. Ale w rzeczywistości sekwencyjne czytanie w pamięci będzie nieco szybsze niż w przypadkowej kolejności. W przypadku pętli o znaczeniu krytycznym może to mieć znaczenie. Nazywają to "przestrzenną lokalizacją" lub miejscowość odniesienia. - Jonathan Tran
Nie ma czegoś takiego jak O(n/2) lub O(n/4). Duża notacja O mówi ci, jak operacja waga z większym n. i operacja, która wymaga n/2 kroki ważą dokładnie tak, jak potrzebna operacja n kroki, które powodują usuwanie stałych lub czynników. O(n/2) i O(n/4) są po prostu sprawiedliwe O(n). LinkedList i ArrayList w każdym razie mają różne stałe czynniki, więc nie ma sensu porównywać a O(n/2) z jednego z a O(n/4) drugiej, oba oznaczają tylko liniowe operacje skalowania. - Holger


Jak dotąd, nikt nie wydaje się zajmować ślad pamięci każdej z tych list oprócz ogólnego konsensusu, że LinkedList jest "dużo więcej" niż ArrayList wykonałem kilka operacji, aby zademonstrować, ile dokładnie obie listy pobierają dla N zerowych odniesień.

Ponieważ referencje są 32 lub 64 bitami (nawet gdy są zerowe) w ich systemach względnych, mam włączone 4 zestawy danych dla 32 i 64 bitów LinkedLists i ArrayLists.

Uwaga: Rozmiary przedstawione dla ArrayList wiersze są dla przycięte listy - W praktyce pojemność macierzy dyskowej w ArrayList jest zwykle większy niż jego aktualny licznik elementów.

Uwaga 2:  (dzięki BeeOnRope) Ponieważ wartość CompressedOops jest teraz domyślna od połowy JDK6 i wyżej, wartości poniżej dla maszyn 64-bitowych będą w zasadzie odpowiadać ich 32-bitowym odpowiednikom, chyba że wyraźnie je wyłączysz.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Wynik jasno to pokazuje LinkedList jest o wiele więcej niż ArrayList, szczególnie przy bardzo wysokiej liczbie elementów. Jeśli pamięć jest czynnikiem, unikaj LinkedLists.

Zastosowane przeze mnie formuły, daj mi znać, jeśli zrobiłem coś złego i naprawię to. "b" to 4 lub 8 dla systemów 32- lub 64-bitowych, a "n" to liczba elementów. Zauważ, że powodem modów jest to, że wszystkie obiekty w java zajmują wiele przestrzeni o wielkości 8 bajtów, niezależnie od tego, czy wszystkie są 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)

LinkedList:

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

535
2017-11-27 14:20



Całkiem interesujące, że LinkedList wymaga tyle pamięci, ile ArrayList do przechowywania pojedynczego elementu. Jak nieintuicyjny! Co stanie się, jeśli użyjesz swojego przykładu z opcją -XX: + UseCompressedOops? - jontejj
Problem z matematyką polega na tym, że wykres znacznie wyolbrzymia wpływ. Modelujesz obiekty, z których każdy zawiera tylko jeden int, więc 4 lub 8 bajtów danych. Na połączonej liście znajdują się zasadniczo 4 "słowa" narzutów. Twój wykres daje wrażenie, że połączone listy używają "pięć razy" przechowywania list tablic. To jest źle. Narzut wynosi 16 lub 32 bajty na obiekt, jako korekta dodatku, a nie współczynnik skalowania. - Heath Hunnicutt
Żaden z obiektów ArrayList / LinkedList / Node nie zawiera tylko int, więc nie dostaję tego, co tam mówisz. Przepisałem "obiektowy narzut" na "nagłówek obiektu" na clarfy - istnieje 8 bajtowy nagłówek dla każdego obiektu, niezależnie od systemu, i tak, że zawiera wszystkie obiekty węzła w LinkedList, które są zliczane poprawnie tak daleko, jak tylko mogę powiedzieć. Nawiasem mówiąc, patrząc na to jeszcze raz, znalazłem kilka innych problemów z moją matematyką w LinkedList, która faktycznie sprawia, że ​​dzielę ją i ArrayList gorzej. Cieszę się, że mogę go aktualizować, więc nie wahaj się wyjaśnić i opracować furuthera. - Numeron
Należy zauważyć że CompressedOops jest teraz domyślnie we wszystkich nowszych pakietach JDK (7, 8 i aktualizacjach 6 przez kilka lat), więc 64-bitowy nie ma znaczenia w ArrayList lub LinkedList rozmiary, chyba że z jakiegoś powodu wyraźnie wyłączyłeś skompresowane pliki. - BeeOnRope
Czy ten obraz wykresu jest dostępny do komercyjnego użytku? Chciałbym go użyć. - Ogen


ArrayList jest to, czego chcesz. LinkedList jest prawie zawsze błędem (wydajności).

Czemu LinkedList ssie:

  • Wykorzystuje wiele małych obiektów pamięci, a zatem wpływa na wydajność w całym procesie.
  • Wiele małych obiektów jest szkodliwych dla pamięci podręcznej.
  • Każda zaindeksowana operacja wymaga przejścia, tj. Ma wydajność O (n). Nie jest to oczywiste w kodzie źródłowym, prowadząc do algorytmów O (n) wolniejszych niż wtedy ArrayListużyto.
  • Uzyskanie dobrej wydajności jest trudne.
  • Nawet jeśli wydajność big-o jest taka sama jak ArrayListprawdopodobnie i tak będzie znacznie wolniej.
  • To drażniące widzieć LinkedList w źródle, ponieważ jest to prawdopodobnie zły wybór.

190
2018-01-01 20:23



Przepraszam. oznaczyłem cię. LinkedList nie wysysa. Istnieją sytuacje, w których klasa LinkedList jest poprawną klasą do użycia. Zgadzam się, że nie ma wielu sytuacji, w których jest to lepsze niż lista tablic, ale one istnieją. Kształcić ludzi, którzy robią głupie rzeczy! - David Turner
Przepraszam, że dostałeś za to dużo głosów oddanych. W rzeczywistości istnieje bardzo niewielki powód, aby korzystać z JavaLink LinkList. Oprócz złej wydajności wykorzystuje również o wiele 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 opakowania z dodatkowymi bajtami, które są z nimi powiązane). - Kevin Brock
Jest to jedna z najbardziej przydatnych odpowiedzi tutaj. To wstyd, że wielu programistów nie rozumie (a) różnicy między abstrakcyjnymi typami danych a konkretnymi implementacjami, oraz (b) rzeczywistą wagą stałych czynników i kosztów pamięci w określaniu wydajności. - Porculus
-1: To jest raczej blinkowany widok. Tak, to prawda, że ​​ArrayList jest bardzo wszechstronnym narzędziem. Ma jednak swoje ograniczenia. Są przypadki, w których spowoduje to kłopoty, i będziesz musiał użyć LinkedList. Oczywiście jest to bardzo specjalistyczne rozwiązanie i, jak każde specjalistyczne narzędzie, w większości przypadków jest lepsze od wszechstronnego. Ale to nie znaczy, że jest "do bani" czy coś w tym stylu, wystarczy wiedzieć, kiedy go użyć. - Malcolm
@DavidTurner: One istnieją, ale myślę, że Tom miał rację, że jeśli musisz zapytać, prawdopodobnie chcesz mieć ArrayList. - Mehrdad


Jako ktoś, kto od około dziesięciu lat wykonuje inżynierię wydajności operacyjnej na bardzo dużych serwisach WWW SOA, wolałbym zachowanie obiektu LinkedList niż ArrayList. Chociaż ciągła przepustowość LinkedList jest gorsza i dlatego może prowadzić do zakupu większej ilości sprzętu - zachowanie ArrayList pod presją może doprowadzić do tego, że aplikacje w klastrze będą rozszerzać swoje tablice w bliskiej synchronizacji, a dla dużych rozmiarów tablic może to prowadzić do braku reakcji. w aplikacji i przestoju, pod presją, co jest katastroficznym zachowaniem.

Podobnie, możesz uzyskać lepszą przepustowość w aplikacji z domyślnej pamięci masowej, ale po otrzymaniu aplikacji java z stertami 10 GB możesz zamknąć aplikację przez 25 sekund podczas pełnych wersji GC, co powoduje przekroczenie limitu czasu i awarie aplikacji SOA. i zawiesza twoje umowy SLA, jeśli występują zbyt często. Nawet jeśli kolektor CMS ma więcej zasobów i nie osiąga takiej samej nieprzetworzonej przepustowości, jest o wiele lepszym wyborem, ponieważ ma bardziej przewidywalne i mniejsze opóźnienie.

ArrayList jest lepszym wyborem dla wydajności, jeśli wszystko, co masz na myśli przez wydajność, to przepustowość i możesz zignorować opóźnienie. Z mojego doświadczenia w pracy nie mogę zignorować najgorszego przypadku.


125
2018-04-08 20:33



Czy innym rozwiązaniem nie jest programistyczne zarządzanie wielkością listy przy użyciu metody zapewnieniaCapacity () ArrayList? Moje pytanie brzmi: dlaczego tak wiele rzeczy jest przechowywanych w grupie kruchej struktury danych, skoro mogą być lepiej przechowywane w mechanizmie buforowania lub db? Poprzedniego dnia miałem wywiad, w którym przeklinali o zła w ArrayList, ale przychodzę tutaj i stwierdzam, że analiza złożoności jest lepsza! WIELKI PUNKT DO DYSKUSJI, MYŚL. DZIĘKI! - ingyhere
gdy otrzymasz aplikacje java z stertami o pojemności 10 GB, możesz zamknąć aplikację na 25 sekund podczas pełnych GC, co powoduje przekroczenie limitu czasu Właściwie z LinkedList mordujesz śmieciarza podczas pełnych GC, musi on iterować nadmiernie dużą LinkedList z miss pamięci podręcznej na każdym węźle. - bestsss
To ... okropne rozwiązanie. zasadniczo polegasz na czyszczeniu GC, co jest niewiarygodnie drogie, kiedy możesz po prostu wywołać metodę ensureCapacity () na liście tabel, zamiast ... - Philip Devine
@Andreas: A LinkedList  zawsze alokuje pięciokrotność pamięci niż zwykła tablica odniesień, więc an ArrayList czasowo wymagające 2,5-krotnie nadal zużywa znacznie mniej pamięci, nawet gdy pamięć nie jest odzyskiwana. Ponieważ duża alokacja macierzy omija przestrzeń Eden, nie mają one żadnego wpływu na zachowanie GC, chyba że naprawdę nie ma wystarczającej ilości pamięci, w takim przypadku LinkedList wybuchło znacznie wcześniej ... - Holger
@Andreas Inną kwestią jest sposób alokowania pamięci. LinkedList potrzebuje tylko niewielkiej części wolnej pamięci do przydzielenia na następny element. ArrayList będzie potrzebować dużego i ciągły wolny blok przestrzeni, aby przydzielić zmienioną tablicę. Jeśli sterty zostaną pofragmentowane, wówczas GC może skończyć porządkowanie całej sterty tylko po to, aby zwolnić odpowiedni pojedynczy blok pamięci. - Piotr Kusmierczyk


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: Big-Oh Notation

ArrayLists są dobre dla wielu osób zapisujących się lub czytających, ale są złe w dodawaniu / usuwaniu z przodu lub środka.


111
2018-05-19 11:21



Nie można porównywać dużych wartości O bezpośrednio, bez myślenia o stałych czynnikach. W przypadku małych list (i większość list jest małych), O (N) ArrayList jest szybszy niż O (1) w LinkedList. - Porculus
Nie zależy mi na wydajności małych list, ani na moim komputerze chyba że jest jakoś użyty w pętli. - Maarten Bodewes
LinkedList nie może naprawdę wstawić w środku O(1). Musi przebiegać przez połowę listy, aby znaleźć punkt wstawienia. - Thomas Ahle
LinkedList: wstaw w środku O (1) - jest NIEPRAWIDŁOWE! Dowiedziałem się, że nawet wstawienie do 1/10 pozycji rozmiaru listy łączy jest wolniejsze niż wstawienie elementu do 1/10 pozycji tablicy ArrayList. A jeszcze gorzej: koniec kolekcji. wstawienie na ostatnie pozycje (nie ostatnie) ArrayList jest szybsze niż na ostatnie pozycje (nie ostatnie) z LinkedList - kachanov
@kananov Wstawianie w LinkedList  jest  O(1)  jeśli masz iterator do pozycji wstawiania, tj. ListIterator.add jest rzekomo O(1) dla LinkedList. - Anony-Mousse


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

LinkedList to prawie zawsze zły wybór, pod względem wydajności. Istnieje kilka bardzo specyficznych algorytmów, do których jest wymagana lista odnośników, ale są one bardzo, bardzo rzadkie, a algorytm zazwyczaj zależy od zdolności LinkedList do wstawiania i usuwania elementów na środku listy stosunkowo szybko, gdy już się tam znajdziesz z ListIteratorem.

Istnieje jeden typowy przypadek użycia, w którym obiekt LinkedList przewyższa ArrayList: kolejkę. Jeśli jednak twoim celem jest wydajność, zamiast listy właściwości LinkedList powinieneś rozważyć użycie ArrayBlockingQueue (jeśli możesz określić górną granicę rozmiaru swojej kolejki z wyprzedzeniem i możesz sobie pozwolić na przydzielenie całej pamięci z góry), lub Implementacja CircularArrayList. (Tak, pochodzi z 2001 roku, więc musisz go wygenerować, ale mam już porównywalne wskaźniki wydajności do tego, co jest cytowane w artykule właśnie w niedawnej maszynie JVM)


92
2017-11-27 01:39



Z Java 6 możesz korzystać ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle
ArrayDeque jest wolniejszy niż LinkedList chyba że wszystkie operacje są na tym samym końcu. Jest OK, gdy jest używany jako stos, ale nie jest dobrą kolejką. - Jeremy List
Untrue - przynajmniej dla implementacji Oracle w jdk1.7.0_60 iw poniższym teście. Stworzyłem test, w którym robię pętlę 10 milionów razy i mam Deque 10 milionów losowych liczb całkowitych. Wewnątrz pętli odpytywam 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 na czele tablicy tak, że nie musi przesuwać wszystkich elementów, gdy głowa jest usuwana. - Henno Vermeulen
ArrayDeque prawdopodobnie będzie szybszy niż Stack gdy jest używany jako stos i szybszy niż LinkedList kiedy jest używany jako kolejka. - i_am_zero
Zauważ, że komentarz akhil_mittal jest cytatem z ArrayDeque dokumentacja. - Stuart Marks


To pytanie dotyczące wydajności. LinkedList jest szybki do dodawania i usuwania elementów, ale ma wolny dostęp do określonego elementu. ArrayList jest szybki, aby uzyskać dostęp do określonego elementu, ale może być powolny do dodania do jednego z końców, a szczególnie powolny do usunięcia w środku.

Array vs ArrayList vs LinkedList vs Vectoridzie bardziej dogłębnie, tak jak Połączona lista.


50
2017-09-21 22:59





Poprawnie lub niepoprawnie: wykonaj test lokalnie i sam zdecyduj!

Edycja / usuwanie jest szybsze w LinkedList niż ArrayList.

ArrayList, wspierane przez Array, która musi być dwukrotnie większa, jest gorsza w przypadku aplikacji o dużej objętości.

Poniżej znajduje się wynik testu jednostkowego dla każdej operacji. Tyczenie 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);
    }
}

49
2018-04-21 00:03



ArrayList nie musi być podwajany, aby być precyzyjnym. Najpierw sprawdź źródła. - Danubian Sailor
Należy zauważyć, że Twój przykład jest wadliwy ... Usuwasz z łańcucha 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 rozmiaru bajtów lista linków działa lepiej, ponieważ rozmiar listy rośnie, przylega tablica (lista) będzie działać lepiej. Co najważniejsze, robisz .equals () na łańcuchach - co nie jest tanią operacją. Jeśli zamiast tego użyłeś liczb całkowitych, myślę, że byłaby różnica. - Centril
- i to prawdopodobnie także dlatego jest tak mała różnica dla usunięcia / zawiera. - Centril
"... jest gorszy w przypadku aplikacji o dużej objętości": To nieporozumienie. LinkedList ma o wiele więcej pamięci, ponieważ dla każdego elementu znajduje się obiekt węzła z pięcioma polami. W wielu systemach, które generują 20 bajtów narzutowych. Średnie obciążenie pamięci na element dla ArrayList to półtorej słowa, które w najgorszym przypadku tworzy 6 bajtów, a 8 bajtów. - Lii
Zrobiłem lepszą wersję twojego testu porównawczego tutaj, z wynikami - Wydajność dołączania do końca dla listy tablic jest sztucznie niska dla ciebie, ponieważ addAll daje macierz pamięci o DOKŁADNIE początkowym rozmiarze, więc pierwsza wstawka zawsze wyzwala arraycopię. Obejmuje to również cykle rozgrzewania, aby umożliwić kompilację JIT przed zgromadzeniem danych. - BobMcGee


ArrayList jest zasadniczo tablicą. LinkedList jest zaimplementowany jako lista podwójnie połączona.

The get jest całkiem jasne. O (1) dla ArrayList, bo ArrayList umożliwić dostęp losowy za pomocą indeksu. O (n) dla LinkedList, ponieważ musi najpierw znaleźć indeks. Uwaga: istnieją różne wersje add i remove.

LinkedList jest szybszy w dodawaniu i usuwaniu, ale wolniejszy w uzyskiwaniu. W skrócie, LinkedList powinno być preferowane, jeśli:

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

=== ArrayList ===

  • dodaj (E e)
    • dodaj na końcu ArrayList
    • wymagają zmiany rozmiaru pamięci.
    • O (n) najgorszy, O (1) amortyzowany
  • dodaj (indeks int, element E)
    • dodaj do określonej pozycji indeksu
    • wymagają zmiany i ewentualnego kosztu zmiany rozmiaru pamięci
    • Na)
  • usuń (indeks int)
    • usuń określony element
    • wymagają zmiany i ewentualnego kosztu zmiany rozmiaru pamięci
    • Na)
  • usuń (obiekt o)
    • usuń pierwsze wystąpienie określonego elementu z tej listy
    • najpierw trzeba przeszukać element, a następnie przesuwać i zmieniać koszt zmiany pamięci
    • Na)

=== Połączona lista ===

  • dodaj (E e)

    • dodaj do końca listy
    • O (1)
  • dodaj (indeks int, element E)

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

Oto liczba z programcreek.com (add i remove są pierwszym typem, tzn. dodają element na końcu listy i usuwają element w określonej pozycji na liście.):

enter image description here


38
2017-11-27 01:41



"LinkedList jest szybszy niż dodawanie / usuwanie". Źle, sprawdź odpowiedź powyżej stackoverflow.com/a/7507740/638670 - Nerrve


ArrayList jest losowo dostępny, podczas gdy LinkedList jest naprawdę tani w rozszerzaniu i usuwaniu elementów. W większości przypadków ArrayList jest w porządku.

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


30
2017-07-07 09:22



LinkedList nie jest tani w dodawaniu elementów. Jest prawie zawsze szybciej dodawać milion elementów do tablicy ArrayList niż dodawać je do listy właściwości LinkedList. A większość list w kodzie realnym nie ma nawet miliona elementów. - Porculus
W dowolnym momencie znasz koszt dodania przedmiotu do swojej listy powiązań. The ArrayList, którego nie masz (ogólnie). Dodanie pojedynczego elementu do tablicy ArrayList zawierającej milion pozycji mógłby zajmie to bardzo dużo czasu - jest to operacja O (n) plus podwójne miejsce do przechowywania, chyba że wcześniej przydzielono miejsce. Dodanie elementu do listy_wijalnej to O (1). Moje ostatnie zdanie stoi. - Dustin
Dodanie pojedynczego elementu do tablicy ArrayList to O (1) bez względu na to, czy jest to 1 milion, czy 1 miliard. Dodanie elementu do listy wynikowej to również O (1). "Dodawanie" oznacza DODAWANIE DO KOŃCA. - kachanov
Musiałeś przeczytać implementację inaczej niż ja. Z mojego doświadczenia wynika, że ​​kopiowanie 1 miliarda elementów zajmuje więcej czasu niż kopiowanie 1 miliona elementów tablicy. - Dustin
@kajanov musisz źle zrozumieć Dustina. Jeśli nie zadeklarowałeś tablicy 1 miliarda przedmiotów, w końcu 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), ale z listą, do której linkujesz, zawsze będziesz get O (1) - Stan R.


1) Szukaj: Operacja wyszukiwania ArrayList jest dość szybka w porównaniu do operacji wyszukiwania LinkedList. get (indeks int) w ArrayList daje wydajność O (1), a wydajność LinkedList to O (n).

Powód: ArrayList utrzymuje oparty na indeksach system dla swoich elementów, ponieważ niejawnie wykorzystuje strukturę danych macierzy, co przyspiesza wyszukiwanie elementu na liście. Z drugiej strony, LinkedList implementuje podwójnie połączoną listę, która wymaga przejścia przez wszystkie elementy do przeszukiwania elementu.

2) Usunięcie: RemoveList usuwa operację, która daje O (1) wydajność, podczas gdy ArrayList daje zmienną wydajność: O (n) w najgorszym przypadku (podczas usuwania pierwszego elementu) i O (1) w najlepszym przypadku (podczas usuwania ostatniego elementu).

Wniosek: Usunięcie elementu LinkList jest szybsze w porównaniu do ArrayList.

Powód: Każdy z elementów LinkedList utrzymuje dwa wskaźniki (adresy), które wskazują oba sąsiednie elementy na liście. Dlatego usuwanie 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) Wydajność wkładek: Metoda LinkList add daje O (1) wydajność, podczas gdy ArrayList daje O (n) w najgorszym przypadku. Powód jest taki sam jak wyjaśniono dla usunięcia.

4) Nakład pamięci: ArrayList utrzymuje indeksy i dane elementów, podczas gdy LinkedList utrzymuje dane elementów i dwa wskaźniki dla węzłów sąsiadów, stąd zużycie pamięci jest stosunkowo wysokie w LinkedList.

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

Zarówno ArrayList, jak i LinkedList są implementacjami interfejsu List. Oba utrzymują porządek wstawiania elementów, co oznacza, że ​​podczas wyświetlania elementów ArrayList i LinkedList zestaw wyników będzie miał tę samą kolejność, w której elementy zostały wstawione do Listy. Obie te klasy są niezsynchronizowane i można je zsynchronizować jawnie za pomocą metody Collections.synchronizedList. Iterator i listIterator zwrócony przez te klasy są odporne na awarie (jeśli lista jest modyfikowana strukturalnie w dowolnym momencie po utworzeniu iteratora, w inny sposób, z wyjątkiem iteratora, własnymi metodami usuwania lub dodawania, iterator wygeneruje wyjątek ConcurrentModificationException).

Kiedy korzystać z LinkedList i kiedy używać ArrayList?

1) Jak wyjaśniono powyżej, operacje wstawiania i usuwania dają dobrą wydajność (O (1)) w LinkedList w porównaniu z ArrayList (O (n)). Stąd, jeśli istnieje wymóg częstego dodawania i usuwania w aplikacji, najlepszym wyborem jest LinkedList.

2) Operacje wyszukiwania (pobierania) są szybkie w ArrayList (O (1)), ale nie w LinkedList (O (n)), więc jeśli jest mniej operacji dodawania i usuwania oraz więcej wymagań dotyczących operacji wyszukiwania, najlepszym wyborem będzie ArrayList.


26
2018-03-01 10:47



Nie zgadzam się z punktem 2 i 3. LinkedList nadal będzie musiał przejść do właściwej pozycji, aby wstawić / usunąć węzeł, a zatem będzie miał złożoność O (n), chyba że będzie musiał wstawić / usunąć na początku / końcu listy. - mdewit
w zasadzie użyj listy połączonych list duszków w grach, które musisz przejść przez wszystkie mimo wszystko i usunąć lub wstawić podczas przechodzenia. jednak wymagałoby to napisania lepszej listy powiązanej dla tego konkretnego zastosowania, ponieważ lista elementów typu LinkedList w języku Java działa jak przykład naukowy. - Lassi Kinnunen