Per me il problema più grande è:
- Aumentare le dimensioni di un nodo elenco con un puntatore (o riferimenti) aggiuntivo per SLL, 3 per DLL. Questo potrebbe non influire molto sul rendimento se si sta solo assegnando sporadicamente i nodi elenco su tutto lo spazio di memoria, poiché a quel punto non sarebbe importante molto a meno che il nodo fosse solo attorno a 64 byte, ad es. allineato a 64 byte, e il puntatore extra lo rendeva oltre 64 byte, nel qual caso dovevamo raddoppiare i nostri errori di cache. Se stai utilizzando un'attenta strategia di allocazione, più piccolo è il nodo elenco, migliore per l'attraversamento sequenziale e un puntatore in più potrebbe essere un enorme aumento della dimensione relativa solo dall'elenco POV.
- Il più grande vantaggio nel mondo reale degli elenchi concatenati, anche nelle aree critiche per le prestazioni, è spesso la capacità di spostare nodi da una lista a un'altra, dividere le liste in due liste e unirle in tempo costante, ecc. scambio per semplificare qualcosa che non è così complesso.
- Sono stati citati riferimenti circolari e questo potrebbe essere un problema in alcune lingue. Se è come C o C ++, sarebbe un backpointer della lista che non influenzerebbe la raccolta in alcun modo, i nodi sarebbero comunque distrutti quando richiesto.
Quello che consiglio è di smettere di provare a mettere l'implementazione della lista collegata in un nodo. Crea un nodo dati grezzi, un dettaglio di implementazione privata di un elenco che non si preoccupa di fornire molta logica. La tua vita diventerà generalmente molto più semplice se smetti di provare a suddividere le preoccupazioni di funzionalità troppo tra le strutture collegate e i loro nodi: albero vs nodo dell'albero, elenco collegato o nodo elenco, ad es. Metti tutta la logica nella struttura dati in cui hai tutte le informazioni necessarie per fare tutto (sia head puntatore e nodo). moveToFront dovrebbe essere un metodo di elenco collegato piuttosto che un metodo di nodo di elenco. Con questo, non c'è più bisogno di un backpointer.
class DataStructure
{
public:
...
private:
struct Node
{
// Don't put functionality here except maybe a ctor/dtor at
// most if you can avoid it. The distribution of concerns should
// this node have functionality will often make things more
// complex rather than simpler, and also have you reaching for
// backpointers quickly, potentially wanting to waste memory
// and increase the amount of state to maintain superfluously
// (more state usually means more potential for bugs) just
// because we want to put functions into this Node class.
};
...
Node* head_or_root;
};
Un'altra cosa da non sottovalutare è che non c'è un lavoro molto più intelligente che moveToFront possa fare oltre a erase e push to front , quindi potrebbe non valere la pena di avere la funzione extra, a parte una cosa di comodo .
Cioè, a meno che ciò non sia inevitabile, dove i client avrebbero solo un nodo a cui accedono da uno spazio persistente precedentemente memorizzato nella cache, ad es., e nessun accesso alla lista collegata. Se hanno accesso alla lista collegata, allora il modo più semplice è semplicemente evitare di mettere logicamente la logica nei tuoi nodi e renderli privati, tipi di dati C-style struct di cose.
Anche in questo caso spesso semplificherete la vita in questo caso per richiedere semplicemente ai clienti di memorizzare un riferimento a entrambi nodo e lista collegata, invece di sempre memorizzare un backpointer in un nodo (che potrebbe non essere necessario per la maggior parte delle operazioni, facendoci sprecare memoria spesso in luoghi che non ne beneficiano).
Un'altra cosa è che dal momento che Node modella i dettagli di implementazione di un elenco collegato, se puoi evitare di esporre direttamente Node riferimenti e invece fornisci un qualche handle indiretto, come Iterator , ridurrà il rischio di problemi.