Microsoft Chiede: Elenco Singolo o Elenco Doubly? Quali sono i pro e i contro dell'uso di ciascuno?

Question

Mi viene fatta questa domanda e ho i miei detti ma non sono proprio sicuro di cosa dire su cons and pro? Microsoft ha posto questa domanda a uno dei suoi candidati.

Elenco collegato singolarmente consente di andare in direzione unidirezionale. Mentre la lista doppiamente collegata ha una direzione bidirezionale successiva e precedente.

Ecco una buona immagine che disegna le liste Singly e Doubly Linked.

Tuttavia, come si fa a spiegare i pro ei contro di questi elementi in maniera più ordinata?

Answer 1

Mi viene fatta questa domanda e ho le mie parole ma non sono sicuro di cosa dire di contro e pro?

Tutto si riduce all'utilizzo. C'è un compromesso qui.

L'elenco collegato singolarmente è più semplice in termini di implementazione e in genere ha un requisito di memoria più piccolo in quanto deve solo mantenere il riferimento in avanti del membro in posizione.

L'elenco collegato in modo corretto ha un'iterazione più efficiente, soprattutto se è necessario ripetere iteramente al contrario (che è orribilmente inefficiente con un singolo elenco collegato) e una cancellazione più efficiente di nodi specifici.

Detto questo, poiché questo taggato è .NET, anche i doppi elenchi collegati hanno il vantaggio di essere direttamente nel framework sotto forma della classe LinkedList<T>. Ciò offre un enorme vantaggio in quanto non è necessario implementare, testare e mantenere la propria classe di raccolta.

Answer 2

Vantaggio della lista collegata doppia: Può percorsa nei due sensi

Vantaggio della lista collegata singola: Meno lavori domestici per essere fatto su di aggiornamento/inserimento/cancellazione, meno l'utilizzo della memoria.

Answer 3

Bene, dipende dalla situazione. Se è necessario essere in grado di ottenere rapidamente sia l'elemento precedente che quello successivo da un dato elemento, allora una lista doppiamente collegata è la migliore.

Se è necessario solo ottenere l'elemento successivo da un determinato elemento, allora un elenco collegato singolarmente è sufficiente.

Answer 4

Mentre l'elenco collegato singolarmente utilizza meno memoria per nodo (un puntatore contro due puntatori), l'operazione di eliminazione è O(N) se tutto ciò che si ha è un puntatore al nodo che si desidera eliminare, mentre l'eliminazione doppia è O(1). Esiste un trucco poco conosciuto che consente di eliminare da un elenco collegato singolarmente in O(1), ma l'elenco deve essere circolare affinché funzioni (spostare il contenuto di next nella corrente ed eliminare next).

È possibile utilizzare elenchi collegati in modo discreto in luoghi in cui le liste collegate singolarmente non funzionerebbero (una coda con doppia coda), ma richiedono un po 'più di "pulizia" e risultano leggermente meno efficienti sugli inserimenti.

Answer 5

Anche se questa domanda è già stato risposto, io non sono in qualche modo soddisfatti della risposta (senza offesa), ecco come vorrei rispondere ad essa:

cosa usare - lista semplicemente o doppiamente concatenata dipende cosa intendi raggiungere e limiti del sistema, se ce ne sono.

lista semplicemente legata:

Pro: Semplice nella realizzazione, richiede relativamente minore memoria per l'archiviazione, supponendo che è necessario eliminare/inserire (at) nodo successivo - delezione/inserzione è più veloce.

Contro: non può essere iterato al contrario, è necessario mantenere una maniglia per il nodo principale della lista else, l'elenco andrà perso in memoria. Se si sta eliminando il nodo precedente o si inserisce nel nodo precedente, sarà necessario scorrere l'elenco dalla testa al nodo precedente per poter eseguire tali operazioni - O (N).

- Quindi, deve essere utilizzato quando si dispone di una memoria inferiore e l'obiettivo principale è l'inserimento/eliminazione e non la ricerca di elementi.

lista doppiamente collegata:

Pro: Può essere iterata in avanti così come direzione inversa. Nel caso in cui sia necessario eliminare il nodo precedente, non è necessario passare dal nodo principale, poiché il nodo da eliminare può essere trovato dal puntatore ".precedente".

Contro: relativamente complesso da implementare, richiede più memoria per l'archiviazione (1 puntatore "precedente" per nodo). Inserimenti e cancellazioni sono relativamente più dispendiose in termini di tempo (assegnazione/riassegnazione puntatore "precedente" per i nodi vicini)

- Questo dovrebbe essere usato quando non ci sono limiti o limiti di memoria, e il tuo obiettivo principale è cercare elementi .

Se ci sono altri pro e contro in qualsiasi, per favore sentiti libero di aggiungere, rispondi nei commenti. Grazie!