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

Материал из Википедии — свободной энциклопедии

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