Interested Article - XOR-связный список

XOR-связный список — структура данных , похожая на обычный двусвязный список , однако в каждом элементе хранится только один составной адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка.

Для того, чтобы перемещаться по списку, необходимо иметь адреса двух последовательных элементов.

Выполнение операции XOR над адресом первого элемента и составным адресом, хранящимся во втором элементе, даёт адрес элемента, следующего за этими двумя элементами.

Выполнение операции XOR над составным адресом, хранящимся в первом элементе, и адресом второго элемента даёт адрес элемента, предшествующего этим двум элементам.

Сравнения

C двусвязным списком

Классический двусвязный список хранит отдельно адреса предыдущего и следующего элемента списка, для хранения которых требуется два указателя:

 ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <–

Накладные расходы XOR-связного списка в два раза меньше, так как в нём хранится только один «адрес» — XOR указателей на предыдущий и следующий элементы:

 ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <->

Недостатки

Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора , затруднения при отладке программы .