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

Question

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

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

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

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

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

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

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

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

Answer 1

<Ол>

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

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

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

Answer 2

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

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

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

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