Design migliore per una lista generica doppiamente collegata attorno alla quale ho intenzione di creare wrapper diversi?

Vorrei iniziare rispondendo alla tua domanda:

La memorizzazione della dimensione dell'elemento per nodo o per elenco non renderà il codice più o meno complesso in un modo o nell'altro. L'unica vera differenza sarà che chiunque chiami per aggiungere un nodo dovrà passare una dimensione una volta o ogni volta e la quantità di spazio di archiviazione richiesta per ciascun nodo potrebbe aumentare di un valore extra di size_t di byte. Il compromesso tra l'utilizzo di meno memoria e meno flessibilità rispetto all'utilizzo di più memoria e maggiore flessibilità è qualcosa che dovresti valutare caso per caso.

Lasciatemi concludere suggerendo un'alternativa:

Se stai implementando questo strumento come strumento generico sulla falsariga dei contenitori generici STL o Java, ti suggerirei di adottare una virata completamente diversa e non tentare di fare nulla con i puntatori che ti vengono forniti. Basta archiviarli nella tua lista e restituirli come è attraversato.

Il tuo approccio allocate-and-copy si basa sul presupposto che ciò che viene archiviato sono strutture semplici, con un paio di problemi:

• La mia struttura potrebbe avere ulteriori riferimenti alla memoria allocata. Se sto utilizzando il tuo elenco come spazio di archiviazione principale per i miei dati e te ne imposti a free() quando chiamo la tua funzione cleanup() , non ho alcuna possibilità di liberare memoria aggiuntiva a meno che non attraversi l'intero cosa in anticipo e fare la mia pulizia. Se così fosse, potrei anche fare un attraversamento e rimuovere i nodi uno alla volta. Puoi ovviare a questo problema fornendo un hook per lo smaltimento, che chiameresti ogni volta che desideri deselezionare un nodo.

• Il puntatore che ti porto potrebbe non essere un puntatore a una struttura. Ad esempio, potrei avere un grande blocco di memoria e voler memorizzare un elenco di indicatori di posizione o qualcosa che implica semplicemente il puntamento in vari punti del blocco. La tua implementazione richiede che ti dia un posto dove copiare i dati da / a durante le operazioni push, pop e peek. Dovrei definire un'altra struttura con un singolo membro per mantenere il mio valore del puntatore. È imbarazzante e scomodo. (Potresti, comunque, scrivere un wrapper che fa allocare-e-copiare e usa l'implementazione solo dei puntatori.)

Forse dovresti dare un'occhiata all'implementazione di liste collegate intrusive usate nel kernel di Linux. La fonte può essere sfogliata qui .

Un design intrusivo ha il vantaggio che qualsiasi tipo può essere inserito in una lista solo includendo un elemento lista nella definizione della struttura.

Gli svantaggi includono sintassi leggermente più macchinosa (una questione di preferenze personali, ovviamente) e l'obbligo di includere più membri dello stesso tipo quando i dati devono essere inseriti in più di una lista.

Gli elenchi intrusivi sono utili soprattutto quando hai bisogno di un numero limitato di elenchi e soprattutto quando il tuo modulo / app si concentra sull'aggiunta e la rimozione di nodi da un elenco. Un design diverso potrebbe essere più adatto se il tuo codice ha bisogno di gestire elenchi locali o usa e getta. La prima considerazione è vera per la maggior parte degli usi delle liste nel kernel.