Как домашний проект, я пытаюсь реализовать структуру данных неизменяемого списка в Java, сводя при этом к минимуму количество копий; Я знаю о Google Collections, но это не то, что мне нужно, поскольку манипуляции со списком просто возвращают новые копии старого списка.
Я предложил два разных подхода к проблеме; оба основаны на двусвязных списках, например:
[head: element1] <--> [element2] <--> [tail: element3]
Таким образом, каждый список состоит из кортежа {head, tail}.
Сначала рассмотрим простой случай добавления или добавления элемента в список A, в результате чего получается список B:
A: [head: element1] <--> [element2] <--> [tail: element3]
B: [head: element0] <--> [element1] <--> [element2] <--> [tail: element3]
Это O (1). Поскольку перебор списка происходит между головой и хвостом только , A не будет ничего знать о новом элементе, добавленном или добавленном к B.
Интересно, когда мы пытаемся вставить или удалить произвольный элемент в списке.
Подход с индексированными элементами
Каждый список имеет уникальный последовательный идентификатор, начиная с 0. Каждый элемент имеет массив {prev, next} указателей, соответствующих идентификаторам списка:
[element1] <--> [element2] <--> [element3] <--> [element4]
A: [0] <---------> [0] <---------> [0] <---------> [0]
B: [0] <---------> [1] <-------------------------> [1]
C: ...
Таким образом, при удалении element3 из списка A с id = 0 указатели prev или next соответственно с id = 1 (список B) из element2 и element4 являются изменено, чтобы отразить результат запрошенной операции; element1 остается неизменным. При переборе списка с индексом x для получения правильных указателей prev или next, max(elementIdCount, x) используется для вычисления правильного индекса (который будет 0 для element1 и 1 для element2 если мы перебираем, например, B с id = 1).
Добавление или замена элементов производится аналогичным образом. Это также O (1), за исключением случаев, когда необходимо изменить размеры массивов идентификаторов элементов, что должно происходить относительно редко.
Большая проблема с этим, конечно же, сборка мусора - после того, как элемент был добавлен в список, он никогда не будет выпущен до тех пор, пока не будут выпущены ВСЕ ссылки на измененные версии исходного списка. Это можно исправить, сделав копию всего списка, например, на каждые 10 модификаций.
Этот вид списка особенно хорошо подходит для таких конструкций кода:
while (...)
list = list.addElement(...);
, поскольку в любой момент времени хранится только одна ссылка на список.
Итераторский подход
Другой подход заключается в злоупотреблении итераторами, чтобы сделать результирующий список похожим на ожидаемую модифицированную версию; поэтому каждый измененный неизменяемый список содержит ссылку на свой «исходный» список и дополнительный кортеж {operation, element, position}, например:
A: [head: element1] <--> [element2] <--> [tail: element3]
B: source: A, {add, element_to_add, 1}
Итератор
B затем вызывает свой итератор списка источников (в данном случае A), за исключением случаев, когда он встречает элемент, который был изменен (добавлен, удален или заменен), и в этом случае он возвращает этот элемент и затем снова продолжается с исходным итератором.
Очевидным недостатком здесь является то, что глубина вложенного итератора увеличивается с каждой измененной версией списка. Это означает, что время от времени также необходимо делать необработанные копии.
У кого-нибудь есть предложения по улучшению? Кроме того, любые указатели на любые структуры данных, изобретенные в 60-х годах, которые могут быть полезны, приветствуются:)