Xor-связанный список

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

Сравнения

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

В сравнении с обычным двусвязным списком, XOR список расходует в два раза меньше памяти для хранения связей между элементами.

Недостатки

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

Использование

Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.

См. также

• Тип данных

Ссылки