Matrice și Lista legată sunt cele două moduri de organizare a datelor din memorie. Înainte de a înțelege diferențele dintre Matrice si Lista legată , ne uităm mai întâi la o matrice și o listă legată .
scaner în java
Ce este o matrice?
O structură de date care conține elemente de același tip. O structură de date este o modalitate de organizare a datelor; o matrice este o structură de date deoarece organizează secvențial datele. O matrice este o bucată mare de memorie în care memoria este împărțită în blocuri mici-mici și fiecare bloc este capabil să stocheze o anumită valoare.
Să presupunem că am creat o matrice care constă din 10 valori, atunci fiecare bloc va stoca valoarea unui tip întreg. Dacă încercăm să stocăm valoarea într-o matrice de diferite tipuri, atunci aceasta nu este o matrice corectă și va genera o eroare de compilare.
Declarație de matrice
O matrice poate fi declarată ca:
data_type name of the array[no of elements]
Pentru a declara o matrice, trebuie mai întâi să specificăm tipul matricei și apoi numele matricei. Între paranteze pătrate, trebuie să specificăm numărul de elemente pe care ar trebui să le conțină matricea noastră.
Să înțelegem printr-un exemplu.
int a[5];
În cazul de mai sus, am declarat o matrice de 5 elemente cu ' A ' numele unui întreg tip de date.
Ce este lista legată?
O listă legată este o colecție de noduri care sunt stocate aleatoriu. Fiecare nod este format din două câmpuri, adică date și legătură . Aici, datele sunt valoarea stocată la acel nod special, iar legătura este pointerul care deține adresa următorului nod.
Diferențele dintre Array și Lista Linked
Nu putem spune care structură de date este mai bună, adică matrice sau lista legată . Poate exista posibilitatea ca o structură de date să fie mai bună pentru un tip de cerință, în timp ce cealaltă structură de date să fie mai bună pentru un alt tip de cerință. Există diverși factori, cum ar fi operațiunile frecvente efectuate asupra structurii de date sau dimensiunea datelor și alți factori, de asemenea, pe baza cărora este selectată structura de date. Acum vom vedea câteva diferențe între matrice și lista legată pe baza unor parametri.
1. Costul accesării unui element
În cazul unei matrice, indiferent de dimensiunea unei matrice, o matrice are nevoie de un timp constant pentru a accesa un element. Într-o matrice, elementele sunt stocate într-o manieră contiguă, deci dacă știm adresa de bază a elementului, atunci putem obține cu ușurință adresa oricărui element dintr-o matrice. Trebuie să facem un calcul simplu pentru a obține adresa oricărui element dintr-o matrice. Deci, accesarea elementului dintr-o matrice este O(1) din punct de vedere al complexității timpului.
În lista legată, elementele nu sunt stocate într-o manieră contiguă. Este format din mai multe blocuri, iar fiecare bloc este reprezentat ca un nod. Fiecare nod are două câmpuri, adică unul este pentru câmpul de date, iar altul stochează adresa următorului nod. Pentru a găsi orice nod în lista legată, trebuie mai întâi să determinăm primul nod cunoscut sub numele de nod principal. Dacă trebuie să găsim al doilea nod din listă, atunci trebuie să parcurgem de la primul nod și, în cel mai rău caz, pentru a găsi ultimul nod, vom parcurge toate nodurile. Cazul mediu pentru accesarea elementului este O(n).
Concluzionăm că costul accesării unui element din matrice este mai mic decât lista legată. Prin urmare, dacă avem vreo cerință pentru accesarea elementelor, atunci matricea este o alegere mai bună.
2. Costul introducerii unui element
Pot exista trei scenarii în inserare:
alfabet după număr
În cazul unei liste legate, pentru a insera un element la începutul listei legate, vom crea un nou nod, iar adresa primului nod este adăugată noului nod. În acest fel, noul nod devine primul nod. Deci, complexitatea timpului nu este proporțională cu dimensiunea listei. Complexitatea timpului ar fi constantă, adică O(1).
Dacă matricea nu este plină, atunci putem adăuga direct noul element prin index. În acest caz, complexitatea timpului ar fi constantă, adică O(1). Dacă matricea este plină, mai întâi trebuie să copiem matricea într-o altă matrice și să adăugăm un nou element. În acest caz, complexitatea timpului ar fi O(n).
Pentru a insera un element la sfârșitul listei legate, trebuie să parcurgem întreaga listă. Dacă lista legată constă din n elemente, atunci complexitatea timpului ar fi O(n).
Să presupunem că vrem să inserăm elementul la ithpozitia matricei; trebuie să deplasăm cele n/2 elemente spre dreapta. Prin urmare, complexitatea timpului este proporțională cu numărul de elemente. Complexitatea timpului ar fi O(n) pentru cazul mediu.
state din SUA
În cazul listei legate, trebuie să trecem în acea poziție în care trebuie să introducem noul element. Chiar dacă, nu trebuie să efectuăm nici un fel de schimbare, ci trebuie să traversăm în poziţia n/2. Timpul necesar este proporțional cu numărul n de elemente, iar complexitatea timpului pentru cazul mediu ar fi O(n).
Lista legată rezultată este:
Implementarea unei matrice este ușoară în comparație cu lista legată. În timpul creării unui program folosind o listă legată, programul este mai predispus la erori, cum ar fi erori de segmentare sau scurgeri de memorie. Deci, trebuie avută multă grijă atunci când creați un program în lista legată.
Lista legată este dinamică ca dimensiune, în timp ce matricea este statică. Aici, static nu înseamnă că nu putem decide dimensiunea în timpul rulării, dar nu o putem schimba odată ce dimensiunea este decisă.
3. Cerințe de memorie
Așa cum elementele dintr-o matrice stochează într-un bloc de memorie contiguu, așa și matricea este de dimensiune fixă. Să presupunem că avem o matrice de dimensiunea 7, iar matricea este formată din 4 elemente, atunci restul spațiului este nefolosit. Memoria ocupată de cele 7 elemente:
Spațiu de memorie = 7*4 = 28 de octeți
Unde 7 este numărul de elemente dintr-o matrice și 4 este numărul de octeți de tip întreg.
În cazul listelor legate, nu există memorie nefolosită, dar memoria suplimentară este ocupată de variabilele pointer. Dacă datele sunt de tip întreg, atunci memoria totală ocupată de un nod este de 8 octeți, adică 4 octeți pentru date și 4 octeți pentru variabila pointer. Dacă lista legată este formată din 4 elemente, atunci spațiul de memorie ocupat de lista legată ar fi:
webdriver
Spațiu de memorie = 8*4 = 32 de octeți
Lista legată ar fi o alegere mai bună dacă partea de date este mai mare. Să presupunem că datele sunt de 16 octeți. Spațiul de memorie ocupat de matrice ar fi 16*7=112 octeți în timp ce lista legată ocupă 20*4=80, aici am specificat 20 octeți ca 16 octeți pentru dimensiunea datelor plus 4 octeți pentru variabila pointer. Dacă alegem o dimensiune mai mare a datelor, atunci lista legată ar consuma mai puțină memorie; în caz contrar, depinde de factorii pe care îi adoptăm pentru a determina mărimea.
Să ne uităm la diferențele dintre matrice și lista legată într-o formă tabelară.
| Matrice | Lista legată |
|---|---|
| Un tablou este o colecție de elemente de un tip de date similar. | O listă legată este o colecție de obiecte cunoscută sub numele de nod în care nodul este format din două părți, adică date și adresă. |
| Elementele matricei sunt stocate într-o locație de memorie adiacentă. | Elementele listei legate pot fi stocate oriunde în memorie sau stocate aleatoriu. |
| Array funcționează cu o memorie statică. Aici memoria statică înseamnă că dimensiunea memoriei este fixă și nu poate fi modificată în timpul rulării. | Lista Linked funcționează cu memorie dinamică. Aici, memoria dinamică înseamnă că dimensiunea memoriei poate fi modificată în timpul rulării în funcție de cerințele noastre. |
| Elementele matricei sunt independente unele de altele. | Elementele listei legate sunt dependente unele de altele. Deoarece fiecare nod conține adresa următorului nod, pentru a accesa următorul nod, trebuie să accesăm nodul său anterior. |
| Array durează mai mult timp în timpul efectuării oricărei operațiuni, cum ar fi inserarea, ștergerea etc. | Lista legată durează mai puțin timp în timpul efectuării oricărei operațiuni precum inserarea, ștergerea etc. |
| Accesarea oricărui element dintr-o matrice este mai rapidă, deoarece elementul dintr-o matrice poate fi accesat direct prin index. | Accesarea unui element dintr-o listă legată este mai lentă, deoarece începe să traverseze de la primul element al listei legate. |
| În cazul unui tablou, memoria este alocată în timpul compilării. | În cazul unei liste legate, memoria este alocată în timpul rulării. |
| Utilizarea memoriei este ineficientă în matrice. De exemplu, dacă dimensiunea matricei este de 6, iar matricea constă doar din 3 elemente, restul spațiului va fi neutilizat. | Utilizarea memoriei este eficientă în cazul unei liste legate, deoarece memoria poate fi alocată sau dezalocată în timpul rulării, conform cerințelor noastre. |