Diferența dintre lista matrice și lista asociată

Cum sunt stocate datele?

Lista de liste și lista conectată sunt termeni obișnuiți atunci când este vorba despre 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ă matricolă și listă asociată

Am discutat deja modul în care ambele mecanisme de stocare pun datele și putem oferi 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.

Folosirea memoriei

Pe măsură ce lista Array 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.

Dimensiunea listei 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.

Recuperare de date

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 Linked utilizează un indicator pentru 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 invers

Lista conectată ne permite să traversăm în direcția inversă cu ajutorul descendingiterator (). Totuși, nu avem o astfel de facilitate într-o listă Array - traversarea inversă devine o problemă aici.

Sintaxă

Să ne uităm la sintaxa Java a ambelor mecanisme de stocare.

Crearea listei de coloane:

Lista arraylistsample = noul ArrayList ();

Adăugarea de obiecte în lista de matrice:

Arraylistsample.add ( „nume1“);

Arraylistsample.add ( „name2“);

Așa va arăta lista rezultată a matricei - [name1, name2].

Crearea unei liste:

Listă linkedlistsample = new linkedList ();

Adăugarea de obiecte în lista conectată:

Linkedlistsample.add ( „NAME3“);

Linkedlistsample.add ( „NAME4“);

Așa va arăta lista asociată rezultată - [nume3, nume4].

 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 n^lea căutare de date. 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 inserare sau adăugare?

Atât lista Array cât și lista 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 aceeași perioadă de 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 Legate, această operație traversează datele particulare și modifică pozițiile indicatorului 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ă 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 operațiune, adică 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ă utilizaț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. După 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ă.

S.No	concepte	diferenţe
		Array List	Lista conectată
1	Modul de stocare a datelor	Utilizează stocarea secvențială a datelor	Utilizează stocarea non-secvențială a datelor
2	Schema internă de stocare	Menține o matrice dinamică internă	Menține o listă asociată
3	Folosirea memoriei	Necesită spațiu de memorie doar pentru date	Necesită spațiu de memorie pentru date, precum și pentru indicatori
4	Dimensiunea listei inițiale	Necesită spațiu pentru cel puțin 10 articole	Nu are nevoie de spațiu și putem crea chiar și o listă lipsită de legături cu dimensiunea 0.
5	Recuperare de date	Se calculează ca prima poziție de date + 'n', unde 'n' este ordinea datelor din lista Array	Este necesară trecerea de la primul sau ultimul până la datele solicitate
6	Sfârșitul datelor	Valorile Null marchează sfârșitul	Indicatorul Null marchează sfârșitul
7	Traversal invers	Nu o permite	Permite acest lucru cu ajutorul descendingiterator ()
8	Sintaxă de creare a listei	Lista arraylistsample = noul ArrayList ();	Listă linkedlistsample = new linkedList ();
9	Adăugarea de obiecte	Arraylistsample.add ( „nume1“);	Linkedlistsample.add ( „NAME3“);
10	Obțineți sau căutați	Are O (1) timp și este mai bun în performanță	Își ia O (n) timpul și performanța depinde de poziția datelor
11	Inserați sau Adăugați	Consumă timpul O (1), cu excepția cazului în care matricea este plină	Consumă O (1) timp în toate circumstanțele
12	Ștergerea sau eliminarea	Își ia O (n) timp	Își ia O (n) timp
13	Când să utilizați?	Atunci când sunt implicate o mulțime de operații Get sau Search; disponibilitatea memoriei ar trebui să fie mai mare chiar și la început	Când există o mulțime de operații Insert sau Delete și disponibilitatea memoriei nu trebuie să fie continuă