Diferența dintre lista matrice și lista asociată Diferența dintre
Cum sunt stocate datele?
Lista array și lista legată sunt termeni obișnuiți atunci când vine vorba de stocarea și recuperarea datelor. Deși există o mulțime de dispozitive de stocare, în cele din urmă depind de mecanismul de stocare. Aceste două mecanisme de stocare plasează datele în dispozitivele de stocare și le recuperează atunci când este necesar. Să aruncăm o privire la modul în care stochează datele în memoria lor. Lista Array utilizează o stocare secvențială, iar fragmentele de date sunt stocate una după alta. Aceasta este probabil o formă mai simplă de depozitare - evită confuzia. Da, putem prelua următorul element sau date din următoarea locație de memorie a listei de matrice; cu toate acestea, acesta este stocat cu ajutorul indicatorilor din lista Legat. Aici avem nevoie de două locații de memorie pentru stocare - una pentru date, cealaltă pentru pointer. Un pointer se adresează locației de memorie a următoarelor date. Putem să înțelegem cu ușurință că lista conectată nu stochează niciodată date secvențial; mai degrabă, utilizează un mecanism de stocare aleatoare. Indicatorii sunt elementele cheie în localizarea locațiilor de date din memorie.
Listă dinamică și listă asociată
Am discutat deja modul în care ambele mecanisme de stocare pun datele și putem da un termen "matrice dinamică" pentru schema de stocare internă a listei Array. Pur și simplu pune piesele de date unul după altul - de exemplu numele - în timp ce lista legată utilizează o listă internă cu ajutorul pointerilor pentru a urmări următorul element. Prin urmare, folosește o listă internă, cum ar fi o listă unică sau dublă, pentru a ne arăta datele următoare.
- <->Utilizare memorie
În lista Array se stochează numai datele reale, avem nevoie doar de spațiu pentru datele pe care le stocăm. În schimb, în lista Legătură, folosim și indicatori. Prin urmare, sunt necesare două locații de memorie și putem spune că lista conectată consumă mai multă memorie decât lista Array. O parte avantajoasă a listei asociate este că nu necesită niciodată locații de memorie permanente pentru a stoca datele noastre, spre deosebire de lista Array. Indicatorii sunt capabili să mențină poziția următoarei locații de date și putem folosi chiar sloturi de memorie mai mici care nu sunt continue. Când vine vorba de utilizarea memoriei, pointerii joacă rolul principal în lista Legată, la fel și eficacitatea acestora.
Mărimea listei de matrice inițiale și a listei asociate
Cu lista Array, chiar și o listă goală necesită o dimensiune de 10, dar cu o listă legată, nu avem nevoie de un astfel de spațiu imens. Putem crea o listă goală asociată cu o dimensiune de 0. Mai târziu, putem mări dimensiunea după cum este necesar.
Recuperarea datelor
Recuperarea datelor este mai simplă în lista Array, deoarece stochează secvențial. Tot ce face este identificarea primei locații de date; de acolo, următoarea locație este accesată secvențial pentru a prelua restul.Se calculează ca prima poziție de date + 'n', unde 'n' este ordinea datelor din lista Array. Lista legată se referă la pointerul inițial pentru a găsi prima locație de date și de aici se referă la pointerul asociat cu fiecare dată pentru a găsi următoarea locație de date. Procesul de recuperare depinde în principal de indicii de aici și ne arată în mod eficient următoarea locație a datelor.
Sfârșitul datelor
Lista Array utilizează o valoare nulă pentru a marca sfârșitul datelor, în timp ce lista asociată folosește un pointer nul în acest scop. Imediat ce sistemul recunoaște date nul, lista Array oprește următoarea extragere de date. În mod similar, indicatorul nulic oprește sistemul să treacă la următoarea extragere de date.
Traversal inversat
Lista legată ne permite să traversăm în direcția inversă cu ajutorul descendingiterator (). Cu toate acestea, nu avem o astfel de facilitate într-o listă Array - traversarea inversă devine o problemă aici.
Sintaxa
Să ne uităm la sintaxa Java a ambelor mecanisme de stocare.
Crearea listei de array:
Lista arraylistsample = nou ArrayList ();
Adăugarea de obiecte în lista de elemente de matrice:
Arraylistsample. add („nume1“);
Arraylistsample. add („name2“);
Astfel rezultă lista array - [name1, name2].
Crearea listei conectate:
List linkedlistsample = new linkedList ();
Adăugarea de obiecte în lista asociată:
Linkedlistsample. add („NAME3“);
Linkedlistsample. add („NAME4“);
Astfel va arăta lista legată rezultată - [name3, name4].
Care este mai bine pentru operațiunea Get sau Search?
Lista de matrice durează O (1) timp pentru a rula orice căutare de date, în timp ce lista legată ia u O (n) pentru căutarea de date n . Prin urmare, o listă de Array utilizează întotdeauna un timp constant pentru orice căutare de date, dar în lista Legate, timpul necesar depinde de poziția datelor. Prin urmare, listele Array sunt întotdeauna o alegere mai bună pentru operațiile Get sau Search.
Care este mai bine pentru operația de inserție sau adăugare?
Atât lista Array cât și Listă legată iau timpul O (1) pentru adăugarea de date. Dar dacă matricea este plină, atunci lista Array durează o perioadă considerabilă de timp pentru ao redimensiona și copia articolele la cea mai nouă. Într-un astfel de caz, lista legată este cea mai bună alegere.
Care este mai bine pentru operația de eliminare?
Operația de eliminare durează aproape același timp atât în lista Array, cât și în lista Linked. În lista Array, această operație șterge datele și apoi schimbă poziția datelor pentru a forma matricea mai nouă - durează ora O (n). În lista Legat, această operație traversează datele particulare și modifică pozițiile indicatoarelor pentru a forma o listă mai nouă. Timpul pentru traversal și eliminare este și O (n) aici.
Care este mai rapid?
Știm că o listă de Array utilizează o matrice internă pentru a stoca datele reale. Prin urmare, dacă toate datele sunt șterse, atunci toate datele viitoare necesită o schimbare de memorie.Evident, acest lucru necesită o perioadă considerabilă de timp și încetinește situația. O astfel de schimbare de memorie nu este necesară în lista Legată, deoarece tot ceea ce face este schimbarea locației indicatorului. Prin urmare, o listă legată este mai rapidă decât o listă Array în orice fel de stocare de date. Cu toate acestea, aceasta depinde exclusiv de tipul de operare, i. e. pentru operația Obțineți sau Căutați, lista Legată are mult mai mult timp decât o listă de Array. Când ne uităm la performanța generală, putem spune că lista asociată este mai rapidă.
Când să folosiți o listă de matrice și o listă asociată?
O listă de matrice este cea mai potrivită pentru cerințele de date mai mici, unde este disponibilă o memorie continuă. Dar când avem de-a face cu o cantitate mare de date, disponibilitatea memoriei continue implementează mecanismele de stocare a datelor, fie că este mică sau imensă. Apoi, decideți care dintre ele să alegeți - lista Array sau lista Linked. Puteți continua cu o listă de matrice atunci când trebuie doar să stocați și să preluați date. Dar o listă vă poate ajuta dincolo de asta prin manipularea datelor. Odată ce decideți cât de frecvent este necesară manipularea datelor, este important să verificați ce tip de recuperare de date efectuați de obicei. Atunci când este doar Get sau Search, atunci lista Array este cea mai bună alegere; pentru alte operațiuni, cum ar fi inserarea sau ștergerea, continuați cu lista conectată.
Să ne uităm la diferențele în forma tabelară.
