implementa l'elenco collegato utilizzando l'array - vantaggi e svantaggi

Question

So come implementare l'elenco collegato utilizzando l'array. Per esempio definiamo una struttura come segue:

struct Node{ 
    int data; 
    int link; 
} 

negozi "dati" informazioni e "link" memorizza l'indice nella matrice di nodo successivo.

Qualcuno può dirmi qual è il vantaggio e lo svantaggio dell'implementazione di un elenco collegato utilizzando la matrice rispetto alla lista concatenata "ordinaria"? Ogni suggerimento sarà apprezzato.

Answer 1

Se si esegue il backup di un elenco collegato con un array, si avranno gli svantaggi di entrambi. Di conseguenza, questo probabilmente non è un ottimo modo per implementarlo.

Alcuni svantaggi immediati:

1. Dovrete spazio morto nella matrice (le voci che non sono attualmente utilizzati per gli elementi) occupare memoria
2. Dovrete tenere traccia della libera voci - dopo alcuni inserimenti e cancellazioni, queste voci gratuite potrebbero essere ovunque.
3. L'utilizzo di un array imporrà un limite superiore alle dimensioni dell'elenco collegato.

suppongo alcuni vantaggi sono:

1. Se siete su un sistema a 64 bit, i "puntatori" avrà meno spazio (anche se lo spazio aggiuntivo richiesto da ingressi gratuiti probabilmente supera questo vantaggio
2. È possibile serializzare l'array su disco e rileggerlo facilmente con una chiamata mmap(). Tuttavia, sarebbe meglio usare una sorta di buffer di protocollo per la portabilità.
3. Si potrebbe fare qualche garanzia sugli elementi nella matrice essendo vicini gli uni agli altri in memoria.

Answer 2

Qualcuno può dirmi qual è il vantaggio e svantaggio di attuazione della lista collegata con un array rispetto a lista collegata "ordinario"?

liste concatenate avere i seguenti complessità:

• cons x xs: O (1)
• accodamento nm: O (n)
• indice i xs: O (n)

se il vostro represe ntazione utilizza un rigoroso, array contiguo, si avrà diversa complessità:

• contro richiederanno copiare il vecchio array: O (n)
• accodamento richiede la copia di entrambi gli array in un nuovo spazio contiguo: O (n + m)
• indice può essere implementata come accesso array: O (1)

Cioè, una lista collegata API implementata in termini s degli array si comporterà come un array.

È possibile attenuarlo in qualche modo utilizzando un elenco o un albero collegato di array rigorosi, che porta a corde o alberi di dita o sequenze pigre.

Answer 3

stack in attrezzo a due vie. prima nell'uso della matrice e la seconda sta usando la lista collegata.

alcuni svantaggi nell'utilizzo della matrice, quindi la maggior parte dei programmatori utilizzano l'elenco collegato nello strumento stack.

prima è lo stack utilizzando l'elenco collegato prima non dichiarare la dimensione dello stack e l'archivio dati non limitato nello stack. la seconda è la lista collegata nel saggio del puntatore per dichiararla e usarla.

utilizza un solo puntatore nell'elenco collegato. il suo puntatore in alto chiamato.

stack è l'uso del metodo lifo. ma alcuni svantaggi nell'implementazione del programma dell'elenco collegato.

La maggior parte dei programmatori utilizzano l'implementazione dello stack utilizzando l'elenco desiderato.

Answer 4

Utilizzando l'implementazione di array, è possibile avere un accesso sequenziale & ai nodi di elenco, d'altra parte, Se si implementa l'elenco collegato utilizzando i puntatori, è possibile avere accesso casuale ai nodi. L'implementazione di array è utile quando si ha a che fare con il numero fisso. Di elementi perché il ridimensionamento di un array è costoso per quanto riguarda le prestazioni, perché se è necessario inserire/eliminare nodi dal centro della lista, è necessario spostare ogni nodo in un secondo momento. Contrariamente a ciò, è necessario utilizzare l'implementazione del puntatore quando non si conosce no. dei nodi desiderati, in quanto tale elenco può crescere/ridursi in modo efficiente & non è necessario spostare alcun nodo, è possibile semplicemente dereferenziando i puntatori di riferimento &.