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

XOR-зв'язний список – структура даних, схожа на звичайний Двобічно зв'язаний список, однак у кожному елементі зберігається лише одна складова адреса – результат виконання операції XOR над адресами попереднього та наступного елементів списку.

Звичайний Двобічно зв'язаний список, в середині кожного елемента списка має інформацію про адреси наступного і попереднього елемента списку.

 ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <– 

XOR-зв'язний список стискає дві адреси в одну комірку, яку розраховує її як результат операції XOR над сусідніми.

 ... A B C D E ... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌ 

Щоб переходити між елементами списку, необхідно мати адреси двох послідовних елементів.

Недоліки

• Складність реалізації та відладки.
• Зменьшення розміру використання пам'яті досягається високою ціною складності реалізації, і обмеженнями що з'являються.
• Не всі мови програмування підтримують XOR для таких структура як вказівник, а також маніпуляції з адресою.
• Більшість механізмів збирання сміття з пам'яті не працюють з такими структурами, де вказівник не є саме вказівником-літералом.
• Під час переходу по списку, адреса попереднього вузла необхідна для обчислення адреси наступного вузла, а вказівники не зчитаються, якщо список не сканується від початку. Може бути оптимізовано, якщо наприклад вказівник на деякий середній елемент списку міститься в іншій структурі даних.
• XOR-зв'язний список не надає деяких важливих переваг двобічно зв'язаних списків, таких як можливість видалення вузла зі списку, знаючи лише його адресу, або можливість вставити новий вузол перед або після існуючого вузла, знаючи лише адресу існуючого вузла.

Використання

Що стосується структур зв'язаних списків, але з економією пам'яті на вказівниках існує Розгорнутий зв'язний список. Тому з урахуванням недоліків, цей метод зберігання списків не є популярним.

Однак, узагальненя концепції використання оператора XOR, з списка до дерева, є основою для Двійкове дерево пошуку