- 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 <->
Недостатки
Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы[1].
Использование
Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.
Примечания
Ссылки
См. также
Категория:- Связные списки
Wikimedia Foundation. 2010.