Matriu i Llista enllaçada són les dues maneres d'organitzar les dades a la memòria. Abans d'entendre les diferències entre el Matriu i la Llista enllaçada , primer mirem en una matriu i una llista enllaçada .
com llegir el fitxer csv en java
Què és una matriu?
Una estructura de dades que conté els elements del mateix tipus. Una estructura de dades és una manera d'organitzar les dades; una matriu és una estructura de dades perquè organitza les dades de manera seqüencial. Una matriu és un gran tros de memòria en què la memòria es divideix en blocs petits i petits, i cada bloc és capaç d'emmagatzemar algun valor.
Suposem que hem creat una matriu que consta de 10 valors, aleshores cada bloc emmagatzemarà el valor d'un tipus enter. Si intentem emmagatzemar el valor en una matriu de diferents tipus, aleshores no és una matriu correcta i generarà un error en temps de compilació.
Declaració de matriu
Una matriu es pot declarar com:
data_type name of the array[no of elements]
Per declarar una matriu, primer hem d'especificar el tipus de matriu i després el nom de la matriu. Dins dels claudàtors, hem d'especificar el nombre d'elements que ha de contenir la nostra matriu.
Entenem-ho a través d'un exemple.
int a[5];
En el cas anterior, hem declarat una matriu de 5 elements amb ' a 'nom d'un enter tipus de dades.
Què és la llista enllaçada?
Una llista enllaçada és la col·lecció de nodes que s'emmagatzemen aleatòriament. Cada node consta de dos camps, és a dir, dades i enllaç . Aquí, les dades són el valor emmagatzemat en aquest node en particular i l'enllaç és el punter que conté l'adreça del següent node.
cadena a caràcter
Diferències entre la matriu i la llista enllaçada
No podem dir quina estructura de dades és millor, és a dir, matriu o llista enllaçada . Pot haver-hi la possibilitat que una estructura de dades sigui millor per a un tipus de requisit, mentre que l'altra estructura de dades sigui millor per a un altre tipus de requisit. Hi ha diversos factors com quines són les operacions freqüents que es realitzen a l'estructura de dades o la mida de les dades, i altres factors també en funció dels quals es selecciona l'estructura de dades. Ara veurem algunes diferències entre la matriu i la llista enllaçada en funció d'alguns paràmetres.
1. Cost d'accés a un element
En el cas d'una matriu, independentment de la mida d'una matriu, una matriu triga un temps constant per accedir a un element. En una matriu, els elements s'emmagatzemen de manera contigua, de manera que si coneixem l'adreça base de l'element, podem obtenir fàcilment l'adreça de qualsevol element d'una matriu. Hem de realitzar un càlcul senzill per obtenir l'adreça de qualsevol element d'una matriu. Per tant, accedir a l'element en una matriu és O(1) en termes de complexitat temporal.
A la llista enllaçada, els elements no s'emmagatzemen de manera contigua. Consta de diversos blocs, i cada bloc es representa com un node. Cada node té dos camps, és a dir, un és per al camp de dades i un altre emmagatzema l'adreça del següent node. Per trobar qualsevol node a la llista enllaçada, primer hem de determinar el primer node conegut com a node principal. Si hem de trobar el segon node de la llista, haurem de travessar des del primer node i, en el pitjor dels casos, per trobar l'últim node, estarem travessant tots els nodes. El cas mitjà per accedir a l'element és O(n).
Arribem a la conclusió que el cost d'accedir a un element de la matriu és inferior al de la llista enllaçada. Per tant, si tenim algun requisit per accedir als elements, la matriu és una millor opció.
2. Cost d'inserció d'un element
Hi pot haver tres escenaris a la inserció:
En el cas d'una llista enllaçada, per inserir un element a l'inici de la llista enllaçada, crearem un nou node, i l'adreça del primer node s'afegeix al nou node. D'aquesta manera, el nou node es converteix en el primer node. Per tant, la complexitat temporal no és proporcional a la mida de la llista. La complexitat temporal seria constant, és a dir, O(1).
Si la matriu no està plena, podem afegir directament l'element nou a través de l'índex. En aquest cas, la complexitat temporal seria constant, és a dir, O(1). Si la matriu està plena, primer hem de copiar la matriu a una altra matriu i afegir un element nou. En aquest cas, la complexitat temporal seria O(n).
Per inserir un element al final de la llista enllaçada, hem de recórrer tota la llista. Si la llista enllaçada consta de n elements, aleshores la complexitat temporal seria O(n).
Suposem que volem inserir l'element a la ithposició de la matriu; hem de desplaçar els n/2 elements cap a la dreta. Per tant, la complexitat temporal és proporcional al nombre d'elements. La complexitat temporal seria O(n) per al cas mitjà.
comanda sed
En el cas de la llista enllaçada, hem de recórrer a aquella posició on hem d'inserir el nou element. Tot i això, no hem de realitzar cap tipus de canvi, sinó que hem de recórrer a la posició n/2. El temps necessari és proporcional al nombre n d'elements, i la complexitat del temps per al cas mitjà seria O(n).
La llista enllaçada resultant és:
La implementació d'una matriu és fàcil en comparació amb la llista enllaçada. Mentre es crea un programa amb una llista enllaçada, el programa és més propens a errors com ara errors de segmentació o fuites de memòria. Per tant, cal tenir molta cura en crear un programa a la llista enllaçada.
La llista enllaçada és de mida dinàmica mentre que la matriu és estàtica. Aquí, l'estàtica no vol dir que no puguem decidir la mida en temps d'execució, però no la podem canviar un cop decidida la mida.
3. Requisits de memòria
Com els elements d'una matriu s'emmagatzemen en un bloc contigu de memòria, la matriu té una mida fixa. Suposem que tenim una matriu de mida 7 i que la matriu consta de 4 elements, la resta de l'espai no s'utilitza. La memòria ocupada pels 7 elements:
Espai de memòria = 7*4 = 28 bytes
On 7 és el nombre d'elements d'una matriu i 4 és el nombre de bytes d'un tipus enter.
En cas de llista enllaçada, no hi ha memòria no utilitzada, però la memòria addicional està ocupada per les variables del punter. Si les dades són de tipus enter, la memòria total ocupada per un node és de 8 bytes, és a dir, 4 bytes per a les dades i 4 bytes per a la variable punter. Si la llista enllaçada consta de 4 elements, l'espai de memòria ocupat per la llista enllaçada seria:
controlador web
Espai de memòria = 8*4 = 32 bytes
La llista enllaçada seria una millor opció si la part de dades és més gran. Suposem que les dades són de 16 bytes. L'espai de memòria ocupat per la matriu seria 16*7=112 bytes mentre que la llista enllaçada ocupa 20*4=80, aquí hem especificat 20 bytes com 16 bytes per a la mida de les dades més 4 bytes per a la variable punter. Si triem la mida més gran de dades, aleshores la llista enllaçada consumiria menys memòria; en cas contrari, depèn dels factors que estem adoptant per determinar la mida.
Vegem les diferències entre la matriu i la llista enllaçada en forma tabular.
| Matriu | Llista enllaçada |
|---|---|
| Una matriu és una col·lecció d'elements d'un tipus de dades similar. | Una llista enllaçada és una col·lecció d'objectes conegut com a node on el node consta de dues parts, és a dir, dades i adreça. |
| Els elements de la matriu s'emmagatzemen en una ubicació de memòria contigua. | Els elements de la llista enllaçada es poden emmagatzemar a qualsevol lloc de la memòria o emmagatzemats aleatòriament. |
| Array funciona amb una memòria estàtica. Aquí la memòria estàtica significa que la mida de la memòria és fixa i no es pot canviar en temps d'execució. | La llista enllaçada funciona amb memòria dinàmica. Aquí, la memòria dinàmica significa que la mida de la memòria es pot canviar en temps d'execució segons els nostres requisits. |
| Els elements de la matriu són independents entre si. | Els elements de la llista enllaçada depenen els uns dels altres. Com que cada node conté l'adreça del següent node, per accedir al següent node, hem d'accedir al seu node anterior. |
| Array triga més temps en realitzar qualsevol operació com ara la inserció, la supressió, etc. | La llista enllaçada triga menys temps en realitzar qualsevol operació com ara inserció, supressió, etc. |
| L'accés a qualsevol element d'una matriu és més ràpid, ja que es pot accedir directament a l'element d'una matriu mitjançant l'índex. | L'accés a un element d'una llista enllaçada és més lent, ja que comença a recórrer des del primer element de la llista enllaçada. |
| En el cas d'una matriu, la memòria s'assigna en temps de compilació. | En el cas d'una llista enllaçada, la memòria s'assigna en temps d'execució. |
| La utilització de la memòria és ineficient a la matriu. Per exemple, si la mida de la matriu és 6 i la matriu només consta de 3 elements, la resta de l'espai no s'utilitzarà. | La utilització de la memòria és eficient en el cas d'una llista enllaçada, ja que la memòria es pot assignar o desassignar en temps d'execució segons el nostre requisit. |