differenza tra liste doppie collegate e lista doppiamente collegata

Question

Non capisco la differenza tra una lista doppia e doppia collegata.

Qual è la principale differenza tra i due?

Answer 1

Una lista doppiamente collegata è una lista in cui gli elementi hanno puntatori a entrambi gli elementi prima e dopo nell'elenco.

Un elenco a doppia estremità è dalla mia comprensione lo stesso di un deque. Questa è una coda da cui puoi aggiungere e rimuovere elementi sia dall'alto che dal basso.

Answer 2

In una lista doppiamente collegata, ciascun nodo ha due puntatori. Uno verso il suo prossimo nodo e un altro verso il suo nodo precedente.

In un elenco doppio attacco legato, ogni nodo ha un solo puntatore che punta alla sua prossima nodo. La sua differenza rispetto alla lista collegata single-ended è che invece di un solo nodo "head", contiene due puntatori di questo tipo ("first" e "last"), quindi qualcuno è in grado di inserire elementi da elencare da entrambe le estremità di esso.

(Ultima immagine non è chiaro, ma cattura il punto delle due estremità.)

Answer 3

singolo collegato è una direzione modo e utilizza meno memoria e la complessità di inserimento è Sopra). Mentre il doppio collegamento è bidirezionale (successivo e precedente), utilizza più memoria rispetto alla singola lista e la complessità dell'inserimento e dell'eliminazione è O (n).