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 <->
Недостатки Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы.
Использование Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список. См. также Алгоритм обмена при помощи исключающего ИЛИ Тип данных Примечания
Ссылки Пример реализации на C++. 15 April 2011 Prokash Sinha, A Memory-Efficient Doubly Linked List // LinuxJournal, Dec 01, 2004 Implementation of Enhanced Singly Linked List Equipped with DLL Operations: An Approach towards Enormous Memory Saving / International Journal of Future Computer and Communication, Vol. 3, No. 2, April 2014
Категория:Связные списки