Când să folosiți LinkedList în loc de ArrayList în Java? (Programare, Java, Arraylist, Colecții, Listă Legată)

sdellysse a intrebat.

Întotdeauna am fost unul care să folosească pur și simplu:

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

Eu folosesc interfața ca nume de tip pentru portabilitate, , astfel încât atunci când pun întrebări de acest gen să pot să îmi refac codul.

Când ar trebui să LinkedList să fie folosit în loc de ArrayList și viceversa?

Comentarii

  • A se vedea, de asemenea: Array versus linked-list –  > Por Hawkeye Parker.
  • Vedeți doar citatul autorului LinkedList stackoverflow.com/a/42529652/2032701 și veți avea o idee practică despre această problemă. –  > Por Ruslan.
33 răspunsuri

Rezumat ArrayList cu ArrayDeque sunt preferabile în multe mai multe cazuri de utilizare decât LinkedList. Dacă nu sunteți sigur – începeți cu ArrayList.


TLDR, în ArrayList, accesarea unui element durează constant [O(1)], iar adăugarea unui element durează O(n) [cel mai rău caz]. În LinkedList, adăugarea unui element durează O(n), iar accesarea durează, de asemenea, O(n), dar LinkedList utilizează mai multă memorie decât ArrayList.

LinkedList și ArrayList sunt două implementări diferite ale interfeței List. LinkedList o implementează cu o listă dublu-legată. ArrayList o implementează cu o matrice redimensionată dinamic.

La fel ca în cazul operațiunilor standard cu liste legate și array-uri, diferitele metode vor avea timpi de execuție algoritmică diferiți.

Pentru LinkedList<E>

  • get(int index) este O(n) (cu n/4 pași în medie), dar O(1) atunci când index = 0 sau index = list.size() - 1 (în acest caz, se poate folosi și getFirst() și getLast()). Unul dintre principalele avantaje ale LinkedList<E>
  • add(int index, E element) este O(n) (cu n/4 pași în medie), dar O(1) atunci când index = 0 sau index = list.size() - 1 (în acest caz, se poate folosi și addFirst() și addLast()/add()). Unul dintre principalele avantaje ale LinkedList<E>
  • remove(int index) este O(n) (cu n/4 pași în medie), dar O(1) atunci când index = 0 sau index = list.size() - 1 (în acest caz, se poate folosi și removeFirst() și removeLast()). Unul dintre principalele avantaje ale LinkedList<E>
  • Iterator.remove() este O(1). Unul dintre principalele avantaje ale LinkedList<E>
  • ListIterator.add(E element) este O(1). Unul dintre principalele avantaje ale LinkedList<E>

Notă: Multe dintre operații au nevoie de n/4 pași în medie, constantă număr constant de pași în cel mai bun caz (de exemplu, index = 0) și n/2 pași în cel mai rău caz (la mijlocul listei)

Pentru ArrayList<E>

  • get(int index) este O(1). Principalul beneficiu al ArrayList<E>
  • add(E element) este O(1) amortizat, dar O(n) în cel mai rău caz, deoarece matricea trebuie redimensionată și copiată
  • add(int index, E element) este O(n) (cu n/2 pași în medie)
  • remove(int index) este O(n) (cu n/2 pași în medie)
  • Iterator.remove() este O(n) (cu n/2 pași în medie)
  • ListIterator.add(E element) este O(n) (cu n/2 pași în medie)

Notă: Multe dintre operații au nevoie de n/2 pași în medie, constantă număr constant de pași în cel mai bun caz (sfârșitul listei), n pași în cel mai rău caz (începutul listei)

LinkedList<E> permite inserții sau eliminări în timp constant utilizarea iteratorilor, , dar numai accesul secvențial la elemente. Cu alte cuvinte, se poate parcurge lista înainte sau înapoi, dar găsirea unei poziții în listă necesită un timp proporțional cu dimensiunea listei. Javadoc spune „operațiile care indexează în listă vor parcurge lista de la început sau de la sfârșit, oricare dintre acestea este mai aproape”, , astfel încât aceste metode sunt O(n) (n/4 pași) în medie, deși O(1) pentru index = 0.

ArrayList<E>, , pe de altă parte, permit accesul rapid la citire aleatorie, astfel încât puteți lua orice element în timp constant. Dar adăugarea sau eliminarea de oriunde în afară de capăt necesită deplasarea tuturor elementelor din urmă, fie pentru a face o deschidere, fie pentru a umple golul. De asemenea, dacă adăugați mai multe elemente decât capacitatea tabloului de bază, se alocă un nou tablou (de 1,5 ori mai mare), iar vechiul tablou este copiat în cel nou, astfel încât adăugarea la un tablou ArrayList este O(n) în cel mai rău caz, dar constant în medie.

Prin urmare, în funcție de operațiile pe care intenționați să le efectuați, ar trebui să alegeți implementările în consecință. Iterarea peste oricare dintre tipurile de liste este practic la fel de ieftină. (Iterarea pe o listă ArrayList este mai rapidă din punct de vedere tehnic, dar, dacă nu faceți ceva foarte sensibil la performanță, nu ar trebui să vă faceți griji în această privință – ambele sunt constante).

Principalele avantaje ale utilizării unui LinkedList apar atunci când reutilizați iteratorii existenți pentru a introduce și elimina elemente. Aceste operații pot fi apoi efectuate în O(1) modificând lista doar la nivel local. Într-o listă de tablouri, restul tabloului trebuie să fie mutat (adică copiat). Pe de altă parte, căutarea într-un LinkedList înseamnă urmărirea legăturilor din O(n) (n/2 pași) în cel mai rău caz, în timp ce într-un ArrayList poziția dorită poate fi calculată matematic și accesată în O(1).

Un alt avantaj al utilizării unui LinkedList apar atunci când adăugați sau eliminați din capul listei, deoarece aceste operații sunt O(1), , în timp ce sunt O(n) pentru ArrayList. Rețineți că ArrayDeque poate fi o alternativă bună la LinkedList pentru adăugarea și eliminarea de la cap, dar nu este o soluție List.

De asemenea, dacă aveți liste mari, rețineți că și utilizarea memoriei este diferită. Fiecare element al unei liste LinkedList are mai mult consum de energie, deoarece sunt stocați și pointeri către elementele următoare și anterioare. ArrayLists nu au acest supraîncărcare. Cu toate acestea, ArrayLists ocupă atâta memorie cât este alocată pentru capacitate, indiferent dacă au fost adăugate efectiv elemente.

Capacitatea inițială implicită a unui element ArrayList este destul de mică (10 din Java 1.4 – 1.8). Dar, deoarece implementarea subiacentă este o matrice, matricea trebuie redimensionată dacă adăugați multe elemente. Pentru a evita costul ridicat al redimensionării atunci când știți că veți adăuga o mulțime de elemente, construiți ArrayList cu o capacitate inițială mai mare.

Dacă se utilizează perspectiva structurilor de date pentru a înțelege cele două structuri, un LinkedList este practic o structură de date secvențială care conține un nod de cap. Nodul este un înveliș pentru două componente: o valoare de tip T [acceptată prin generice] și o altă referință la Nodul legat de acesta. Prin urmare, putem afirma că este o structură de date recursivă (un nod conține un alt nod care are un alt nod și așa mai departe…). Adăugarea de elemente durează liniar în LinkedList, așa cum s-a menționat mai sus.

O ArrayList este o matrice care poate crește. Este la fel ca o matrice obișnuită. Sub capotă, atunci când se adaugă un element la indexul i, se creează un alt tablou cu o dimensiune cu 1 mai mare decât dimensiunea anterioară (deci, în general, atunci când se adaugă n elemente la un ArrayList, se creează un nou tablou cu dimensiunea anterioară plus n). Elementele sunt apoi copiate din tabloul anterior în cel nou, iar elementele care urmează să fie adăugate sunt, de asemenea, plasate la indicii specificați.

Comentarii

  • Un lucru pe care mulți oameni îl uită este faptul că ArrayList este compact în memorie, ceea ce înseamnă că este mai ușor de memorizat decât LinkedList. LinkedList ar putea fi împrăștiat peste tot în memoria RAM, în timp ce ArrayList este întotdeauna bine împachetat pentru a profita de localitatea spațială. Acest lucru are ramificații importante în lumea reală. –  > Por AminM.
Numeron

Până în prezent, nimeni nu pare să se fi ocupat de amprenta de memorie a fiecăreia dintre aceste liste, în afară de consensul general că o listă de tip LinkedList este „mult mai mare” decât o ArrayList așa că am făcut niște calcule numerice pentru a demonstra exact cât de mult ocupă ambele liste pentru N referințe nule.

Deoarece referințele sunt fie de 32, fie de 64 de biți (chiar și atunci când sunt nule) pe sistemele respective, am inclus 4 seturi de date pentru 32 și 64 de biți. LinkedLists și ArrayLists.

Notă: Dimensiunile afișate pentru ArrayList linii sunt pentru liste tăiate – În practică, capacitatea tabloului de susținere a unui fișier ArrayList este, în general, mai mare decât numărul actual de elemente.

Nota 2: (mulțumiri BeeOnRope) Deoarece CompressedOops este acum implicit de la jumătatea JDK6 și mai sus, valorile de mai jos pentru mașinile pe 64 de biți se vor potrivi practic cu omologii lor pe 32 de biți, cu excepția cazului în care, desigur, îl dezactivați în mod specific.



Rezultatul arată în mod clar că LinkedList este mult mai mare decât ArrayList, , în special cu un număr foarte mare de elemente. Dacă memoria este un factor important, evitați să folosiți LinkedLists.

Urmează formulele pe care le-am folosit, anunțați-mă dacă am greșit cu ceva și voi remedia. ‘b’ este fie 4 sau 8 pentru sisteme pe 32 sau 64 de biți, iar ‘n’ este numărul de elemente. Rețineți că motivul pentru modurile este că toate obiectele din java vor ocupa un multiplu de 8 octeți de spațiu, indiferent dacă este sau nu utilizat în totalitate.

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)

Comentarii

    242

  • Problema cu matematica dvs. este că graficul dvs. exagerează foarte mult impactul. Modelați obiecte care conțin fiecare doar un singur int, deci 4 sau 8 octeți de date. În lista legată, există, în esență, 4 „cuvinte” de suprataxă. Astfel, graficul dvs. dă impresia că listele legate utilizează „de cinci ori” mai mult spațiu de stocare decât listele de matrice. Acest lucru este greșit. Cheltuielile generale sunt de 16 sau 32 de octeți pe obiect, ca o ajustare aditivă, nu ca un factor de scalare. –  > Por Heath Hunnicutt.
Tom Hawtin – tackline

ArrayList este ceea ce vă doriți. LinkedList este aproape întotdeauna un bug (de performanță).

De ce LinkedList este nașpa:

  • Folosește o mulțime de obiecte mici de memorie și, prin urmare, are un impact asupra performanței în întregul proces.
  • O mulțime de obiecte mici nu sunt bune pentru localizarea în memoria cache.
  • Orice operațiune indexată necesită o traversare, adică are o performanță O(n). Acest lucru nu este evident în codul sursă, ceea ce duce la algoritmi O(n) mai lenți decât dacă ArrayList era utilizat.
  • Obținerea unor performanțe bune este dificilă.
  • Chiar și atunci când performanța big-O este aceeași cu ArrayList, , probabil că va fi oricum semnificativ mai lent.
  • Este ciudat să vezi LinkedList în sursă, deoarece este probabil alegerea greșită.

lamont

În calitate de persoană care a făcut inginerie de performanță operațională pe servicii web SOA la scară foarte mare timp de aproximativ un deceniu, aș prefera comportamentul LinkedList față de ArrayList. În timp ce randamentul în regim staționar al LinkedList este mai rău și, prin urmare, ar putea duce la cumpărarea de mai mult hardware – comportamentul lui ArrayList sub presiune ar putea duce la aplicații într-un cluster care își extind array-urile aproape sincronizat și, pentru dimensiuni mari ale array-urilor, ar putea duce la lipsa de reacție a aplicației și la o întrerupere, în timp ce se află sub presiune, ceea ce reprezintă un comportament catastrofal.

În mod similar, puteți obține un randament mai bun într-o aplicație cu ajutorul colectorului de gunoi implicit, dar odată ce obțineți aplicații java cu grămezi de 10 GB, puteți bloca aplicația timp de 25 de secunde în timpul unui GC complet, ceea ce cauzează timeout-uri și eșecuri în aplicațiile SOA și vă distruge SLA-urile dacă se întâmplă prea des. Chiar dacă colectorul CMS necesită mai multe resurse și nu atinge același debit brut, este o alegere mult mai bună, deoarece are o latență mai previzibilă și mai mică.

ArrayList este o alegere mai bună pentru performanță doar dacă tot ceea ce înțelegeți prin performanță este debitul și puteți ignora latența. Din experiența mea la locul de muncă, nu pot ignora latența în cel mai rău caz.

Comentarii

  • O altă soluție nu ar fi gestionarea programatică a dimensiunii listei prin utilizarea metodei ensureCapacity() a ArrayList? Întrebarea mea este de ce sunt stocate atât de multe lucruri într-o grămadă de structuri de date fragile, când ar fi mai bine să fie stocate într-un mecanism de cache sau db? Zilele trecute am avut un interviu în care se înjura în sus și în jos despre relele ArrayList, dar vin aici și constat că analiza complexității este pe toate planurile mai bună! UN PUNCT DE DISCUȚIE EXCELENT, TOTUȘI. MULȚUMIRI! –  > Por ingyhere.
  • 23

  • odată ce obțineți aplicații java cu heaps de 10 GB, puteți ajunge să blocați aplicația timp de 25 de secunde în timpul unui GCs complet, ceea ce cauzează timeout-uri. De fapt, cu LinkedList ucizi colectorul de gunoi în timpul GC-urilor complete, acesta trebuie să parcurgă LinkedList-ul prea mare cu rateuri de cache pe fiecare nod. –  > Por bestsss.
  • Aceasta este… o soluție oribilă. Practic, vă bazați pe GC pentru a face curățenie, ceea ce este incredibil de costisitor, când puteți apela pur și simplu la ensureCapacity() pe o listă de tip arraylist… –  > Por Philip Devine.
  • @Andreas: atunci când o listă crește și se micșorează în trepte de câte un element, nu există nicio problemă cu ArrayList deloc, deoarece nici măcar nu are nevoie de memorie suplimentară pentru asta. Luând în considerare posibilitatea ca ArrayList trebuie să își mărească capacitatea o dată cu în timpul întregii durate de viață a unui serviciu web ca un motiv pentru a scădea performanța cu o LinkedList, , este destul de ciudat, mai ales dacă luați în considerare costul serviciului web de I/O în comparație cu acesta. Extinderea capacității unui ArrayList, , chiar și cu milioane de elemente, este destul de puțin probabil să fie observată ca latență. –  > Por Holger.
  • @Andreas: A LinkedList întotdeauna alocă de cinci ori mai multă memorie decât o matrice simplă de referințe, astfel încât un ArrayList care necesită temporar de 2,5 ori consumă totuși mult mai puțină memorie, chiar dacă memoria nu este recuperată. Deoarece alocarea de array-uri mari ocolește spațiul Eden, acestea nu au niciun impact asupra comportamentului GC, cu excepția cazului în care nu există cu adevărat suficientă memorie, caz în care, opțiunea LinkedList explodează mult mai devreme… –  > Por Holger.
Michael Munsey
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)

Algoritmi: Notarea Big-Oh (arhivat)

ArrayLists sunt bune pentru write-once-once-read-many sau appenders, dar nu sunt bune pentru adăugarea/eliminarea din față sau din mijloc.

Comentarii

    44

  • Nu puteți compara direct valorile big-O fără să vă gândiți la factori constanți. Pentru listele mici (și majoritatea listelor sunt mici), O(N) al lui ArrayList este mai rapid decât O(1) al lui LinkedList. –  > Por Porculus.
  • Nu-mi pasă de performanța listelor mici și nici computerului meu nu-i pasă de performanța listelor mici cu excepția cazului în care nu este folosită cumva într-o buclă. –  > Por Maarten Bodewes.
  • 48

  • LinkedList nu se poate insera cu adevărat la mijloc în O(1). Trebuie să parcurgă jumătate din listă pentru a găsi punctul de inserție. –  > Por Thomas Ahle.
  • LinkedList: inserare în mijloc O(1) – este GREȘIT! Am aflat că până și inserarea în poziția 1/10 din dimensiunea LinkedList este mai lentă decât inserarea unui element în poziția 1/10 dintr-o ArrayList. Și chiar mai rău: sfârșitul colecției. inserarea în ultimele poziții (nu chiar ultimele) din ArrayList este mai rapidă decât în ultimele poziții (nu chiar ultimele) din LinkedList –  > Por kachanov.
  • 16

  • @kachanov Inserarea într-un LinkedList este O(1) dacă aveți un iterator la poziția de inserție, , adică ListIterator.add se presupune că este O(1) pentru un LinkedList. –  > Por A RENUNȚAT–Anony-Mousse.
Daniel Martin

Da, știu, este o întrebare veche, dar îmi voi spune părerea:

LinkedList este aproape întotdeauna alegerea greșită, din punct de vedere al performanței. Există unii algoritmi foarte specifici în care se solicită LinkedList, dar aceștia sunt foarte, foarte rari, iar algoritmul va depinde, de obicei, în mod specific de capacitatea LinkedList de a introduce și șterge elemente în mijlocul listei relativ rapid, după ce ați navigat acolo cu un ListIterator.

Există un caz comun de utilizare în care LinkedList este mai performant decât ArrayList: cel al unei cozi. Cu toate acestea, dacă obiectivul dvs. este performanța, în loc de LinkedList ar trebui să luați în considerare și utilizarea unui ArrayBlockingQueue (dacă puteți determina din timp o limită superioară a dimensiunii cozii și vă puteți permite să alocați toată memoria în avans) sau a acestui implementare CircularArrayList. (Da, este din 2001, așa că va trebui să o generalizați, dar am obținut rate de performanță comparabile cu cele citate în articol chiar acum, într-un JVM recent)

Comentarii

    40

  • Din Java 6 puteți utiliza ArrayDeque. docs.oracle.com/javase/6/docs/api/java/java/util/ArrayDeque.html –  > Por Thomas Ahle.
  • ArrayDeque este mai lent decât LinkedList cu excepția cazului în care toate operațiile sunt la același capăt. Este OK atunci când este folosit ca stivă, dar nu face o coadă bună. –  > Por Jeremy List.
  • Neadevărat – cel puțin pentru implementarea Oracle în jdk1.7.0_60 și în următorul test. Am creat un test în care fac o buclă de 10 milioane de ori și am un Deque de 10 milioane de numere întregi aleatorii. În interiorul buclei interoghez un element din și ofer un element constant. Pe calculatorul meu, LinkedList este de peste 10 ori mai lent decât ArrayDeque și folosește mai puțină memorie). Motivul este că, spre deosebire de ArrayList, ArrayDeque păstrează un pointer la capul tabloului, astfel încât nu trebuie să mute toate elementele atunci când capul este eliminat. –  > Por Henno Vermeulen.
  • ArrayDeque este probabil să fie mai rapid decât Stack atunci când este utilizat ca stivă și mai rapid decât LinkedList atunci când este utilizat ca o coadă. –  > Por akhil_mittal.
  • Rețineți că comentariul lui akhil_mittal este un citat din ArrayDeque documentație. –  > Por Stuart Marks.
dgtized

Este o întrebare legată de eficiență. LinkedList este rapid pentru adăugarea și ștergerea elementelor, dar lent pentru a accesa un anumit element. ArrayList este rapid pentru accesarea unui anumit element, dar poate fi lent pentru a adăuga la oricare dintre capete și, mai ales, lent pentru a șterge la mijloc.

Array vs ArrayList vs LinkedList vs Vector este mai detaliat, la fel ca și Lista legată.

Comentarii

  • Merită să menționăm aici că LinkedList este rapid pentru adăugarea/eliminarea doar în prima și ultima poziție – atunci complexitatea va fi O(1), dar adăugarea în mijloc va fi tot O(n), deoarece trebuie să parcurgem aproximativ n/2 elemente din LinkedList. –  > Por Dmitriy Fialkovskiy.
Ruslan

Joshua Bloch, autorul cărții LinkedList:

Folosește cineva de fapt LinkedList? Eu am scris-o și nu o folosesc niciodată.

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

Îmi pare rău pentru răspuns că nu este atât de informativ ca celelalte răspunsuri, dar am crezut că va fi cel mai interesant și auto-explicativ.

Ash

Corect sau Incorect: Vă rugăm să executați testul local și să decideți singur!

Editarea/eliminarea este mai rapidă în LinkedList decât ArrayList.

ArrayList, , susținută de Array, , care trebuie să fie de două ori mai mare, este mai rău în aplicații de volum mare.

Mai jos este rezultatul testului unitar pentru fiecare operațiune.Timingul este dat în nanosecunde.


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

Iată codul:

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

Comentarii

  • ArrayList nu trebuie să fie dublată, pentru a fi precis. Vă rugăm să verificați mai întâi sursele. –  > Por Danubian Sailor.
  • Trebuie remarcat faptul că exemplul dvs. este eronat… Eliminați din șirul de între: 18 + [2, 12] octeți („true0false”, „true500000false”), în medie 25 octeți, care sunt dimensiunile elementelor din mijloc. Se știe că, pe măsură ce crește dimensiunea în octeți a elementelor, lista legată se comportă mai bine, pe măsură ce crește dimensiunea listei, o matrice (listă) contiguă se va comporta mai bine. Cel mai important, faceți .equals() pe șiruri de caractere – care nu este o operațiune ieftină. Dacă ați folosi în schimb numere întregi, cred că ar exista o diferență. –  > Por Centril.
  • „… este mai rău în cazul aplicațiilor de volum mare„: Aceasta este o neînțelegere. LinkedList are mult mai multă memorie pentru că pentru fiecare element există un obiect nod cu cinci câmpuri. Pe multe sisteme, acest lucru înseamnă 20 de octeți de memorie în plus. Media costurilor de memorie pentru fiecare element pentru ArrayList este de un cuvânt și jumătate, ceea ce înseamnă 6 octeți și 8 octeți în cel mai rău caz. –  > Por Lii.
  • Am realizat o versiune mai bună a indicatorului dvs. de referință aici, cu rezultate – performanța „append-on-end” pentru arraylist este artificial de scăzută în cazul dumneavoastră, deoarece addAll oferă un array de stocare de EXACT dimensiunea inițială, astfel încât prima inserție declanșează întotdeauna o copiere a array-ului. De asemenea, aceasta include cicluri de încălzire pentru a permite compilarea JIT înainte de colectarea datelor. –  > Por BobMcGee.
  • @BillK începând cu Java 8, puteți utiliza removeIf(element -> condition) acolo unde se potrivește, ceea ce poate fi semnificativ mai rapid pentru o ArrayList, , în comparație cu bucla și eliminarea prin intermediul iteratorului, deoarece nu este necesar să se decaleze întregul rest pentru fiecare element individual. Indiferent dacă acest lucru se comportă mai bine sau mai rău decât LinkedList depinde de scenariul particular, deoarece un LinkedList este O(1) în teorie, dar eliminarea unui singur nod necesită mai multe accesări de memorie, care pot depăși cu ușurință numărul necesar pentru ArrayList atunci când se elimină un număr semnificativ de elemente. –  > Por Holger.
Ryan

ArrayList este, în esență, o matrice. LinkedList este implementat ca o listă dublu legată.

Adresa get este destul de clară. O(1) pentru ArrayList, , deoarece ArrayList permite accesul aleatoriu prin utilizarea indexului. O(n) pentru LinkedList, , deoarece trebuie să găsească mai întâi indexul. Notă: există diferite versiuni ale add și remove.

LinkedList este mai rapidă la adăugarea și eliminarea, dar mai lentă la obținerea. Pe scurt, LinkedList ar trebui să fie preferat dacă:

  1. nu există un număr mare de accesări aleatorii ale unui element
  2. există un număr mare de operații de adăugare/eliminare

=== ArrayList ===

  • add(E e)
    • adăugare la sfârșitul ArrayList
    • necesită costuri de redimensionare a memoriei.
    • O(n) în cel mai rău caz, O(1) amortizat
  • add(int index, E element)
    • adăugare la o anumită poziție a indexului
    • necesită decalare & posibil cost de redimensionare a memoriei
    • O(n)
  • remove(int index)
    • elimină un element specificat
    • necesită deplasare & posibil cost de redimensionare a memoriei
    • O(n)
  • remove(Obiect o)
    • elimină prima apariție a elementului specificat din această listă
    • este necesar să se caute mai întâi elementul, iar apoi să se facă o deplasare & posibil cost de redimensionare a memoriei
    • O(n)

=== LinkedList ===

  • add(E e)

    • adaugă la sfârșitul listei
    • O(1)
  • add(int index, E element)

    • se inserează în poziția specificată
    • trebuie să se găsească mai întâi poziția
    • O(n)
  • remove()
    • elimină primul element din listă
    • O(1)
  • remove(int index)
    • elimină elementul cu indicele specificat
    • trebuie să se găsească mai întâi elementul
    • O(n)
  • remove(Obiect o)
    • elimină prima apariție a elementului specificat
    • trebuie să se găsească primul element
    • O(n)

Iată o figură din programcreek.com (add și remove sunt de primul tip, adică adaugă un element la sfârșitul listei și elimină elementul de la poziția specificată în listă):

Comentarii

  • „LinkedList este mai rapid decât add/remove”. Greșit, verificați răspunsul de mai sus stackoverflow.com/a/7507740/638670 –  > Por Abbas Gadhia.
Lior Bar-On

TL;DR datorită arhitecturii moderne a calculatoarelor, ArrayList va fi semnificativ mai eficientă pentru aproape orice caz de utilizare posibil – și, prin urmare LinkedList ar trebui evitată cu excepția unor cazuri foarte unice și extreme.


În teorie, LinkedList are o performanță O(1) pentru add(E element)

De asemenea, adăugarea unui element în mijlocul unei liste ar trebui să fie foarte eficientă.

Practica este foarte diferită, deoarece LinkedList este un ostilă memoriei cache structură de date. Din punctul de vedere al performanței – există foarte puține cazuri în care LinkedList ar putea fi mai performant decât prietenoasă cu memoria cache ArrayList.

Iată rezultatele unui test de referință care testează inserarea elementelor în locații aleatorii. După cum se poate observa, lista de matrice este mult mai eficientă, deși, teoretic, fiecare inserare în mijlocul listei va necesita „mutarea” elementului în mod normal. n ultimele elemente ale matricei (valorile mai mici sunt mai bune):

Lucrând pe o generație ulterioară de hardware (cache-uri mai mari și mai eficiente) – rezultatele sunt și mai concludente:

LinkedList are nevoie de mult mai mult timp pentru a îndeplini aceeași sarcină. sursa Codul sursă

Există două motive principale pentru acest lucru:

  1. În principal, – faptul că nodurile din LinkedList sunt împrăștiate aleatoriu în memorie. Memoria RAM („Random Access Memory”) nu este cu adevărat aleatorie, iar blocurile de memorie trebuie să fie preluate în memoria cache. Această operațiune durează, iar atunci când astfel de fetch-uri se întâmplă frecvent – paginile de memorie din memoria cache trebuie înlocuite tot timpul -> Cache misses -> Cache nu este eficient.ArrayList elementele sunt stocate pe memorie continuă – ceea ce este exact ceea ce optimizează arhitectura modernă a procesorului.

  2. Secundar LinkedList necesară pentru a păstra pointeri back/forward, ceea ce înseamnă un consum de memorie de 3 ori mai mare pentru fiecare valoare stocată, comparativ cu ArrayList.

DynamicIntArray, , btw, este o implementare personalizată ArrayList care deține Int (tip primitiv) și nu obiecte – prin urmare, toate datele sunt stocate în mod real în mod adiacent – deci și mai eficient.

Un element cheie de reținut este faptul că costul recuperării unui bloc de memorie este mai semnificativ decât costul accesării unei singure celule de memorie. De aceea, citirea a 1 MB de memorie secvențială este de până la x400 de ori mai rapidă decât citirea acestei cantități de date din diferite blocuri de memorie:

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

Sursa: Cifrele de latență pe care orice programator ar trebui să le cunoască

Pentru a clarifica și mai mult acest aspect, vă rugăm să verificați benchmark-ul de adăugare a elementelor la începutul listei. Acesta este un caz de utilizare în care, în teorie, se poate spune că LinkedList ar trebui să strălucească cu adevărat, iar ArrayList ar trebui să prezinte rezultate slabe sau chiar mai proaste:

Notă: acesta este un punct de referință al librăriei C++ Std, dar experiența mea anterioară a arătat că rezultatele din C++ și Java sunt foarte similare. Codul sursă

Copierea unui volum secvențial de memorie este o operațiune optimizată de procesoarele moderne – schimbând teoria și făcând, din nou, în realitate, ArrayList/Vector mult mai eficient


Credite: Toate benchmark-urile postate aici sunt create de Kjell Hedström. Chiar și mai multe date pot fi găsite pe blogul său

Comentarii

  • Nu aș numi o coadă unică sau extremă! O coadă fifo este mult mai ușor de implementat pe o LinkedList în loc de o ArrayList. Este de fapt un coșmar pe un ArrayList, deoarece trebuie să urmărești propriul start, stop și să faci propria realocare, ai putea la fel de bine să folosești o matrice, dar o Linked List ESTE un Fifo. Nu sunt sigur de implementarea Java, dar o LinkedList poate face O(1) atât pentru operațiunile de coadă, cât și pentru cele de dequeue (necesită un pointer special la elementul de coadă pentru eliminare, pe care presupun că Java îl are, dar nu am verificat de două ori). –  > Por Bill K.
  • Inserarea în mijlocul unei ArrayList array utilizează metoda nativă java.lang.System.arraycopy() care este scrisă în C++ în OpenJDK. astfel încât, deși în teorie un fișier LinkedList are mai puțină treabă de făcut în practică există atât de multe mecanisme extralingvistice care fac ca „Big O” să fie în mare parte irelevant. În special cât de prietenoase sunt lucrurile cu memoria cache, conform acestui răspuns excelent. –  > Por simbo1905.
Dustin

ArrayList este accesibil în mod aleatoriu, în timp ce LinkedList este foarte ieftin de extins și de eliminat elemente din el. Pentru majoritatea cazurilor, ArrayList este în regulă.

Cu excepția cazului în care ați creat liste mari și ați măsurat un blocaj, probabil că nu va trebui să vă faceți griji cu privire la această diferență.

Comentarii

    18

  • Nu este ieftin să adăugați elemente la LinkedList. Este aproape întotdeauna mai rapid să adăugați un milion de elemente la o ArrayList decât să le adăugați la o LinkedList. Iar majoritatea listelor din codul din lumea reală nu au nici măcar un milion de elemente. –  > Por Porculus.
  • În orice moment, cunoașteți costul adăugării unui element în LinkedList. La ArrayList nu știți (în general). Adăugarea unui singur element la o ArrayList care conține un milion de elemente ar putea dura foarte mult timp – este o operațiune O(n) plus dublul stocării, cu excepția cazului în care ați prealocat spațiu. Adăugarea unui element la o LinkedList este O(1). Ultima mea afirmație rămâne valabilă. –  > Por Dustin.
  • Adăugarea unui singur element la o ArrayList este O(1), indiferent dacă este vorba de 1 milion sau 1 miliard. Adăugarea unui element la o LinkedList este, de asemenea, O(1). „Adăugarea” înseamnă A ADĂUGAREA la sfârșit. –  > Por kachanov.
  • Probabil că ai citit implementarea altfel decât mine. Din experiența mea, copierea unui array de 1 miliard de elemente durează mai mult decât copierea unui array de 1 milion de elemente. –  > Por Dustin.
  • @kachanov probabil că nu l-ai înțeles bine pe Dustin. Cu excepția cazului în care ați declarat un array de 1 miliard de elemente, în cele din urmă va trebui să redimensionați array-ul, caz în care va trebui să copiați toate elementele într-un array nou mai mare, prin urmare, uneori veți obține O (N), însă cu o listă legată veți obține întotdeauna O (1) – -.  > Por Stan R..
Jesse Wilson

În cazul în care codul dumneavoastră are add(0) și remove(0), , utilizați un LinkedList și va fi mai drăguț addFirst() și removeFirst() metode. În caz contrar, utilizați ArrayList.

Și, bineînțeles, Guava‘s ImmutableList este cel mai bun prieten al dumneavoastră.

Comentarii

  • Pentru listele mici, ArrayList.add(0) va fi întotdeauna mai rapid decât LinkedList.addFirst(). –  > Por Porculus.
  • @Porculus Aud în mod constant acest argument că pentru listele mici ArrayList.add(0) va fi mai rapid, acest mic este cât de mic? 10 elemente, 10 milioane, ?  > Por garg10may.
  • @garg10may mic este mai mic decât 10. –  > Por Jesse Wilson.
  • @Porculus small înseamnă mai puțin decât capacitatea maximă a matricei interne care stă la baza ArrayList. –  > Por Janac Meena.
Gayan Weerakutti

De obicei, folosesc una în detrimentul celeilalte în funcție de complexitatea temporală a operațiilor pe care le-aș efectua pe lista respectivă.

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

Comentarii

  • ArrayDeque echilibrează puțin mai mult lucrurile în favoarea array-urilor, deoarece inserarea/eliminarea din față/din spate sunt toate O(1), singurul lucru la care Linked List încă câștigă este adăugarea/eliminarea în timpul traversării (operațiunile Iterator). –  > Por Bill K.
Ajax

Știu că este o postare veche, dar sincer nu-mi vine să cred că nimeni nu a menționat că LinkedList implementează Deque. Uitați-vă doar la metodele din Deque (și Queue); dacă doriți o comparație corectă, încercați să rulați LinkedList cu ArrayDeque și faceți o comparație caracteristică cu caracteristică.

Abhijeet Ashok Muneshwar

Să comparăm LinkedList și ArrayList cu parametrii de mai jos:

1. Implementare

ArrayList este implementarea matricei redimensionabile a interfeței list, în timp ce

LinkedList este implementarea listei cu legături duble a interfeței list.


2. Performanță

  • get(int index) sau operațiunea de căutare

    ArrayList operația get(int index) se execută în timp constant, adică O(1), în timp ce

    LinkedList get(int index) este O(n).

    Motivul pentru care ArrayList este mai rapid decât LinkedList este faptul că ArrayList utilizează un sistem bazat pe indici pentru elementele sale, deoarece utilizează în mod intern o structură de date de tip array, pe de altă parte,

    LinkedList nu oferă acces pe bază de index pentru elementele sale, deoarece itera fie de la început, fie de la sfârșit (în funcție de care este mai aproape) pentru a prelua nodul la indexul de element specificat.

  • Operațiunea insert() sau add(Object)

    Inserțiile în LinkedList sunt, în general, rapide în comparație cu ArrayList. În LinkedList, adăugarea sau inserția este o operațiune O(1).

    În timp ce în ArrayList, dacă matricea este completă, adică în cel mai rău caz, există un cost suplimentar pentru redimensionarea matricei și copierea elementelor în noua matrice, ceea ce face ca timpul de execuție al operației de adăugare în ArrayList să fie O(n), în caz contrar fiind O(1).

  • Operațiunea remove(int)

    Operațiunea de eliminare în LinkedList este, în general, la fel ca în ArrayList, adică O(n).

    În LinkedList, există două metode de eliminare supraîncărcate: una este remove() fără parametru, care elimină capul listei și se execută în timp constant O(1). Cealaltă metodă supraîncărcată de eliminare în LinkedList este remove(int) sau remove(Object) care elimină obiectul sau int trecut ca parametru. Această metodă parcurge LinkedList până când găsește obiectul și îl deconectează din lista originală. Prin urmare, timpul de execuție al acestei metode este O(n).

    În timp ce în ArrayList remove(int) presupune copierea elementelor din vechea matrice în noua matrice actualizată, de aceea timpul de execuție este O(n).


3. Iterator invers

LinkedList poate fi iterată în sens invers folosind descendingIterator() în timp ce

nu există un descendingIterator() în ArrayList , așa că trebuie să scriem propriul nostru cod pentru a itera peste ArrayList în sens invers.


4. Capacitatea inițială

În cazul în care constructorul nu este supraîncărcat, atunci ArrayList creează o listă goală cu o capacitate inițială de 10, în timp ce

LinkedList construiește doar o listă goală fără capacitate inițială.


5. Cheltuieli de memorie

Cheltuielile de memorie în LinkedList este mai mare în comparație cu ArrayList, deoarece un nod din LinkedList trebuie să mențină adresele nodului următor și ale celui anterior. În timp ce

În ArrayList fiecare index păstrează doar obiectul (datele) real.


Sursa

Rajith Delantha

Iată notația Big-O în ambele variante ArrayList și LinkedList și, de asemenea, în CopyOnWrite-ArrayList:

ArrayList

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

LinkedList

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)

Pe baza acestora trebuie să decideți ce să alegeți. 🙂

Comentarii

  • >>>>> ArrayList add –> O(1) <- nu este adevărat. În unele cazuri, ArrayList va trebui să crească pentru a adăuga încă un element –  > Por kachanov.
  • LinkedList remove nu este O(1), ci ar trebui să caute elementul care urmează să fie eliminat, prin urmare, în cel mai rău caz O(n) și în medie O(n/2) –  > Por garg10may.
  • Nici nu este LinkedList.add(), , deși majoritatea răspunsurilor de aici spun acest lucru. –  > Por user207421.
PhiLho

Pe lângă celelalte argumente bune de mai sus, ar trebui să observați că ArrayList implementează RandomAccess interfață, în timp ce LinkedList implementează Queue.

Așadar, ele abordează cumva probleme ușor diferite, cu diferențe de eficiență și comportament (a se vedea lista lor de metode).

Matthew Schinckel

Depinde de operațiile pe care le veți face mai mult pe Listă.

ArrayList este mai rapidă pentru a accesa o valoare indexată. Este mult mai rău la inserarea sau ștergerea obiectelor.

Pentru a afla mai multe, citiți orice articol care vorbește despre diferența dintre array-uri și listele legate.

Comentarii

  • Pentru a afla mai multe, nu citiți, doar scrieți codul. și veți afla că implementarea ArrayList este mai rapidă decât LinkedList la inserare și ștergere. –  > Por kachanov.
kemiller2002

O listă de array este, în esență, un array cu metode de adăugare a elementelor etc. (și ar trebui să folosiți în schimb o listă generică). Este o colecție de elemente care pot fi accesate prin intermediul unui indexator (de exemplu [0]). Aceasta implică o progresie de la un element la altul.

O listă legată specifică o progresie de la un element la altul (Element a -> element b). Puteți obține același efect cu o listă de matrice, dar o listă legată spune în mod absolut ce element trebuie să urmeze celui precedent.

chharvey

Comentarii

  • Bună @chharvey , Răspunsurile Link only primesc 6 Upvotes ? Vă rugăm să adăugați câteva puncte care ar putea susține link-ul .Ce se întâmplă dacă oracle își schimbă link-ul? – user8898216
Karussell

O caracteristică importantă a unei liste legate (pe care nu am citit-o într-un alt răspuns) este concatenarea a două liste. Cu o matrice acest lucru este O(n) (+ cheltuielile generale ale unor realocări) cu o listă legată este doar O(1) sau O(2) 😉

Important: Pentru Java, este LinkedList acest lucru nu este adevărat! A se vedea Există o metodă rapidă de concatenare pentru listele legate în Java?

Comentarii

  • Cum este aceasta? Acest lucru poate fi valabil pentru structurile de date cu liste legate, dar nu și pentru un obiect Java LinkList. Nu puteți să indicați pur și simplu un obiect next dintr-o listă către primul nod din cea de-a doua listă. Singura modalitate este de a utiliza addAll() care adaugă elementele secvențial, deși este mai bine decât să faci o buclă și să apelezi la add() pentru fiecare element. Pentru a face acest lucru rapid, în O(1), ați avea nevoie de o clasă de compunere (cum ar fi org.apache.commons.collections.collection.CompositeCollection), dar atunci acest lucru ar funcționa pentru orice tip de listă/colecție. –  > Por Kevin Brock.
  • da, adevărat. Am editat răspunsul în consecință. dar vedeți acest răspuns pentru „cum” să faceți acest lucru cu LinkedList: stackoverflow.com/questions/2494031/… –  > Por Karussell.
Nesan Mano

ArrayList și LinkedList au propriile argumente pro și contra.

ArrayList folosește adrese de memorie contiguă în comparație cu LinkedList care folosește pointeri spre următorul nod. Astfel, atunci când doriți să căutați un element într-un ArrayList este mai rapid decât să faceți n iterații cu LinkedList.

Pe de altă parte, inserția și ștergerea într-o LinkedList sunt mult mai ușoare, deoarece trebuie doar să schimbați indicatoarele, în timp ce o ArrayList implică utilizarea operației de schimbare pentru orice inserție sau ștergere.

Dacă în aplicația dvs. aveți operații frecvente de recuperare, utilizați un ArrayList. Dacă aveți operații frecvente de inserție și ștergere, utilizați un LinkedList.

gaijinco

Am citit răspunsurile, dar există un scenariu în care folosesc întotdeauna un LinkedList în locul unui ArrayList pe care vreau să îl împărtășesc pentru a auzi păreri:

De fiecare dată când am avut o metodă care returnează o listă de date obținute dintr-o BD am folosit întotdeauna o LinkedList.

Raționamentul meu a fost că, deoarece este imposibil să știu exact câte rezultate obțin, nu se va irosi memorie (ca în ArrayList cu diferența dintre capacitatea și numărul real de elemente) și nu se va pierde timp încercând să dublez capacitatea.

În ceea ce privește ArrayList, sunt de acord că cel puțin ar trebui să folosiți întotdeauna constructorul cu capacitatea inițială, pentru a minimiza pe cât posibil duplicarea array-urilor.

Real73

ArrayList și LinkedList ambele implementează List interface și metodele și rezultatele acestora sunt aproape identice. Cu toate acestea, există câteva diferențe între ele, care fac ca una să fie mai bună decât cealaltă, în funcție de cerințe.

ArrayList vs LinkedList

1) Search: ArrayList operațiunea de căutare este destul de rapidă în comparație cu LinkedList operațiunea de căutare. get(int index) în ArrayList oferă performanța de O(1) în timp ce LinkedList performanța este O(n).

Reason: ArrayList menține un sistem bazat pe index pentru elementele sale, deoarece utilizează implicit structura de date array, ceea ce îl face mai rapid pentru căutarea unui element în listă. Pe de altă parte LinkedList implementează o listă dublu legată care necesită parcurgerea tuturor elementelor pentru căutarea unui element.

2) Deletion: LinkedList operația de eliminare oferă O(1) performanță în timp ce ArrayList oferă o performanță variabilă: O(n) în cel mai rău caz (în timpul eliminării primului element) și O(1) în cel mai bun caz (în timpul eliminării ultimului element).

Concluzie: Ștergerea elementelor din LinkedList este mai rapidă în comparație cu ArrayList.

Motivul: Fiecare element din LinkedList păstrează doi pointeri (adrese) care indică ambele elemente vecine din listă. Prin urmare, eliminarea necesită doar modificarea locației indicatorului în cele două noduri (elemente) vecine nodului care urmează să fie eliminat. În timp ce în ArrayList toate elementele trebuie să fie deplasate pentru a umple spațiul creat de elementul eliminat.

3) Inserts Performance: LinkedList Metoda add oferă O(1) performanță, în timp ce ArrayList oferă O(n) în cel mai rău caz. Motivul este același cu cel explicat pentru metoda remove.

4) Memory Overhead: ArrayList menține indicii și datele elementelor în timp ce LinkedList păstrează datele elementelor și doi pointeri pentru nodurile vecine.

prin urmare, consumul de memorie este ridicat în LinkedList comparativ cu LinkedList.

Există câteva asemănări între aceste clase, care sunt următoarele:

  • Atât ArrayList, cât și LinkedList sunt implementări ale interfeței List.
  • Ambele clase păstrează ordinea de inserție a elementelor, ceea ce înseamnă că, la afișarea elementelor ArrayList și LinkedList, setul de rezultate va avea aceeași ordine în care elementele au fost inserate în listă.
  • Ambele clase sunt nesincronizate și pot fi sincronizate în mod explicit prin utilizarea metodei Collections.synchronizedList.
  • iterator și listIterator returnate de aceste clase sunt fail-fast (în cazul în care lista este modificată structural în orice moment după crearea iteratorului, în orice mod, cu excepția metodei iterator’s propriile metode de eliminare sau adăugare, iteratorul va fi throw a ConcurrentModificationException).

Când se utilizează LinkedList și când se utilizează ArrayList?

  • După cum s-a explicat mai sus, operațiile de inserare și eliminare oferă performanțe bune (O(1)) în LinkedList în comparație cu ArrayList(O(n)).

    Prin urmare, în cazul în care există o cerință de adăugare și ștergere frecventă în aplicație, LinkedList este cea mai bună alegere.

  • Căutare (get method) sunt rapide în Arraylist (O(1)) dar nu și în LinkedList (O(n))

    astfel încât, dacă sunt necesare mai puține operații de adăugare și ștergere și mai multe operații de căutare, ArrayList ar fi cea mai bună alegere.

Amitābha

Operațiunea get(i) în ArrayList este mai rapidă decât în LinkedList, deoarece:
ArrayList: Implementarea matricei redimensionabile a interfeței List
LinkedList: Implementarea listelor dublu legate a interfețelor List și Deque.

Operațiile care indexează lista vor parcurge lista de la început sau de la sfârșit, în funcție de care dintre acestea este mai aproape de indexul specificat.

Anjali Suman

1) Structura de date de bază

Prima diferență între ArrayList și LinkedList vine odată cu faptul că ArrayList este susținută de Array, în timp ce LinkedList este susținută de LinkedList. Acest lucru va duce la diferențe suplimentare în ceea ce privește performanța.

2) LinkedList implementează Deque

O altă diferență între ArrayList și LinkedList este faptul că, în afară de interfața List, LinkedList implementează și interfața Deque, care oferă operații de tip first in first out pentru add() și poll() și alte câteva funcții Deque. 3) Adăugarea de elemente în ArrayList Adăugarea unui element în ArrayList este o operațiune O(1) dacă nu declanșează redimensionarea array-ului, caz în care devine O(log(n)), Pe de altă parte, adăugarea unui element în LinkedList este o operațiune O(1), deoarece nu necesită nicio navigare.

4) Îndepărtarea unui element de pe o poziție

Pentru a elimina un element de la un anumit index, de exemplu, prin apelul remove(index), , ArrayList efectuează o operație de copiere, ceea ce face ca operația să fie aproape O(n), în timp ce LinkedList trebuie să se deplaseze până la acel punct, ceea ce face ca operația să fie, de asemenea, O(n/2), deoarece se poate deplasa din ambele direcții în funcție de proximitate.

5) Iterarea peste ArrayList sau LinkedList

Iterarea este operația O(n) atât pentru LinkedList, cât și pentru ArrayList, unde n este numărul unui element.

6) Preluarea unui element dintr-o poziție

Se utilizează get(index) este O(1) în ArrayList, în timp ce este O(n/2) în LinkedList, deoarece trebuie să se parcurgă până la acea intrare. Cu toate acestea, în notația Big O, O(n/2) este doar O(n), deoarece ignorăm constantele.

7) Memorie

LinkedList utilizează un obiect wrapper, Entry, care este o clasă imbricata statică pentru stocarea datelor și două noduri, next și previous, în timp ce ArrayList stochează doar datele în Array.

Prin urmare, necesarul de memorie pare mai mic în cazul ArrayList decât în cazul LinkedList, cu excepția cazului în care Array efectuează operația de redimensionare atunci când copiază conținutul dintr-un Array în altul.

Dacă Array este suficient de mare, poate ocupa foarte multă memorie în acel moment și poate declanșa colectarea gunoiului, ceea ce poate încetini timpul de răspuns.

Din toate diferențele de mai sus dintre ArrayList și LinkedList, se pare că ArrayList este o alegere mai bună decât LinkedList în aproape toate cazurile, cu excepția cazurilor în care se efectuează frecvent add() operațiune decât remove(), , sau get().

Este mai ușor să modificați o listă legată decât ArrayList, în special dacă adăugați sau eliminați elemente de la început sau sfârșit, deoarece lista legată păstrează în mod intern referințe ale acestor poziții și sunt accesibile în timp O(1).

Cu alte cuvinte, nu este nevoie să parcurgeți lista legată pentru a ajunge la poziția în care doriți să adăugați elemente; în acest caz, adăugarea devine o operațiune O(n). De exemplu, inserarea sau ștergerea unui element în mijlocul unei liste legate.

După părerea mea, utilizați ArrayList în loc de LinkedList pentru majoritatea scopurilor practice din Java.

Comentarii

  • Cred că acesta este cel mai bun răspuns al întregului grup de aici. Este precis și informativ. Aș sugera modificarea ultimului rând – la sfârșit adăugați „în afară de cozile de așteptare”, care sunt structuri foarte importante care nu au niciun sens pentru o listă legată. –  > Por Bill K.
Jose Martinez

Unul dintre testele pe care le-am văzut aici efectuează testul doar o singură dată. Dar ceea ce am observat este că trebuie să efectuați aceste teste de mai multe ori și, în cele din urmă, timpii lor vor converge. Practic, JVM-ul trebuie să se încălzească. Pentru cazul meu particular de utilizare aveam nevoie să adaug/eliminând elemente într-o listă care crește până la aproximativ 500 de elemente. În testele mele LinkedList a fost mai rapid, cu LinkedList ajungând la aproximativ 50 000 NS și ArrayList ajungând la aproximativ 90.000 NS… mai mult sau mai puțin. Vedeți codul de mai jos.

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

pietz

Ambele remove() și insert() au o eficiență în timp de execuție de O(n) atât pentru ArrayLists, cât și pentru LinkedLists. Cu toate acestea, motivul din spatele timpului de procesare liniară provine din două motive foarte diferite:

Într-o ArrayList, se ajunge la element în O(1), dar eliminarea sau inserarea efectivă a unui element face ca timpul de lucru să fie O(n), deoarece toate elementele următoare trebuie modificate.

Într-o LinkedList, este nevoie de O(n) pentru a ajunge efectiv la elementul dorit, deoarece trebuie să începem chiar de la început până când ajungem la indexul dorit. De fapt, eliminarea sau inserarea este constantă, deoarece trebuie să schimbăm doar 1 referință pentru remove() și 2 referințe pentru insert().

Care dintre cele două variante este mai rapidă pentru inserare și eliminare depinde de locul în care se întâmplă. Dacă ne aflăm mai aproape de început, LinkedList va fi mai rapidă, deoarece trebuie să trecem prin relativ puține elemente. Dacă ne aflăm mai aproape de sfârșit, o ArrayList va fi mai rapidă, deoarece ajungem acolo în timp constant și trebuie să modificăm doar cele câteva elemente rămase care o urmează. Dacă se face exact la mijloc, LinkedList-ul va fi mai rapid, deoarece parcurgerea a n elemente este mai rapidă decât mutarea a n valori.

Bonus: Deși nu există nicio modalitate de a face aceste două metode O(1) pentru o ArrayList, există o modalitate de a face acest lucru în LinkedLists. Să presupunem că dorim să parcurgem întreaga listă eliminând și inserând elemente pe parcurs. În mod normal, veți începe de la început pentru fiecare element folosind LinkedList, dar am putea, de asemenea, să „salvăm” elementul curent la care lucrăm cu ajutorul unui Iterator. Cu ajutorul Iteratorului, obținem o eficiență O(1) pentru remove() și insert() atunci când se lucrează într-o LinkedList. Acesta este singurul beneficiu de performanță de care am cunoștință în cazul în care o LinkedList este întotdeauna mai bună decât o ArrayList.

Randhawa

ArrayList extinde AbstractList și implementează interfața List. ArrayList este o matrice dinamică.
Se poate spune că a fost creat în principiu pentru a depăși dezavantajele array-urilor

Clasa LinkedList extinde AbstractSequentialList și implementează interfețele List, Deque și Queue.
Performanță
arraylist.get() este O(1), în timp ce linkedlist.get() este O(n)
arraylist.add() este O(1) și linkedlist.add() este 0(1)
arraylist.contains() este O(n) șilinkedlist.contains() este O(n)
arraylist.next() este O(1) și linkedlist.next() este O(1)
arraylist.remove() este O(n), în timp ce linkedlist.remove() este O(1)
În arraylist
iterator.remove() este O(n)
întrucât în cazul listei legate
iterator.remove()este O(1)

Sina Madani

Regula mea de bază este că dacă am nevoie de un Collection (adică nu trebuie să fie un List), atunci folosesc ArrayList dacă cunoașteți dimensiunea în avans, sau puteți cunoaște dimensiunea cu încredere, sau știți că nu va varia prea mult. Dacă aveți nevoie de acces aleatoriu (adică folosiți get(index)), evitați LinkedList. În principiu, utilizați LinkedList numai dacă nu aveți nevoie de acces indexat și dacă nu cunoașteți dimensiunea (aproximativă) a colecției pe care o alocați. De asemenea, dacă aveți de gând să efectuați multe adăugiri și eliminări (din nou prin Collection interfață), atunci LinkedList poate fi preferabilă.

Ilya Gazman

Când ar trebui să folosesc LinkedList? Atunci când lucrez cu stive, în principal, sau când lucrez cu tampoane.Când ar trebui să folosesc ArrayList? Numai atunci când lucrați cu indici, altfel puteți folosi HashTable cu lista legată, atunci veți obține:

Hash table + linked list

  • Acces prin cheie O(1),
  • Inserare după cheie O(1),
  • Eliminare prin cheie O(1)
  • și există un truc pentru a implementa RemoveAll / SetAll cu O(1) atunci când se utilizează versionarea

Pare a fi o soluție bună, și în majoritatea cazurilor este, însă trebuie să știți că:HashTable ocupă mult spațiu pe disc, așa că atunci când trebuie să gestionați o listă de 1.000.000 de elemente, acest lucru poate deveni un lucru important. Acest lucru se poate întâmpla în cazul implementărilor pe server, dar în cazul clienților este rar.

Aruncați o privire și la Red-Black-Tree

  • Acces aleatoriu Log(n),
  • Insert Log(n),
  • Eliminare Log(n)

Comentarii

  • Aș vrea să pot acorda mai mult de un -1: LinkedList oferă O(N) la toate inserțiile, eliminările și accesul aleatoriu, deoarece trebuie să parcurgeți lista pentru a ajunge mai întâi la punctul corect. De asemenea, s-ar putea să vă surprindă să aflați că hashmap/table utilizează array-uri de redimensionare la fel ca ArrayList și, având în vedere că cea mai comună utilizare a listelor este de a fi indexate cu un număr, utilizarea uneia dintre acestea în locul unei ArrayList este cea mai proastă idee. –  > Por Numeron.
  • @Numeron ai dreptate, nu a fost clar ce am răspuns. Într-adevăr, atunci când încercați să accesați o listă legată prin index, va fi O(n), însă eu m-am referit la inserarea în lista legată prin elemente. Atunci este O(1) și, de asemenea, interacționând peste toată lista, este la fel ca o listă de matrice. –  > Por Ilya Gazman.
Boris Fain

În primul rând, folosiți Vector în loc de ArrayList, deoarece puteți suprascrie metoda insureCapasity, în ArrayList este privată și adăugați 1,5 la dimensiunea matricei curente. https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-int-

în multe cazuri poate fi mai bine decât linkedList, lasList are un mare avantaj: introduceți date cu o frecvență mare, astfel încât dimensiunea listei se schimbă foarte repede și nu puteți aloca dimensiunea pentru numărul de elemente. În teorie, se poate obține o eroare de genul „memorie insuficientă”, dar în calculatoarele moderne există 16G și discuri de schimb, astfel încât, dacă lista are un număr de miliarde de elemente, se poate eșua, în comparație cu acum 15-20 de ani.

Comentarii

  • Vector este mai lent în comparație cu ArrayList deoarece Vector este sigur pentru fire de execuție. Cea mai bună practică este să nu se utilizeze un Vector decât dacă nu este nevoie de thread safety. Vector își dublează dimensiunea în mod implicit, ArrayList îi multiplică dimensiunea cu 3/2. Consultați:stackoverflow.com/questions/17471913/…. –  > Por Doga Oruc.