Esiste un modo pratico per una struttura di nodi collegati che sia immutabile?

Con gli elenchi in lingue funzionali, lavori quasi sempre con la testa e la coda, il primo elemento e il resto dell'elenco. La pre-registrazione è molto più comune perché, come hai ipotizzato, l'aggiunta richiede la copia dell'intero elenco (o altre strutture di dati pigri che non assomigliano precisamente a un elenco collegato).

Nelle lingue imperative, l'aggiunta è molto più comune, perché tende a sentirsi più naturale semanticamente e non ti interessa invalidare i riferimenti alle versioni precedenti della lista.

Come esempio del perché la preparazione in anticipo non richiede la copia dell'intero elenco, considera di avere:

2 -> 3 -> 4

La previsione di una 1 ti dà:

1 -> 2 -> 3 -> 4

Ma tieni presente che non importa se qualcun altro ha ancora un riferimento a 2 come capo della loro lista, perché l'elenco è immutabile e i link vanno solo in un modo. Non c'è modo di dire che 1 è presente anche se hai solo un riferimento a 2 . Ora, se hai aggiunto un 5 a una lista, dovresti fare una copia dell'intero elenco, perché altrimenti verrebbe visualizzato anche sull'altro elenco.

Si è corretto, l'aggiunta richiede la copia dell'intero elenco se non si desidera modificare i nodi sul posto. Poiché abbiamo bisogno di impostare il puntatore next del (secondo) secondo-ultimo nodo, che in un'impostazione immutabile crea un nuovo nodo, e quindi dobbiamo impostare il puntatore next del penultimo nodo e così via.

Penso che il problema principale qui non sia l'immutabilità, e l'operazione append non è consigliata. Entrambi stanno perfettamente bene nei loro rispettivi domini. Miscelarli è sbagliato: l'interfaccia naturale (efficiente) per una lista immutabile ha enfatizzato la manipolazione in cima all'elenco, ma per gli elenchi mutabili è spesso più naturale creare l'elenco aggiungendo successivamente gli elementi da prima alla fine.

Quindi ti suggerisco di prendere una decisione: vuoi un'interfaccia effimera o una persistente? La maggior parte delle operazioni produce una nuova lista e lascia una versione non modificata accessibile (persistente), oppure scrivi un codice come questo (effimero):

list.append(x);
list.prepend(y);

Entrambe le scelte vanno bene, ma l'implementazione dovrebbe rispecchiare l'interfaccia: una struttura di dati persistente beneficia di nodi immutabili, mentre un effimero ha bisogno della mutabilità interna per soddisfare effettivamente le prestazioni che promette implicitamente. java.util.List e altre interfacce sono effimere: implementarle su un elenco immutabile è inappropriato e in effetti rappresenta un rischio per le prestazioni. I buoni algoritmi su strutture di dati mutabili sono spesso molto diversi dai buoni algoritmi su strutture di dati immutabili, quindi rivestire una struttura di dati immutabile come mutabile (o viceversa) invita algoritmi sbagliati.

Mentre un elenco persistente presenta alcuni svantaggi (nessuna aggiunta efficiente), questo non deve essere un problema serio quando si programma in modo funzionale: molti algoritmi possono essere formulati in modo efficiente spostando la mentalità e utilizzando funzioni di ordine superiore come map o fold (per nominarne due relativamente primitivi), o prepending ripetutamente. Inoltre, nessuno ti obbliga a utilizzare solo questa struttura dati: quando altri (effimeri o persistenti ma più sofisticati) sono più appropriati, usali. Dovrei anche notare che gli elenchi persistenti presentano alcuni vantaggi per altri carichi di lavoro: condividono le loro code, che possono conservare la memoria.

Se hai una lista concatenata, lavorerai con il fronte se più di quanto faresti con la schiena.

I linguaggi funzionali come prolog e haskel offrono modi semplici per ottenere l'elemento frontale e il resto dell'array. L'aggiunta alla parte posteriore è un'operazione O (n) con copie di ciascun nodo.

Come altri hanno sottolineato, hai ragione sul fatto che una lista immutabile collegata singolarmente richiede la copia dell'intero elenco quando si eseguono operazioni di aggiunta.

Spesso puoi usare la soluzione alternativa per implementare il tuo algoritmo in termini di cons (antefatto), quindi invertire l'elenco una volta. Questo ha ancora bisogno di copiare la lista una volta, ma il sovraccarico della complessità è lineare nella lunghezza della lista, mentre usando ripetutamente append si può facilmente ottenere una complessità quadratica.

Elenchi di differenze (vedi ad esempio qui ) sono un'alternativa interessante. Un elenco di differenze avvolge un elenco e fornisce un'operazione di aggiunta in tempo costante. Fondamentalmente lavori con il wrapper fino a quando devi aggiungere, e poi riconvertirli in un elenco quando hai finito. Questo è in qualche modo simile a quello che fai quando usi StringBuilder per costruire una stringa, e alla fine ottieni il risultato come String (immutabile!) Chiamando toString . Una differenza è che un StringBuilder è mutabile, ma una lista di differenze è immutabile. Inoltre, quando converti una lista di differenze in un elenco, devi comunque costruire l'intero nuovo elenco ma, ancora una volta, devi farlo solo una volta.

Dovrebbe essere abbastanza facile implementare una classe DList immutabile che fornisce un'interfaccia simile a quella di Haskell Data.DList .

Devi guardare questo bellissimo video del 2015 React conf da Immutable.js 's creatore Lee Byron. Ti fornirà indicatori e strutture per capire come implementare un efficiente elenco immutabile che non duplica il contenuto. Le idee di base sono: - finché due liste utilizzano nodi identici (stesso valore, stesso nodo successivo), viene utilizzato lo stesso nodo - quando le liste iniziano a differire, viene creata una struttura sul nodo di divergenza, che contiene puntatori al nodo successivo successivo di ogni lista

Questa immagine da un reagire all'esercitazione potrebbe essere più chiara del mio inglese rotto:

Non è strettamente Java, ma ti suggerisco di leggere questo articolo su una struttura dati persistente indicizzata, immutabile, ma performante scritta in Scala:

link

Poiché si tratta di una struttura dati Scala, può essere utilizzata anche da Java (con un po 'più verbosità). Si basa su una struttura dati disponibile in Clojure, e sono sicuro che ci sia anche una libreria Java "nativa" che offre.

Inoltre, una nota su costruzione di strutture di dati immutabili : quello che di solito si vuole è una sorta di "Builder", che consente di "mutare" la struttura dei dati "sotto-costruzione" aggiungendo elementi ad esso (all'interno di un singolo thread); dopo aver finito di appendere, chiami un metodo sull'oggetto "under-construction" come .build() o .result() , che "costruisce" l'oggetto, dandoti una struttura di dati immutabile che puoi quindi condividere tranquillamente.

Un approccio che a volte può essere utile sarebbe avere due classi di oggetti che tengono in lista - un oggetto forward-list con un riferimento final al primo nodo in un elenco forward-linked e un non iniziale - final riferimento che (quando non nullo) identifica un oggetto elenco inverso contenente gli stessi elementi nell'ordine opposto e un oggetto elenco inverso con un riferimento final all'ultimo elemento di un elenco di collegamenti inversi e un riferimento non finale inizialmente null che (quando non null) identifica un oggetto forward-list che mantiene gli stessi elementi in ordine opposto.

La preimportazione di un elemento in una lista di inoltro o l'aggiunta di un elemento a una lista inversa richiederebbe semplicemente la creazione di un nuovo nodo che si collega al nodo identificato dal riferimento final e creando un nuovo oggetto lista dello stesso tipo di l'originale, con un riferimento final a quel nuovo nodo.

Aggiungere un elemento a una lista di inoltro o anteporre a una lista inversa richiederebbe una lista del tipo opposto; la prima volta che viene eseguita con un elenco particolare, dovrebbe creare un nuovo oggetto di tipo opposto e memorizzare un riferimento; ripetere l'azione dovrebbe riutilizzare la lista.

Si noti che lo stato esterno di un oggetto lista sarà considerato uguale se il suo riferimento a un elenco di tipo opposto è nullo o identifica un elenco di ordini opposti. Non ci sarebbe bisogno di fare alcuna variabile final , anche quando si utilizza il codice multi-thread, poiché ogni oggetto lista avrebbe un riferimento final a una copia completa del suo contenuto.

Se il codice su un thread crea e memorizza nella cache una copia invertita di un elenco e il campo in cui tale copia è memorizzata nella cache non è volatile, sarebbe possibile che il codice su un altro thread non visualizzi l'elenco memorizzato nella cache, ma il l'unico effetto negativo sarebbe che l'altro thread avrebbe bisogno di fare del lavoro extra per costruire un'altra copia invertita della lista. Poiché tali azioni nel peggiore dei casi comprometterebbero l'efficienza, ma non influenzerebbero la correttezza, e poiché le variabili volatile creerebbero svantaggi di efficienza, spesso sarebbe meglio avere la variabile non volatile e accettare la possibilità di operazioni ridondanti occasionali.