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].

Использование[править | править вики-текст]

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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

См. также[править | править вики-текст]