Po przeczytaniu tego pytaniaNiezmienne lub niezmienne? i czytając odpowiedzi na moje poprzednie pytania dotyczące niezmienności, wciąż jestem trochę zdziwiony skuteczną implementacją prostej listy LinkedList, która jest niezmienna. Pod względem tablicy tha wydaje się być łatwa - skopiuj tablicę i zwróć nową strukturę na podstawie tej kopii.

Podobno mamy ogólną klasę węzła:

<code>class Node{
    private Object value;
    private Node next;
}
</code>

I klasa LinkedList oparta na powyższym, pozwalająca użytkownikowi dodawać, usuwać itp. Teraz, jak zapewnilibyśmy niezmienność? Czy powinniśmy rekurencyjnie kopiować wszystkie odniesienia do listy, gdy wstawiamy element?

Ciekawi mnie także odpowiedźNiezmienne lub niezmienne? wspominając o optymalizacji cerain prowadzącej do log (n) czasu i przestrzeni za pomocą drzewa binarnego. Czytałem też gdzieś, że dodanie elem do frontu również wynosi 0 (1). To bardzo mnie zastanawia, jak gdybyśmy nie dostarczali kopii odnośników, w rzeczywistości modyfikujemy te same struktury danych w dwóch różnych źródłach, co przerywa niezmienność ...

Czy któraś z twoich odpowiedzi będzie działać na listach podwójnie powiązanych? Z niecierpliwością czekam na wszelkie odpowiedzi / wskazówki do innych pytań / rozwiązań. Z góry dziękuje za twoją pomoc.