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

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

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

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

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

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

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

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

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

data-structures linked-list xor-linkedlist
person Pale Blue Dot    schedule 26.10.2009    source источник
comment
Должен также работать с добавлением, хотя плохо обращаться с такими указателями.   -  person starblue    schedule 26.10.2009

Ответы (2)


arrow_upward
5
arrow_downward

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

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

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

person Justin Niessner    schedule 26.10.2009

arrow_upward
5
arrow_downward

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

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

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

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

person Peter Recore    schedule 26.10.2009
comment
Не забывайте, что не все пишут код для ПК. Встроенные системы по-прежнему имеют ограничения по памяти, где этот подход может/должен использоваться (в зависимости от наложенных ограничений). - person Justin Niessner; 26.10.2009
comment
Правда, есть случаи, когда это может быть полезно. Если вы посмотрите на последний абзац цитаты, которую я включил, там это конкретно упоминается. ... накладные расходы на хранение обычно не являются главной проблемой за пределами специализированных встроенных систем ... - person Peter Recore; 27.10.2009
comment
Кроме того, несмотря на то, что это используется только в определенных ситуациях, я все же думаю, что это действительно умная идея. - person Peter Recore; 27.10.2009