Kada „Java“ sistemoje naudoti „LinkedList“?

Aš visada turėjau vieną naudoti:

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

Aš naudoju sąsają kaip tipo pavadinimą perkeliamumui, taigi, kai aš užduodu tokius klausimus, galiu pakeisti savo kodą.

Kada turėtų būti naudojamas „ LinkedList per „ ArrayList ir atvirkščiai?

2684
27 нояб. nustatyti sdellysse 27 lapkritis 2008-11-27 04:36 '08, 4:36, 2008-11-27 04:36
@ 34 atsakymai
  • 1
  • 2

ArrayList su „ ArrayDeque pirmenybė teikiama daug didesniam naudojimo atvejų skaičiui nei „ LinkedList . Jei nesate tikri, pradėkite nuo „ ArrayList .


LinkedList ir „ ArrayList yra dvi skirtingos sąrašo sąsajos realizacijos. LinkedList įgyvendina su dvigubu susietu sąrašu. ArrayList įgyvendina dinamiškai besikeičiančiu masyvu.

Kaip ir standartinių susietų sąrašų ir masyvo operacijų atveju, skirtingi metodai turės skirtingus algoritminius režimus.

LinkedList<E>

  • get(int index) - O (n) (vidutinė n / 4 vertė)
  • add(E element) - O (1)
  • add(int index, E element) - O (n) (su vidutine n / 4 reikšme), bet O (1), kai index = 0 <yra pagrindinis „ LinkedList<E> privalumas LinkedList<E>
  • remove(int index) - O (n) (su n / 4 vidurkiu)
  • Iterator.remove() - O (1). <--- „ LinkedList<E> pagrindinis privalumas LinkedList<E>
  • ListIterator.add(E element) yra O (1) Tai vienas iš pagrindinių „ LinkedList<E> privalumų LinkedList<E>

Pastaba: daugeliui operacijų vidutiniškai trunka vidutiniškai n / 4 žingsniai, pastovus žingsnių skaičius (pvz., Indeksas = 0) ir n / 2 žingsniai blogiausiu atveju (sąrašo viduryje)

ArrayList<E>

  • get(int index) - O (1) <--- pagrindinis ArrayList<E> privalumas ArrayList<E>
  • add(E element) yra O (1) nuvertėjęs, bet O (n) yra blogiausias, nes masyvas turi būti pakeistas ir nukopijuotas.
  • add(int index, E element) yra O (n) (vidutiniškai n / 2 žingsniai)
  • remove(int index) yra O (n) (su n / 2 pakopų vidurkiu)
  • Iterator.remove() - O (n) (vidutiniškai n / 2 žingsniai)
  • ListIterator.add(E element) yra O (n) (su n / 2 pakopų vidurkiu)

Pastaba: daugeliui operacijų reikia vidutiniškai vidutinio žingsnių skaičiaus, pastovaus žingsnių skaičiaus geriausiu atveju (sąrašo pabaiga), n žingsnius blogiausiu atveju (sąrašo viršuje)

LinkedList<E> leidžia nustatyti arba pašalinti nuolatinį laiką naudojant iteratorius, bet tik nuoseklią prieigą prie elementų. Kitaip tariant, galite perkelti sąrašą į priekį arba atgal, tačiau pozicijos paieška sąraše užima laiko proporcingai sąrašo dydžiui. Javadocas sako: "Operacijos, kurios indeksuoja į sąrašą, susikurs sąrašą nuo pradžios arba pabaigos, priklausomai nuo to, kuris yra arčiau", todėl šie metodai yra vidutiniškai lygūs O (n) (n / 4 žingsniai), nors O (1) už index = 0 .

Kita vertus, „ ArrayList<E> leidžia greitai pasiekti atsitiktinę prieigą prie skaitymo, kad galėtumėte fiksuoti bet kurį elementą pastoviu laiku. Tačiau, norint padaryti atradimą arba užpildyti spragą, reikia pridėti arba pašalinti iš bet kurios vietos, išskyrus galą. Be to, jei pridėsite daugiau elementų nei bazinės matricos talpa, paskiriama nauja masyvas (1,5 karto didesnis už dydį), o senoji masyvas nukopijuojamas į naują, todėl pridedant prie „ ArrayList “ blogiausiu atveju yra O (n), bet pastovus vidutiniškai.

Todėl, priklausomai nuo operacijų, kurias ketinate atlikti, turite atitinkamai pasirinkti įgyvendinimą. Iteracija bet kokiuose sąrašuose yra beveik vienodai pigus. („ ArrayList persiuntimas ArrayList techniškai greitesnis, tačiau, jei jūs nedarote ką nors iš tikrųjų jautrios, nereikia jaudintis - jie abu yra konstantos.)

Pagrindiniai „ LinkedList naudojimo privalumai atsiranda tada, kai esami iteratoriai pakartotinai naudojami elementams įterpti ir ištrinti. Tada šias operacijas galima atlikti O (1) keičiant tik vietinį sąrašą. Masyvų sąraše likusi masyvo dalis turėtų būti perkelta (t. Y. Nukopijuota). Kita vertus, paieška „ LinkedList reiškia šias nuorodas, esančias O (n) (n / 2 pakopose) blogiausiu atveju, o „ ArrayList norima padėtis gali būti matematiškai apskaičiuojama ir prieinama O (1).

Kitas „ LinkedList naudojimo privalumas atsiranda, kai įtraukiate arba pašalinate iš sąrašo galvutės, nes šios operacijos yra O (1), o O (n) - „ ArrayList . Atkreipkite dėmesį, kad „ ArrayDeque gali būti tinkama „ LinkedList alternatyva pridėti ir pašalinti iš galvos, bet tai nėra List .

Be to, jei turite didelius sąrašus, atminkite, kad atminties naudojimas taip pat skiriasi. Kiekvienas „ LinkedList elementas turi daugiau pridėtinės vertės, nes taip pat saugomi rodikliai į kitą ir ankstesnius elementus. ArrayLists neturi šių pridėtinių išlaidų. Tačiau „ ArrayLists užima tiek daug atminties, kiek skiriama talpa, nepriklausomai nuo to, ar elementai buvo faktiškai pridėti.

Pradinis numatytojo „ ArrayList pajėgumas ArrayList gana mažas (10 iš „Java 1.4“ - 1.8). Bet kadangi bazės diegimas yra masyvas, masyvas turi būti pakeistas, jei pridedate daug elementų. Kad išvengtumėte didelių dydžių dydžio keitimo, kai žinote, kad ketinate pridėti daug elementų, ArrayList su didesniu pradiniu pajėgumu.

2957
27 нояб. Atsakymą pateikė Jonathan Tran 27 lapkritis. 2008-11-27 04:49 '08 at 4:49 2008-11-27 04:49

Iki šiol, atrodo, kad niekas neatsižvelgė į kiekvieno iš šių sąrašų atminties dydį, išskyrus bendrą nuomonę, kad „ LinkedList „daug daugiau“ nei „ ArrayList todėl šiek tiek suskaičiuojau, kad būtų galima parodyti, kaip tiksliai abu sąrašai užima N tuščias nuorodas,

Kadangi jų santykinėse sistemose nuorodos yra 32 arba 64 bitų (net jei jos yra nulinės), įtraukiau 4 duomenų rinkinius 32 ir 64 bitų „ LinkedLists ir „ ArrayLists .

PastabaArrayList eilutėse rodomi dydžiai skirti sutrumpintiems sąrašams. Praktiškai „ ArrayList atsarginių kopijų talpa paprastai ArrayList didesnė už dabartinį elementų skaičių.

2 pastaba: („BeeOnRope“ dėka) Kadangi „CompressedOops“ dabar yra naudojamas pagal JDK6 ir aukštesnius vidus, 64 bitų kompiuterių šios reikšmės dažniausiai atitiks jų 32 bitų atitikmenis, nebent jūs, be abejo, jį išjungiate.


border=0


border=0

Rezultatas aiškiai rodo, kad „ LinkedList daug daugiau nei „ ArrayList , ypač su labai daug elementų. Jei atmintis yra veiksnys, būkite atokiau nuo „ LinkedLists .

Naudojamos formulės, leiskite man žinoti, ar padariau kažką neteisingo, ir aš jį išsprendžiu. "b" yra 4 arba 8 32 bitų arba 64 bitų sistemoms, o "n" - elementų skaičius. Atkreipkite dėmesį, kad modų priežastis yra ta, kad visi java objektai užims 8 baitų erdvės daugumą, nepriklausomai nuo to, ar jie visi naudojami, ar ne.

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

556
06 окт. Atsakymą pateikė „ Numeron“ spalio 06 d. 2011-10-06 09:46 '11 at 9:46 2011-10-06 09:46

ArrayList yra tai, ko norite. LinkedList beveik visada yra klaida (našumas).

Kodėl „ LinkedList sucks:

  • Jis naudoja daug mažų atminties objektų ir todėl daro įtaką proceso veikimui.
  • Daugelis smulkių objektų yra blogi dėl talpyklos lokalizavimo.
  • Bet kuriai indeksuotai operacijai reikia apėjimo, ty jis turi O (n) našumą. Tai nėra akivaizdu šaltinio kode, kuris veda į O (n) algoritmus lėčiau nei naudojant „ ArrayList .
  • Gerų rezultatų pasiekimas yra sudėtingas.
  • Net jei didelės produkcijos našumas yra toks pat, kaip ir „ ArrayList , bet kuriuo atveju jis greičiausiai bus daug lėtesnis.
  • Labai erzina pamatyti šaltinį „ LinkedList “, nes tai tikriausiai yra netinkamas pasirinkimas.
208
27 нояб. Atsakymą pateikė Tom Hawtin - tackline lapkričio 27 d 2008-11-27 17:20 '08, 17:20, 2008-11-27 17:20

Kaip asmuo, kuris jau dešimtmetį plėtoja labai didelių SOA žiniatinklio paslaugų veiklos rezultatus, norėčiau, kad „LinkedList“ būtų per „ArrayList“. Nors „LinkedList“ fiksuotas dažnių juostos plotis yra blogesnis ir todėl gali būti perkamos daugiau aparatūros, „ArrayList“ elgesys spaudimu gali sukelti klasterio taikomųjų programų išplėtimą beveik sinchroniškai, o dideli matricų dydžiai gali sukelti atsakymo trūkumą programoje ir atsijungus nuo spaudimo, kuris yra pražūtingas elgesys.

Be to, taikomojoje programoje galite gauti didesnį dažnių juostos plotį nuo numatytojo šiukšlių surinkėjo, bet kai gausite „Java“ programą su 10 GB krūva, galite užblokuoti programą 25 sekundes per visą „GC“, kuris sukelia laiko trukmę ir avarijas SOA programose ir pašalina jūsų SLA, jei taip nutinka pernelyg dažnai. Nors CMS surinkėjas sunaudoja daugiau išteklių ir nepasiekia to paties žaliavinio dažnių juostos pločio, tai yra daug geresnis pasirinkimas, nes jis turi labiau nuspėjamą ir mažiau latentinį.

„ArrayList“ yra tik geriausias pasirinkimas, jei visi turite omenyje pralaidumą ir galite ignoruoti latenciją. Savo darbo metu negaliu ignoruoti blogiausių vėlavimų.

130
01 янв. atsakymas duotas lamont 01 jan. 2011-01-01 23:23 '11, 23:23, 2011-01-01 23:23
 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) 

Algoritmai: Big-Oh Notation

„ArrayLists“ yra tinkamas rašyti kartą skaitomiems ar daugeliui priedų, bet ne geras, kai pridedate / ištrinate prieš tai viduryje.

112
08 апр. Atsakymas, kurį pateikė Michael Munsey Bal 08 2010-04-08 23:33 '10, 11:33, 2010-04-08 23:33

Taip, aš žinau, tai yra senas klausimas, bet aš išleisiu du centus:

„LinkedList“ beveik visada yra netinkamas pasirinkimas. Yra keletas labai specifinių algoritmų, kuriems reikalinga „LinkedList“ nuoroda, tačiau jie yra labai, labai reti, ir algoritmas paprastai priklausys nuo to, ar „LinkedList“ sugebės įterpti ir ištrinti elementus sąrašo viduryje gana greitai, kai jūs einate ten su „ListIterator“.

Yra vienas bendras naudojimo atvejis, kai „LinkedList“ viršija „ArrayList“: eilę. Tačiau jei jūsų tikslas yra našumas, o ne „LinkedList“, turėtumėte apsvarstyti galimybę naudoti „ArrayBlockingQueue“ (jei galite iš anksto nustatyti viršutinę savo eilės dydžio ribą ir galite leisti priskirti visą atmintį), arba tai yra „CircularArrayList“ įgyvendinimas . (Taip, tai yra nuo 2001 m., Taigi jums reikės apibendrinti, bet aš turėjau palyginamus veiklos rodiklius su straipsniu, kuris pateikiamas straipsnyje tik neseniai JVM)

96
19 мая '09 в 14:21 2009-05-19 14:21 Atsakymą davė Daniel Martin May 19 '09, 14:21, 2009-05-19 14:21

Tai yra veiksmingumo klausimas. LinkedList greitai prideda ir pašalina elementus, bet lėtai pasiekia tam tikrą elementą. ArrayList greitai pasiekia prieigą prie tam tikro elemento, tačiau gali būti lėtas pridėti prie bet kurio galo ir ypač lėtai pašalinti viduryje.

Array vs ArrayList vs LinkedList vs Vector yra detalesnis, kaip ir susietas sąrašas .

51
27 нояб. atsakymas yra dgtized 27 lapkričio. 2008-11-27 04:39 '08 at 4:39 2008-11-27 04:39

Teisingas ar neteisingas: atlikite testą vietoje ir nuspręskite sau!

LinkedList spartesnis keitimas / trynimas nei „ ArrayList .

ArrayList , palaikomas „ Array , kuri turėtų būti dvigubai didesnė, dar blogesnė didelės apimties programoje.

Žemiau pateikiamas kiekvienos operacijos testo rezultatas. Citavimas pateikiamas nanosekundėmis.


 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 

Čia yra kodas:

 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); } } 
50
22 сент. atsakymas pateiktas Ash 22 Sep. 2011-09-22 01:59 '11 at 1:59 2011-09-22 01:59

ArrayList iš esmės yra masyvas. LinkedList “ įgyvendinamas kaip dvigubas susietas sąrašas.

get gana aišku. O (1) „ ArrayList , nes „ ArrayList leidžia atsitiktinę prieigą naudojant indeksą. O (n) „ LinkedList , nes pirmiausia turi rasti indeksą. Pastaba Yra skirtingų add ir remove versijų.

LinkedList prideda ir pašalina greičiau, tačiau lėčiau paaiškėja. Trumpai tariant, „ LinkedList turėtų būti teikiama pirmenybė, jei:

  1. ne daug atsitiktinio prieigos elemento
  2. Yra daug pridėti / ištrinti operacijų.

=== ArrayList ===

  • pridėti (E e)
    • iki galo pridėkite „ArrayList“
    • reikia pakeisti atminties dydį.
    • O (n) dar blogiau, O (1) amortizuojama
  • pridėti (int indeksas, elementas E)
    • pridėti prie konkrečios indekso pozicijos
    • reikia kompensuoti ir galimas atminties dydžio keitimo išlaidas
    • Įjungta)
  • pašalinti (int indeksas)
    • ištrinkite nurodytą elementą
    • reikia kompensuoti ir galimas atminties dydžio keitimo išlaidas
    • Įjungta)
  • pašalinti (Objektas o)
    • pašalinkite pirmąjį nurodyto elemento atsiradimą iš šio sąrašo
    • pirmiausia turite ieškoti elemento ir tada perkelti galimas atminties dydžio keitimo išlaidas
    • Įjungta)

=== LinkedList ===

  • pridėti (E e)

    • pridėti prie sąrašo pabaigos
    • O (1)
  • pridėti (int indeksas, elementas E)

    • įdėkite į nurodytą padėtį
    • pirmiausia turite rasti poziciją
    • Įjungta)
  • Ištrinti ()
    • ištrinti pirmąjį sąrašo elementą
    • O (1)
  • pašalinti (int indeksas)
    • ištrinti elementą su nurodytu indeksu
    • pirmiausia turite rasti elementą
    • Įjungta)
  • pašalinti (Objektas o)
    • pašalinti pirmąjį nurodyto elemento įvykį
    • pirmiausia turite rasti elementą
    • Įjungta)

Čia yra paveikslėlis iš programcreek.com ( add ir remove yra pirmasis tipas, t. Y. Elemento pridėjimas sąrašo pabaigoje ir elemento pašalinimas tam tikroje sąrašo vietoje.):

2019

42
21 апр. atsakymas pateiktas Ryan 21 Bal 2013-04-21 03:03 '13, 3:03, 2013-04-21 03:03

1) Paieška: paieškos operacija „ArrayList“ yra gana greita, palyginti su paieškos operacija „LinkedList“. gauti (int indeksas) ArrayList yra O (1), o LinkedList yra O (n).

Priežastis: „ ArrayList“ palaiko indekso sistemą, skirtą jos elementams, nes ji netiesiogiai naudoja masyvo duomenų struktūrą, kuri leidžia greičiau rasti elementą sąraše. Kita vertus, „LinkedList“ įgyvendina dvigubą susietą sąrašą, kuriam reikalingi visi elementai, kad būtų ieškoma elemento.

2) Ištrynimas: „ LinkedList“ ištrynimo operacija suteikia O (1) našumą, o „ArrayList“ pateikia kintamąjį našumą: O (n) blogiausiu atveju (ištrinant pirmąjį elementą) ir O (1) geriausiu atveju (ištrinant paskutinį elementą) ,

Išvada: „ LinkedList“ elemento pašalinimas yra greitesnis nei „ArrayList“.

Priežastis Kiekvienas „LinkedLists“ elementas palaiko du rodykles (adresus), nurodančius abu gretimus elementus sąraše. Todėl ištrynimui reikia tik keisti rodyklės vietą dviejuose naikinamo mazgo kaimyniniuose mazguose (elementuose). „ArrayList“ sistemoje visi elementai turi būti perkelti, kad užpildytų ištrinto elemento sukurtą erdvę.

3) Įterpti našumą: LinkedList pridedamas metodas suteikia O (1) našumą, o „ArrayList“ - O (n) blogiausiu atveju. Priežastis yra tokia pati, kaip ir ištrynimui.

4) Atminties pridėtinės vertės: „ ArrayList“ palaiko indeksus ir elementų duomenis, o „LinkedList“ palaiko elementų duomenis ir du rodykles kaimyniniams mazgams, todėl „LinkedList“ atminties sąnaudos yra palyginti didelės.

Tarp šių klasių yra keletas panašumų , kurie yra tokie:

Tiek „ArrayList“, tiek „LinkedList“ yra „Sąsajos“ sąsajos įgyvendinimas. Abi jos palaiko elementų įterpimo tvarką, o tai reiškia, kad, rodant „ArrayList“ ir „LinkedList“ elementus, rezultatų rinkinys turi tą pačią tvarką, kurioje elementai buvo įtraukti į sąrašą. Abi šios klasės nėra sinchronizuotos ir gali būti sinchronizuotos aiškiai naudojant „Kolekcijos“ sinchronizuotą sąrašą. Итератор и listIterator, возвращаемые этими классами, являются неудачными (если список структурно изменен в любое время после создания итератора, любым способом, кроме как через собственные методы удаления или добавления итераторов, итератор будет вызывать исключение ConcurrentModificationException).

Когда использовать LinkedList и когда использовать ArrayList?