удалить узел в списке ссылок xor

Question

Я нашел приведенный ниже код на C ++, который вставляет и пересекает список ссылок XOR.

Как нам удалить узел? Как кажется, когда мы удаляем узел, все адреса узла в списке должны обновляться?

Или моя интуиция на этот раз не верна?

https://en.wikipedia.org/wiki/XOR_linked_list

https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/

Answer 1

Нет, вы не обновляете все адресов, а только соседние.Посмотрите на список примеров;давайте расширим его еще на два узла:

z        A         B         C         D         E         F
   <–>  z⊕B  <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->  D⊕F  <->

Значения only , использующие адрес C, соответствуют значениям B и D.Если мы удалим C, нам нужно будет только изменить эти значения следующими движущимися:

B.link = B.link ⊕ C ⊕ D
D.link = D.link ⊕ C ⊕ B

Это дает нам

z        A         B         D         E         F
   <–>  z⊕B  <–>  A⊕D  <->  B⊕E  <->  D⊕F  <->

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