Vettore E Lista collegata sono i due modi di organizzare i dati in memoria. Prima di comprendere le differenze tra il Vettore e il Lista collegata , diamo prima un'occhiata in una matrice E un elenco collegato .
operatore condizionale in Java
Cos'è un array?
Una struttura dati che contiene gli elementi dello stesso tipo. Una struttura dati è un modo di organizzare i dati; un array è una struttura dati perché organizza i dati in sequenza. Un array è un grosso pezzo di memoria in cui la memoria è divisa in blocchi piccoli e piccoli e ciascun blocco è in grado di memorizzare un valore.
Supponiamo di aver creato un array composto da 10 valori, quindi ogni blocco memorizzerà il valore di un tipo intero. Se proviamo a memorizzare il valore in un array di tipi diversi, allora non è un array corretto e genererà un errore in fase di compilazione.
Dichiarazione di array
Un array può essere dichiarato come:
data_type name of the array[no of elements]
Per dichiarare un array, dobbiamo prima specificare il tipo dell'array e poi il nome dell'array. All'interno delle parentesi quadre dobbiamo specificare il numero di elementi che il nostro array dovrebbe contenere.
Capiamolo attraverso un esempio.
int a[5];
Nel caso precedente, abbiamo dichiarato un array di 5 elementi con ' UN ' nome di un numero intero tipo di dati.
Cos'è la lista collegata?
Un elenco collegato è la raccolta di nodi archiviati in modo casuale. Ogni nodo è costituito da due campi, ovvero dati E collegamento . Qui, i dati sono il valore memorizzato in quel particolare nodo e il collegamento è il puntatore che contiene l'indirizzo del nodo successivo.
join e tipi di join
Differenze tra array ed elenco collegato
Non possiamo dire quale struttura dati sia migliore, cioè array o lista collegata . Può esserci la possibilità che una struttura dati sia migliore per un tipo di requisito, mentre l'altra struttura dati sia migliore per un altro tipo di requisito. Esistono vari fattori come quali sono le operazioni frequenti eseguite sulla struttura dei dati o la dimensione dei dati e altri fattori anche sulla base della selezione della struttura dei dati. Ora vedremo alcune differenze tra l'array e la lista concatenata in base ad alcuni parametri.
1. Costo di accesso a un elemento
Nel caso di un array, indipendentemente dalla dimensione dell'array, l'array impiega un tempo costante per accedere a un elemento. In un array, gli elementi sono memorizzati in modo contiguo, quindi se conosciamo l'indirizzo di base dell'elemento, possiamo facilmente ottenere l'indirizzo di qualsiasi elemento in un array. Dobbiamo eseguire un semplice calcolo per ottenere l'indirizzo di qualsiasi elemento di un array. Quindi, accedere all'elemento in un array è O(1) in termini di complessità temporale.
Nell'elenco collegato gli elementi non vengono memorizzati in modo contiguo. È costituito da più blocchi e ciascun blocco è rappresentato come un nodo. Ogni nodo ha due campi, ovvero uno è per il campo dati e un altro memorizza l'indirizzo del nodo successivo. Per trovare qualsiasi nodo nell'elenco collegato, dobbiamo prima determinare il primo nodo noto come nodo testa. Se dobbiamo trovare il secondo nodo nell'elenco, allora dobbiamo attraversare dal primo nodo e, nel peggiore dei casi, per trovare l'ultimo nodo, attraverseremo tutti i nodi. Il caso medio per accedere all'elemento è O(n).
Concludiamo che il costo di accesso a un elemento dell'array è inferiore a quello della lista concatenata. Pertanto, se abbiamo dei requisiti per accedere agli elementi, l'array è una scelta migliore.
2. Costo per l'inserimento di un elemento
Nell'inserimento possono essere presenti tre scenari:
Nel caso di una lista concatenata, per inserire un elemento all'inizio della lista concatenata, creeremo un nuovo nodo, e l'indirizzo del primo nodo verrà aggiunto al nuovo nodo. In questo modo il nuovo nodo diventa il primo nodo. Pertanto, la complessità temporale non è proporzionale alla dimensione dell'elenco. La complessità temporale sarebbe costante, cioè O(1).
Se l'array non è pieno, possiamo aggiungere direttamente il nuovo elemento tramite l'indice. In questo caso, la complessità temporale sarebbe costante, cioè O(1). Se l'array è pieno, dobbiamo prima copiare l'array in un altro array e aggiungere un nuovo elemento. In questo caso, la complessità temporale sarebbe O(n).
Per inserire un elemento alla fine della lista concatenata, dobbiamo percorrere tutta la lista. Se la lista concatenata fosse composta da n elementi, la complessità temporale sarebbe O(n).
Supponiamo di voler inserire l'elemento in ithposizione dell'array; dobbiamo spostare gli n/2 elementi verso destra. Pertanto la complessità temporale è proporzionale al numero degli elementi. La complessità temporale sarebbe O(n) per il caso medio.
elenco degli stati
Nel caso della lista concatenata, dobbiamo passare alla posizione in cui dobbiamo inserire il nuovo elemento. Tuttavia, non dobbiamo eseguire alcun tipo di spostamento, ma dobbiamo passare alla posizione n/2. Il tempo impiegato è proporzionale al numero n di elementi e la complessità temporale per il caso medio sarebbe O(n).
L'elenco collegato risultante è:
L'implementazione di un array è semplice rispetto all'elenco collegato. Durante la creazione di un programma utilizzando un elenco collegato, il programma è più soggetto a errori come errori di segmentazione o perdite di memoria. Pertanto, è necessario prestare molta attenzione durante la creazione di un programma nell'elenco collegato.
L'elenco collegato ha dimensioni dinamiche mentre l'array è statico. Qui, statico non significa che non possiamo decidere la dimensione in fase di esecuzione, ma non possiamo modificarla una volta decisa la dimensione.
3. Requisiti di memoria
Poiché gli elementi di un array vengono archiviati in un blocco contiguo di memoria, l'array ha dimensioni fisse. Supponiamo di avere un array di dimensione 7 e che l'array sia composto da 4 elementi, quindi il resto dello spazio è inutilizzato. La memoria occupata dai 7 elementi:
Spazio di memoria = 7*4 = 28 byte
Dove 7 è il numero di elementi in un array e 4 è il numero di byte di tipo intero.
In caso di lista concatenata, non c'è memoria inutilizzata ma la memoria extra è occupata dalle variabili puntatore. Se i dati sono di tipo intero, la memoria totale occupata da un nodo è 8 byte, ovvero 4 byte per i dati e 4 byte per la variabile puntatore. Se la lista concatenata è composta da 4 elementi, lo spazio di memoria occupato dalla lista concatenata sarebbe:
webdriver
Spazio di memoria = 8*4 = 32 byte
L'elenco collegato sarebbe una scelta migliore se la parte dati è di dimensioni maggiori. Supponiamo che i dati siano di 16 byte. Lo spazio di memoria occupato dall'array sarebbe 16*7=112 byte mentre l'elenco collegato occupa 20*4=80, qui abbiamo specificato 20 byte come 16 byte per la dimensione dei dati più 4 byte per la variabile puntatore. Se scegliamo una dimensione di dati maggiore, l'elenco collegato consumerà meno memoria; altrimenti dipende dai fattori che stiamo adottando per determinare la dimensione.
Diamo un'occhiata alle differenze tra l'array e l'elenco collegato in forma tabellare.
| Vettore | Lista collegata |
|---|---|
| Un array è una raccolta di elementi con tipo di dati simile. | Una lista collegata è una raccolta di oggetti nota come nodo in cui il nodo è costituito da due parti, ovvero dati e indirizzo. |
| Gli elementi dell'array vengono archiviati in una posizione di memoria contigua. | Gli elementi dell'elenco collegato possono essere archiviati ovunque nella memoria o archiviati in modo casuale. |
| L'array funziona con una memoria statica. Qui memoria statica significa che la dimensione della memoria è fissa e non può essere modificata in fase di esecuzione. | L'elenco collegato funziona con la memoria dinamica. In questo caso, memoria dinamica significa che la dimensione della memoria può essere modificata in fase di esecuzione in base alle nostre esigenze. |
| Gli elementi dell'array sono indipendenti l'uno dall'altro. | Gli elementi dell'elenco collegato dipendono l'uno dall'altro. Poiché ciascun nodo contiene l'indirizzo del nodo successivo, per accedere al nodo successivo dobbiamo accedere al nodo precedente. |
| L'array richiede più tempo durante l'esecuzione di qualsiasi operazione come inserimento, cancellazione, ecc. | L'elenco collegato richiede meno tempo durante l'esecuzione di qualsiasi operazione come inserimento, cancellazione, ecc. |
| L'accesso a qualsiasi elemento di un array è più veloce poiché è possibile accedere direttamente all'elemento di un array tramite l'indice. | L'accesso a un elemento in un elenco collegato è più lento poiché inizia a spostarsi dal primo elemento dell'elenco collegato. |
| Nel caso di un array, la memoria viene allocata in fase di compilazione. | Nel caso di un elenco collegato, la memoria viene allocata in fase di esecuzione. |
| L'utilizzo della memoria è inefficiente nell'array. Ad esempio, se la dimensione dell'array è 6 e l'array è composto solo da 3 elementi, il resto dello spazio sarà inutilizzato. | L'utilizzo della memoria è efficiente nel caso di un elenco collegato poiché la memoria può essere allocata o deallocata in fase di esecuzione in base alle nostre esigenze. |