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

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

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

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

См. также

Примечания

  1. ↑ GC FAQ - draft  (неопр.). Дата обращения: 17 декабря 2012. Архивировано 9 января 2013 года.

Ссылки

  • Пример реализации на C++. 15 April 2011
  • Prokash Sinha, A Memory-Efficient Doubly Linked List // LinuxJournal, Dec 01, 2004
  • Implementation of Enhanced Singly Linked List Equipped with DLL Operations: An Approach towards Enormous Memory Saving / International Journal of Future Computer and Communication, Vol. 3, No. 2, April 2014