Проблема в понимании связанного списка XOR

Question

Я читаю XOR связанный список (из Википедии). Но у меня возникли некоторые проблемы с его пониманием.

Я не получаю следующий абзац.

Чтобы начать обход списка в любом направлении с некоторой точки, вам нужен адрес двух последовательных элементов, а не только одного. Если адреса двух последовательных элементов меняются местами, вы в конечном итоге пройдете список в обратном направлении.

У меня есть несколько вопросов по этому поводу:

1. Как он (сам список ссылок XOR) на самом деле работает?

   (Было бы замечательно, если бы вы обосновали свой ответ, приведя несколько примеров.i.e взяв несколько адресов, а затем делая некоторые вычисления соответственно.)

2. Как я могу это реализовать? Краткое представление о реализации.

3. Практически, где это находится или может быть использовано? Это действительно полезно, как кажется?

Answer 1

3. Этот вид связанного списка в настоящее время не очень практичен. Его главное преимущество - экономия памяти, которая обычно дешевая и в изобилии. В статье в Википедии, на которую вы ссылаетесь, довольно четко изложены недостатки:

Эта форма связанного списка может быть нецелесообразной:

• Средства отладки общего назначения не могут следовать цепочке XOR, что затрудняет отладку;
• Ценой уменьшения использования памяти является увеличение сложности кода, что делает обслуживание более дорогим;
• Большинство схем сборки мусора не работают со структурами данных, которые не содержат литеральных указателей;
• XOR указателей не определено в некоторых контекстах (например, язык C), хотя многие языки обеспечивают какое-то преобразование типов между указателями и целыми числами;
• Указатели будут нечитаемыми, если никто не просматривает список - например, если указатель на элемент списка содержался в другой структуре данных;
• При обходе списка вам необходимо запомнить адрес ранее посещенного узла, чтобы вычислить адрес следующего узла.

Компьютерные системы имеют все больше дешевая и обильная память, и затраты на хранение обычно не главный вопрос за пределами специализированной встроенные системы. Где это еще желательно уменьшить накладные расходы связанный список, развертывание обеспечивает более практический подход (а также другие преимущества, такие как увеличение кеша производительность и превышение скорости доступ).

Answer 2

1. Вышеприведенная процедура работает путем сохранения адресов как следующих, так и предыдущих элементов в одном поле (назовем его A). Поэтому, чтобы получить значение следующего элемента в списке, вы берете адрес другого элемента, который у вас есть (вот почему вам нужно два ... назовите его B). Чтобы найти адрес следующего элемента, достаточно просто A XOR B, чтобы получить C (местоположение следующего элемента).

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

3. Может использоваться везде, где вы используете двойной связанный список (связанный список XOR сохранит память). Предостережение заключается в том, что вам нужно иметь два последовательных элемента списка для прохождения через элементы.