Differenza tra lista matrici e lista collegata

Come vengono archiviati i dati?

Elenco di matrici e elenco collegato sono termini comuni quando si tratta di archiviazione e recupero dei dati. Sebbene ci siano molti dispositivi di archiviazione, in definitiva, dipendono dal meccanismo di archiviazione. Questi due meccanismi di archiviazione inseriscono i dati nei dispositivi di archiviazione e li recuperano quando necessario. Diamo un'occhiata a come memorizzano i dati nella loro memoria. L'elenco di array utilizza una memoria sequenziale e le porzioni di dati vengono memorizzate una dopo l'altra. Questa è forse una forma più semplice di archiviazione: evita la confusione. Sì, possiamo recuperare l'elemento o i dati successivi dalla successiva posizione di memoria dell'elenco di array; tuttavia, viene memorizzato con l'aiuto di puntatori nell'elenco collegato. Qui abbiamo bisogno di due posizioni di memoria per la memorizzazione: una per i dati, l'altra per il puntatore. Un puntatore indirizza la posizione di memoria dei dati successivi. Possiamo facilmente capire che la lista collegata non memorizza mai i dati in sequenza; piuttosto, utilizza un meccanismo di archiviazione casuale. I puntatori sono gli elementi chiave nella localizzazione delle posizioni dei dati nella memoria.

Array dinamico e elenco collegato

Abbiamo già discusso di come entrambi i meccanismi di archiviazione inseriscono i dati e possiamo fornire un termine 'array dinamico' per lo schema di archiviazione interna dell'elenco di array. Mette semplicemente i dati uno dopo l'altro, da cui il nome, mentre l'elenco collegato utilizza un elenco interno con l'aiuto di puntatori per tracciare l'elemento successivo. Pertanto, utilizza una lista collegata interna, come una lista concatenata o doppiamente collegata per mostrarci i dati successivi.

Utilizzo della memoria

Come elenco di array memorizza solo i dati effettivi, abbiamo bisogno di spazio solo per i dati che memorizziamo. Viceversa, nella lista Linked, utilizziamo anche i puntatori. Pertanto, sono necessarie due posizioni di memoria e possiamo dire che l'elenco collegato consuma più memoria rispetto all'elenco di array. Un aspetto vantaggioso dell'elenco collegato è che non richiede mai posizioni di memoria continua per archiviare i nostri dati, al contrario dell'elenco di array. I puntatori sono in grado di mantenere la posizione della prossima posizione dei dati, e possiamo persino utilizzare slot di memoria più piccoli che non sono continui. Quando si parla di utilizzo della memoria, i puntatori svolgono il ruolo principale nella lista Linked, e così pure l'efficacia di essi.

Dimensione dell'elenco di array iniziale e dell'elenco collegato

Con la lista di array, anche una lista vuota richiede una dimensione di 10, ma con una lista collegata, non abbiamo bisogno di uno spazio così grande. Possiamo creare una lista Linked vuota con una dimensione di 0. In seguito, possiamo aumentare la dimensione secondo necessità.

Recupero dei dati

Il recupero dei dati è più semplice nell'elenco di array quando si memorizza in sequenza. Tutto ciò che fa è identificare la prima posizione dei dati; da lì, si accede in sequenza alla prossima posizione per recuperare il resto. Calcola come la prima posizione dei dati + 'n', dove 'n' è l'ordine dei dati nella lista della matrice. L'elenco collegato fa riferimento al puntatore iniziale per trovare la prima posizione dei dati e da lì fa riferimento al puntatore associato a ciascun dato per trovare la successiva posizione dei dati. Il processo di recupero dipende principalmente dai puntatori qui, e ci mostrano in modo efficace la prossima posizione dei dati.

Fine dei dati

L'elenco di array utilizza un valore nullo per contrassegnare la fine dei dati, mentre l'elenco collegato utilizza un puntatore nullo a questo scopo. Non appena il sistema riconosce i dati nulli, l'elenco della matrice interrompe il successivo recupero dei dati. In modo simile, il puntatore nullo arresta il sistema dal procedere al successivo recupero dei dati.

Inverso trasversale

L'elenco collegato ci consente di attraversare le direzioni opposte con l'aiuto di descendingiterator (). Tuttavia, non disponiamo di una tale funzionalità in una lista di array: l'attraversamento inverso diventa un problema qui.

Sintassi

Diamo un'occhiata alla sintassi Java di entrambi i meccanismi di archiviazione.

Creazione lista matrici:

Elenca arraylistsample = new ArrayList ();

Aggiunta di oggetti all'elenco di array:

Arraylistsample.add ( “nome1”);

Arraylistsample.add ( “nome2”);

Ecco come apparirà la lista di array risultante: [nome1, nome2].

Creazione di liste collegate:

List linkedlistsample = new linkedList ();

Aggiunta di oggetti alla lista collegata:

Linkedlistsample.add ( “NAME3”);

Linkedlistsample.add ( “NAME4”);

Ecco come apparirà la lista collegata risultante: [nome3, nome4].

 Che è meglio per l'operazione Get o Ricerca?

La lista Array richiede O (1) tempo per eseguire qualsiasi ricerca di dati, mentre la lista Collegata prende u O (n) per il n^esimo ricerca di dati. Pertanto, un elenco di array utilizza sempre un tempo costante per qualsiasi ricerca di dati, ma nell'elenco collegato, il tempo impiegato dipende dalla posizione dei dati. Pertanto, gli elenchi di array sono sempre una scelta migliore per le operazioni di ricerca o di ricerca.

Quale è meglio per l'operazione di inserimento o aggiunta?

Sia l'elenco di array sia l'elenco collegato richiedono O (1) per l'aggiunta dei dati. Ma se l'array è pieno, l'elenco di Array impiega una notevole quantità di tempo per ridimensionarlo e copiare gli elementi in uno più nuovo. In tal caso, l'elenco collegato è la scelta migliore.

Quale è meglio per l'operazione di rimozione?

L'operazione di rimozione richiede quasi lo stesso tempo sia nella lista della matrice che nella lista collegata. Nell'elenco della matrice, questa operazione elimina i dati e quindi sposta la posizione dei dati per formare l'array più recente: richiede O (n) di tempo. Nell'elenco Collegato, questa operazione attraversa i dati particolari e cambia le posizioni dei puntatori per formare l'elenco più recente. Anche qui il tempo per l'attraversamento e la rimozione è O (n).

Che è più veloce?

Sappiamo che un elenco di array utilizza un array interno per memorizzare i dati effettivi. Pertanto, se vengono cancellati dati, tutti i dati successivi necessitano di uno spostamento di memoria. Ovviamente, ciò richiede una notevole quantità di tempo e rallenta le cose. Tale spostamento di memoria non è richiesto nella lista collegata, poiché tutto ciò che fa è cambiare la posizione del puntatore. Pertanto, un elenco collegato è più veloce di un elenco di array in qualsiasi tipo di archiviazione di dati. Tuttavia, questo dipende esclusivamente dal tipo di operazione, vale a dire per l'operazione Ottieni o Ricerca, l'elenco collegato impiega molto più tempo di un elenco di array. Quando guardiamo al rendimento generale, possiamo dire che l'elenco collegato è più veloce.

Quando utilizzare un elenco di matrici e un elenco collegato?

Un elenco di array è più adatto per i requisiti di dati più piccoli in cui è disponibile memoria continua. Ma quando gestiamo enormi quantità di dati, la disponibilità di memoria continua implementa i meccanismi di archiviazione dei dati, che siano piccoli o enormi. Quindi, decidere quale scegliere: l'elenco di array o l'elenco collegato. Puoi andare avanti con un elenco di array quando hai solo bisogno di immagazzinare e recuperare dati. Ma una lista può aiutarti oltre a manipolare i dati. Una volta decisa la frequenza con cui è richiesta la manipolazione dei dati, è importante verificare quale tipo di recupero dei dati si esegue abitualmente. Quando è solo Get o Cerca, la Lista array è la scelta migliore; per altre operazioni come Inserimento o Cancellazione, andare avanti con l'Elenco collegato.

Vediamo le differenze in forma tabellare.

S.No	concetti	differenze
		Lista di array	Lista collegata
1	Data Storage Fashion	Utilizza la memorizzazione sequenziale dei dati	Utilizza archiviazione dati non sequenziale
2	Schema di archiviazione interno	Mantiene una matrice dinamica interna	Mantiene un elenco collegato
3	Utilizzo della memoria	Richiede spazio di memoria solo per i dati	Richiede spazio di memoria per i dati e anche per i puntatori
4	Dimensione dell'elenco iniziale	Ha bisogno di spazio per almeno 10 articoli	Non ha bisogno di spazio e possiamo persino creare un elenco Linked vuoto di dimensioni 0.
5	Recupero dei dati	Calcola come la prima posizione dati + 'n', dove 'n' è l'ordine dei dati nella lista della matrice	È necessario attraversare il primo o l'ultimo fino a quando non sono richiesti i dati richiesti
6	Fine dei dati	I valori Null segnano la fine	The Null Pointer segna la fine
7	Inverso trasversale	Non lo consente	Permette con l'aiuto di descendingiterator ()
8	Sintassi per la creazione di liste	Elenca arraylistsample = new ArrayList ();	List linkedlistsample = new linkedList ();
9	Aggiungere oggetti	Arraylistsample.add ( “nome1”);	Linkedlistsample.add ( “NAME3”);
10	Ottieni o cerca	Prende O (1) tempo ed è migliore in termini di prestazioni	Prende O (n) il tempo e le prestazioni dipendono dalla posizione dei dati
11	Inserisci o aggiunta	Consuma O (1) volta tranne quando l'array è pieno	Consuma O (1) tempo in tutte le circostanze
12	Cancellazione o rimozione	Prende O (n) tempo	Prende O (n) tempo
13	Quando usare?	Quando sono coinvolte molte operazioni di ricerca o di ricerca; la disponibilità di memoria dovrebbe essere più alta anche all'inizio	Quando ci sono molte operazioni di inserimento o cancellazione, e la disponibilità di memoria non deve essere continua