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

Introducerea elementului la început:Pentru a introduce noul element la început, trebuie mai întâi să deplasăm elementul spre dreapta pentru a crea un spațiu în prima poziție. Deci, complexitatea timpului va fi proporțională cu dimensiunea listei. Dacă n este dimensiunea matricei, complexitatea timpului ar fi O(n).

Î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).

Introducerea unui element la sfârșit

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

Inserarea unui element la mijloc

Să presupunem că vrem să inserăm elementul la i^thpozitia 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:

Ușurință în utilizare

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ă.

Dinamic în mărime

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ă.