Differenza tra elenco di array e elenco collegato Differenza tra
Come vengono memorizzati 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 interno 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 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 lato vantaggioso dell'elenco collegato è che non richiede mai posizioni di memoria continua per memorizzare 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ì anche l'efficacia di essi.
Dimensione della lista iniziale della matrice e della lista collegata
Con la lista della matrice, 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 dati
Il recupero dei dati è più semplice nella lista Array mentre 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.
Reverse Traversal
L'elenco collegato ci permette di attraversare in direzione opposta 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. aggiungere (“nome1”);
Arraylistsample. aggiungere (“nome2”);
Ecco come apparirà la lista di array risultante: [nome1, nome2].
Creazione lista collegata:
Elenco linkedlistsample = new linkedList ();
Aggiunta di oggetti alla lista collegata:
Campaignlistsample. aggiungere (“NAME3”);
Linkedlistsample. aggiungere (“NAME4”);
Ecco come apparirà la lista collegata risultante: [nome3, nome4].
Quale è meglio per l'operazione Get o Ricerca?
L'elenco di Array richiede O (1) tempo per eseguire qualsiasi ricerca di dati, mentre l'elenco Collegato prende u O (n) per la ricerca di dati n th . 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).
Qual è il 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 dei dati. Tuttavia, questo è puramente dipendente dal tipo di operazione, i. e. per l'operazione Ottieni o Ricerca, l'elenco collegato impiega molto più tempo di un elenco di matrici. 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.
