Меню
Главная
Случайная статья
Настройки
|
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранится только один составной адрес — результат выполнения побитовой операции исключающего «ИЛИ» (XOR) над адресами предыдущего и следующего элементов списка.
Для того, чтобы перемещаться по списку, необходимо иметь адреса двух последовательных элементов.
Выполнение побитовой операции XOR над адресом первого элемента и составным адресом, хранящимся во втором элементе, даёт адрес элемента, следующего за этими двумя элементами.
Выполнение побитовой операции XOR над составным адресом, хранящимся в первом элементе, и адресом второго элемента даёт адрес элемента, предшествующего этим двум элементам.
Содержание
Сравнения
C двусвязным списком
Классический двусвязный список хранит отдельно адреса предыдущего и следующего элемента списка, для хранения которых требуется два указателя:
... A B C D E ...
–> next –> next –> next –>
<– prev <– prev <– prev <–
Накладные расходы XOR-связного списка в два раза меньше, так как в нём хранится только один «адрес» — побитовый XOR указателей на предыдущий и следующий элементы:
... A B C D E ...
<–> AC <-> BD <-> CE <->
Недостатки
Из недостатков можно упомянуть более сложную реализацию, невозможность использования стандартного сборщика мусора, затруднения при отладке программы[1].
Использование
Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.
См. также
Примечания
- GC FAQ - draft (неопр.). Дата обращения: 17 декабря 2012. Архивировано 9 января 2013 года.
Ссылки
|
|