Când să utilizați o listă legată în locul unei liste de matrice/ listă de matrice? (Programare, Array-Uri, Lista, Arraylist, Listă Legată)

fără față1_14 a intrebat.

Folosesc o mulțime de liste și array-uri, dar încă nu am întâlnit un scenariu în care lista de array-uri să nu poată fi folosită la fel de ușor, dacă nu chiar mai ușor decât lista legată. Speram ca cineva să-mi dea câteva exemple de situații în care lista legată este considerabil mai bună.

Comentarii

  • În Java, ArrayList și LinkedList utilizează exact același cod, cu excepția constructorului. „Lista de array… folosită la fel de ușor sau mai ușor decât lista legată” nu are sens. Vă rugăm să oferiți un exemplu în care o ArrayList să fie „mai ușoară” decât o LinkedList. –  > Por S.Lott.
  • Verificați și acest lucru, stackoverflow.com/questions/322715/… –  > Por NoNaMe.
  • Posibil duplicat al Array versus Linked-List –  > Por Hawkeye Parker.
  • S.Lott Acest lucru nu este adevărat. ArrayList-ul Java este un înveliș în jurul unui Array, la care au fost adăugate câteva funcții de utilitate. O listă legată este, evident, o listă legată. developer.classpath.org/doc/java/util/ArrayList-source.html –  > Por kingfrito_5005.
15 răspunsuri
Lamar

Listele legate sunt preferabile în locul array-urilor atunci când:

  1. aveți nevoie de inserții/eliminări în timp constant din listă (cum ar fi în calculul în timp real, unde predictibilitatea timpului este absolut critică)

  2. nu se știe câte elemente vor fi în listă. În cazul tablourilor, este posibil să fie nevoie să declarați din nou și să copiați memoria dacă tabloul crește prea mult.

  3. nu aveți nevoie de acces aleatoriu la niciun element.

  4. doriți să puteți insera elemente în mijlocul listei (cum ar fi o coadă prioritară).

Array-urile sunt preferabile atunci când:

  1. aveți nevoie de acces indexat/aleatoriu la elemente

  2. cunoașteți din timp numărul de elemente din matrice, astfel încât să puteți aloca cantitatea corectă de memorie pentru matrice.

  3. aveți nevoie de rapiditate atunci când iterați prin toate elementele în succesiune. Puteți utiliza matematica pointerilor în matrice pentru a accesa fiecare element, în timp ce trebuie să căutați nodul pe baza pointerului pentru fiecare element din lista legată, ceea ce poate duce la erori de pagină, ceea ce poate duce la pierderi de performanță.

  4. memoria este o problemă. Array-urile pline ocupă mai puțină memorie decât listele legate. Fiecare element din matrice reprezintă doar datele. Fiecare nod al listei legate necesită datele, precum și unul (sau mai mulți) pointeri către celelalte elemente din lista legată.

Listele de array-uri (precum cele din .Net) vă oferă avantajele array-urilor, dar alocă resursele în mod dinamic pentru dumneavoastră, astfel încât nu trebuie să vă faceți prea multe griji cu privire la dimensiunea listei și puteți șterge elemente la orice index fără niciun efort sau reîmpărțire a elementelor. Din punct de vedere al performanței, listele de matrice sunt mai lente decât matricele brute.

Comentarii

  • Un început bun, dar acest lucru omite lucruri importante: listele acceptă partajarea structurii, array-urile sunt mai dense și au o mai bună localitate. –  > Por Darius Bacon.
  • Practic, diferența de performanță între listele de matrice și array-uri este neglijabilă. Acest lucru presupune că se compară comparabil și, de exemplu, atunci când cunoașteți dimensiunea în prealabil, îi spuneți arraylistului despre aceasta. –  > Por svick.
  • 45

  • De când LinkedList are O(1) inserții/ștergeri (la care presupun că vă referiți când spuneți că inserții/ștergeri în timp constant)? Inserarea de lucruri în mijlocul unei LinkedList este întotdeauna O(n) –  > Por Pacerier.
  • 32

  • Listele legate au inserții O(1) dacă se întâmplă să vă aflați deja în locul în care se face inserția (prin intermediul unui iterator). Totuși, nu întotdeauna. –  > Por Adam.
  • Folosirea listelor legate pentru cozile de așteptare prioritare este o idee foarte proastă. Grămezile dinamice susținute de tablouri permit inserții amortizate O(lg n) și ștergeri logaritmice în cel mai rău caz și se numără printre cele mai rapide structuri practice de coadă de prioritate. –  > Por Fred Foo.
Dustin

Array-urile au acces aleatoriu O(1), dar sunt foarte costisitoare pentru a adăuga sau a șterge lucruri.

Listele legate sunt foarte ieftine pentru a adăuga sau elimina elemente oriunde și pentru a itera, dar accesul aleatoriu este O(n).

Comentarii

  • Îndepărtarea elementelor de la capătul unui array este în timp continuu, la fel ca și inserarea/eliminarea elementelor din fie capăt al unei liste legate. La mijloc … nu prea mult pentru niciuna dintre ele. –  > Por Joey.
  • @Joey, inserția/ștergerea la sfârșitul unei liste legate nu este O(n)? Dacă nu ești deja poziționat la penultima legătură, tot vei avea nevoie de O(n) pași pentru a găsi ultimul element, nu? –  > Por Alex Moore-Niemi.
  • @AlexMoore-Niemi: Pentru o listă cu o singură legătură, da. Dar multe au legături înainte și înapoi și, prin urmare, păstrează pointeri la fiecare capăt. –  > Por Joey.
  • Dacă aveți o listă dublu legată, va trebui să faceți căutări înainte și înapoi, cu excepția cazului în care LL are valori ordonate… și totuși cel mai rău scenariu este O(n) –  > Por securecurve.
  • „Listele legate sunt foarte ieftine pentru a adăuga sau elimina elemente oriunde și pentru a itera” nu este în întregime adevărat. Dacă vreau să elimin un element care se află în mijlocul unei liste legate, va trebui să iteratez de la început până când ajung la acel element din listă. Este un timp O(n/2), unde n = numărul de elemente din listă. Din răspunsul dvs. se pare că sugerați că este un timp constant O(1), așa cum este în matrice. Adăugarea/eliminarea din nodul principal/radical al unei liste legate este în timp constant. –  > Por Yawar Murtaza.
Vpn_talent
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)

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

  • Rețineți că O(1) pentru inserarea după un element într-o listă legată este adevărată numai dacă aveți deja pointerul la elementul după care trebuie să inserați noul nod. În caz contrar, va trebui să parcurgeți lista legată până când veți găsi poziția corectă, ceea ce ar fi O(N). –  > Por Riccardo.
Jay Conrod

Pentru a adăuga la celelalte răspunsuri, majoritatea implementărilor de liste de matrice rezervă o capacitate suplimentară la sfârșitul listei, astfel încât să se poată adăuga noi elemente la sfârșitul listei în timp O(1). Atunci când capacitatea unei liste de matrice este depășită, o nouă matrice, mai mare, este alocată intern, iar toate elementele vechi sunt copiate. De obicei, noua matrice are o dimensiune dublă față de cea veche. Aceasta înseamnă că în medieadăugarea de noi elemente la sfârșitul unei liste de tablouri este o operațiune O(1) în aceste implementări. Prin urmare, chiar dacă nu cunoașteți în avans numărul de elemente, o listă de tablouri poate fi mai rapidă decât o listă legată pentru adăugarea de elemente, atâta timp cât le adăugați la sfârșit. Evident, inserarea de noi elemente în locații arbitrare într-o listă de tablouri este în continuare o operațiune O(n).

De asemenea, accesarea elementelor dintr-o listă de matrice este mai rapidă decât o listă legată, chiar dacă accesările sunt secvențiale. Acest lucru se datorează faptului că elementele din matrice sunt stocate în memorie contiguă și pot fi stocate cu ușurință în memoria cache. Nodurile din listele legate pot fi împrăștiate pe mai multe pagini diferite.

V-aș recomanda să folosiți o listă legată numai dacă știți că veți introduce sau șterge elemente în locații arbitrare. Listele Array vor fi mai rapide pentru aproape orice altceva.

Comentarii

  • În plus, puteți, de asemenea, să implementați listele legate (în sensul Abstract Data Type) folosind array-uri dinamice. În acest fel, puteți profita de memoria cache a computerului, având în același timp inserții și ștergeri amortizate în timp constant la capul listei și, de asemenea, inserții și ștergeri amortizate în timp constant la mijlocul listei atunci când aveți indicele elementului după care trebuie făcută inserția sau indicele elementului de șters (nu este nevoie de deplasări/dezplasări). O bună referință în acest sens este CLRS 10.3. –  > Por Domenico De Felice.
Uri

Avantajul listelor apare dacă aveți nevoie să inserați elemente la mijloc și nu doriți să începeți să redimensionați array-ul și să schimbați lucrurile.

Aveți dreptate în sensul că, de obicei, acesta nu este cazul. Am avut câteva cazuri foarte specifice de acest gen, dar nu prea multe.

Comentarii

  • Deplasarea și redimensionarea matricei este ceea ce se întâmplă de fapt atunci când faceți inversiuni la mijloc. Veți avea nevoie de deplasare fără redimensionare doar dacă nu atingeți limita de amortizare. –  > Por securecurve.
Harleen

Totul depinde de tipul de operațiune pe care o efectuați în timpul iterației, toate structurile de date au un compromis între timp și memorie și, în funcție de nevoile noastre, ar trebui să alegem DS corect. Astfel, există unele cazuri în care LinkedList este mai rapid decât array-ul și invers. Luați în considerare cele trei operații de bază asupra structurilor de date.

  • Căutarea

Deoarece matricea este o structură de date bazată pe indici, căutarea array.get(index) va dura O(1), în timp ce Linkedlist nu este o DS cu indici, astfel încât va trebui să parcurgeți până la index, unde index <=n , n este dimensiunea listei legate, astfel încât matricea este mai rapidă decât lista legată atunci când accesul la elemente este aleatoriu.

Î.Deci, care este frumusețea din spatele acestui lucru?

Deoarece array-urile sunt blocuri de memorie contiguă, bucăți mari din ele vor fi încărcate în memoria cache la prima accesare, ceea ce face ca accesul la elementele rămase din array să fie relativ rapid, iar pe măsură ce accesăm elementele din array, crește și localitatea referințelor, astfel încât sunt mai puține ratări de captură, localitatea cache-ului se referă la faptul că operațiile se află în memoria cache și se execută mult mai rapid decât în memorie, în principiu, în array maximizăm șansele ca accesul secvențial la elemente să fie în memoria cache. În timp ce listele legate nu se află neapărat în blocuri contigue de memorie, nu există nicio garanție că elementele care apar secvențial în listă sunt de fapt aranjate unul lângă altul în memorie, ceea ce înseamnă mai puține accesări ale cache-ului, de exemplu, mai multe ratări ale cache-ului, deoarece trebuie să citim din memorie pentru fiecare accesare a unui element din lista legată, ceea ce crește timpul necesar pentru accesarea acestora și deteriorează performanța, astfel încât, dacă efectuăm mai multe operații de acces aleatoriu, cum ar fi căutarea, array-ul va fi mai rapid, după cum se explică mai jos.

  • Inserție

Acest lucru este ușor și rapid în LinkedList, deoarece inserarea este o operațiune O(1) în LinkedList (în Java) în comparație cu array-ul, luați în considerare cazul în care array-ul este plin, trebuie să copiem conținutul în noul array dacă array-ul este plin, ceea ce face ca inserarea unui element în ArrayList să fie O(n) în cel mai rău caz, în timp ce ArrayList trebuie, de asemenea, să își actualizeze indexul dacă se inserează ceva oriunde, cu excepția capătului array-ului, în cazul listei legate nu trebuie să o redimensionăm, ci doar să actualizăm indicatorii.

  • Ștergere

Funcționează la fel ca inserțiile și este mai bine în LinkedList decât în array.

Praveen Kumar Verma

Acestea sunt cele mai des utilizate implementări ale colecțiilor.

ArrayList:

  • inserare/ștergere la sfârșit în general O(1) în cel mai rău caz O(n)

  • inserare/ștergere la mijloc O(n)

  • recuperarea oricărei poziții O(1)

LinkedList:

  • inserare/eliminare în orice poziție O(1) (rețineți dacă aveți o referință la element).

  • recuperarea în mijloc O(n)

  • extragerea primului sau ultimului element O(1)

Vector: nu-l utilizați. Este o implementare veche, similară cu ArrayList, dar cu toate metodele sincronizate. Nu este abordarea corectă pentru o listă partajată într-un mediu multithreading.

HashMap

inserare/eliminare/recuperare după cheie în O(1)

TreeSetinserați/eliminați/conține în O(log N)

HashSetinsert/remove/contains/size în O(1)

user3150186

În realitate, localitatea memoriei are o influență uriașă asupra performanței în procesarea reală.

Utilizarea sporită a fluxului de discuri în procesarea „big data” față de accesul aleatoriu arată cum structurarea aplicației în funcție de aceasta poate îmbunătăți dramatic performanța la scară mare.

Dacă există vreo modalitate de a accesa secvențial o matrice, aceasta este de departe cea mai performantă. Proiectarea cu acest obiectiv ar trebui să fie luată în considerare cel puțin dacă performanța este importantă.

Raghu

Hmm, Arraylist poate fi folosit în cazuri precum cele de mai jos, cred:

  1. nu sunteți sigur de câte elemente vor fi prezente
  2. dar trebuie să accesați toate elementele aleatoriu prin indexare.

De exemplu, trebuie să importați și să accesați toate elementele dintr-o listă de contacte (a cărei dimensiune nu o cunoașteți)

gizgok

Utilizați lista legată pentru Radix Sort peste array-uri și pentru operații polinomiale.

Avanish Kumar

1) 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, dacă există o cerință de adăugare și ștergere frecventă în aplicație, LinkedList este cea mai bună alegere.

2) Operațiunile de căutare (metoda get) 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.

Curious_goat

Cred că principala diferență este dacă aveți nevoie în mod frecvent să inserați sau să eliminați lucruri din partea de sus a listei.

În cazul unui array, dacă eliminați ceva din partea de sus a listei, atunci complexitatea este o(n), deoarece toți indicii elementelor array-ului vor trebui să se schimbe.

În cazul unei liste legate, complexitatea este o(1), deoarece trebuie doar să creați nodul, să realocați capul și să atribuiți referința la următorul ca fiind capul anterior.

Atunci când se inserează sau se elimină frecvent la sfârșitul listei, sunt preferabile array-urile, deoarece complexitatea va fi o(1), nefiind necesară reindexarea, dar pentru o listă legată va fi o(n) deoarece trebuie să treceți de la cap la ultimul nod.

Cred că căutarea atât în listele legate, cât și în array-uri va fi o(log n), deoarece veți utiliza probabil o căutare binară.

Emil Albert

Am făcut câteva analize comparative și am constatat că clasa list este de fapt mai rapidă decât LinkedList pentru inserarea aleatorie:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Este nevoie de 900 ms pentru lista legată și de 100 ms pentru clasa listă.

Creează liste de numere întregi ulterioare. Fiecare nou număr întreg este inserat după un număr aleatoriu care se află deja în listă. poate că clasa List folosește ceva mai bun decât un simplu array.

Comentarii

  • List este o interfață, nu o clasă –  > Por borgmater.
photonic

Array-urile, de departe, sunt cele mai utilizate structuri de date. Cu toate acestea, listele legate se dovedesc utile în felul lor unic, acolo unde array-urile sunt stângace – sau cel puțin costisitoare.

Listele legate sunt utile pentru a implementa stive și cozi de așteptare în situațiile în care dimensiunea lor este supusă variației. Fiecare nod din lista legată poate fi împins sau scos fără a perturba majoritatea nodurilor. Același lucru este valabil și pentru inserarea/eliminarea nodurilor undeva la mijloc. În matrici, însă, toate elementele trebuie să fie deplasate, ceea ce reprezintă o sarcină costisitoare din punct de vedere al timpului de execuție.

Arborii binari și arborii de căutare binari, tabelele hash și tries sunt câteva dintre structurile de date în care – cel puțin în C – aveți nevoie de listele legate ca ingredient fundamental pentru construirea lor.

Cu toate acestea, listele legate ar trebui evitate în situațiile în care se așteaptă să se poată apela orice element arbitrar prin indexul său.

Rohit Goynar

Un răspuns simplu la întrebare poate fi dat folosind aceste puncte:

  1. Array-urile se utilizează atunci când este necesară o colecție de elemente de date de tip similar. În schimb, lista legată este o colecție de elemente legate de date de tip mixt, cunoscute sub numele de noduri.

  2. În cadrul unei matrice, se poate vizita orice element în timp O(1). În schimb, în cazul unei liste legate, ar trebui să parcurgem întreaga listă legată de la cap până la nodul necesar, ceea ce necesită un timp O(n).

  3. În cazul tablourilor, trebuie declarată inițial o anumită dimensiune. Dar listele legate au o dimensiune dinamică.