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

Недостатки

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

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

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

См. также

• Алгоритм обмена при помощи исключающего ИЛИ
• Тип данных

Ссылки

• [blog.wsensors.com/?p=177 Пример реализации на C++.] 15 April 2011
• Prokash Sinha, [www.linuxjournal.com/article/6828 A Memory-Efficient Doubly Linked List] // LinuxJournal, Dec 01, 2004
• [www.ijfcc.org/papers/276-E1045.pdf 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

Отрывок, характеризующий XOR-связный список

Знакомая павлоградцам, с высокоподнятыми плечами, фигура Жеркова (он недавно выбыл из их полка) подъехала к полковому командиру. Жерков, после своего изгнания из главного штаба, не остался в полку, говоря, что он не дурак во фронте лямку тянуть, когда он при штабе, ничего не делая, получит наград больше, и умел пристроиться ординарцем к князю Багратиону. Он приехал к своему бывшему начальнику с приказанием от начальника ариергарда.
– Полковник, – сказал он с своею мрачною серьезностью, обращаясь ко врагу Ростова и оглядывая товарищей, – велено остановиться, мост зажечь.
– Кто велено? – угрюмо спросил полковник.
– Уж я и не знаю, полковник, кто велено , – серьезно отвечал корнет, – но только мне князь приказал: «Поезжай и скажи полковнику, чтобы гусары вернулись скорей и зажгли бы мост».
Вслед за Жерковым к гусарскому полковнику подъехал свитский офицер с тем же приказанием. Вслед за свитским офицером на казачьей лошади, которая насилу несла его галопом, подъехал толстый Несвицкий.
– Как же, полковник, – кричал он еще на езде, – я вам говорил мост зажечь, а теперь кто то переврал; там все с ума сходят, ничего не разберешь.
Полковник неторопливо остановил полк и обратился к Несвицкому:
– Вы мне говорили про горючие вещества, – сказал он, – а про то, чтобы зажигать, вы мне ничего не говорили.
– Да как же, батюшка, – заговорил, остановившись, Несвицкий, снимая фуражку и расправляя пухлой рукой мокрые от пота волосы, – как же не говорил, что мост зажечь, когда горючие вещества положили?
– Я вам не «батюшка», господин штаб офицер, а вы мне не говорили, чтоб мост зажигайт! Я служба знаю, и мне в привычка приказание строго исполняйт. Вы сказали, мост зажгут, а кто зажгут, я святым духом не могу знайт…