Связный список XOR

Возможно, вы слышали об односвязном, двусвязном и кольцевом связном списке.

Но что такое XOR-связанный список?

Вы правильно поняли! Это операция XOR и связанный список.

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

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

Вот таблицы битовых операций

Как работает XOR?

Посмотрите на эту таблицу

Если вы все еще не можете понять, прочитайте здесь

Код и подход

Почему именно XOR-связанный список?

  • Он эффективен для памяти (двусвязный список полезнее односвязного, потому что каждый узел имеет адрес предыдущего узла, но он занимает дополнительное пространство, что если мы реализуем двусвязный список в односвязном списке! XOR-связанный список может сделать это волшебство)

  • Вы можете перемещаться в любом направлении с помощью XOR-связанного списка

  • Каждый узел имеет как минимум две части, одна для данных, другая для адреса следующего узла. Связный список XOR хранит XOR адреса предыдущего узла и следующего узла.

Все еще не могу понять… верно?

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

Теперь, что если это первый узел, он будет хранить адреса как NULL XOR NULL, так как его предыдущий и следующий оба являются NULL.

  • Теперь как двигаться назад и вперед, используя только одну секцию для хранения адреса.

Для перемещения вперед — XOR секции адреса текущего узла и предыдущего узла.

Для перемещения назад — XOR адресной секции текущего узла со следующим элементом.

Предположим, у нас есть такой список

NULL <-> 1 <-> 2 <-> 3 <-> NULL

Здесь 1 указывает на NULL и 2, а 2 указывает на 2 1 и 3, аналогично 3 указывает на 2 и NULL.

Пусть head = 1

Проверим, что находится в адресной части узла 1…

Адресная часть узла может быть названа npx, чтобы не повторять адресную часть снова и снова.

Итак, данные в head равны 1, а npx — это XOR предыдущего узла и следующего узла.
Таким образом, npx = XOR(NULL,2), где NULL — предыдущий, а 2 — следующий узел в последовательности.

Аналогично для узла 2, npx = XOR(1, 3), где 1 — предыдущий, а 3 — следующий узел.

Давайте проверим, как определить следующий узел в последовательности при создании XOR-связанного списка с нуля.

  1. Предположим, мы создали узел head, вставили в него данные и отметили его npx как NULL

для удобства прочитайте приведенный ниже код


struct Node
{
    int data;
    struct Node* npx;

    Node(int x){
        data = x;
        npx = NULL;
    }
};

Войти в полноэкранный режим Выйти из полноэкранного режима

Итак, узел 1 имеет данные 1 и npx = XOR предыдущего и следующего, то есть XOR NULL и NULL, поскольку это первый узел в нашем списке, поэтому его npx = NULL, так как XOR от (NULL, NULL) равен NULL.

  1. Вставьте узел со значением 2 в этот список
  • Создайте узел, добавьте значение 2
  • Для npx мы знаем, что он будет XOR предыдущего и следующего узлаВы подумаете, что теперь мы должны отслеживать его предыдущее значение при каждом обновлении списка. Но мы не будем использовать для этого дополнительное пространство, вместо этого мы будем обновлять голову каждый раз, когда вставляем новый узел, поэтому после вставки второго узла голова переместится на этот узел и больше не будет указывать на первый.

Таким образом, npx для узла 2 является XOR из (head->npx,NULL), поэтому теперь он указывает на head->npx как на предыдущий узел, а следующий узел не существует, следовательно, NULL для следующего узла.

  • Но здесь снова есть изюминка, теперь head должен указывать на этот новый узел и в узле head (который здесь все еще является узлом 1), должен быть узел 2 в его npx вместо того, чтобы иметь NULL XOR NULL.

Поэтому обновите npx узла head, поставив XOR узла 2 и XOR head->npx и NULL, который оценивается в head->npx, и в итоге у нас остается head->npx XOR узла 2, и мы успешно обновили npx узла 1.

Теперь сделаем head = узел 2

  • И да, мы закончили с этим, аналогичным образом мы добавим узел 3.

Позвольте мне обсудить это более четко

  1. npx узла 1 — NULL XOR NULL
  2. npx узла 2 — 1 XOR NULL, обновление для узла 1 npx = NULL XOR 2
  3. npx узла 3 — 2 XOR NULL, обновление для узла2 npx = узел 2 XOR NULL

Как перемещаться вперед и назад

  1. Перемещение вперед

XOR npx текущего узла и предыдущего узла

Предположим, вы находитесь на узле 1, хотите переместиться на узел 2, поэтому выполните XOR следующим образом
npx текущего узла -> NULL XOR 2 = 2
2 XOR NULL = 2, и следующим узлом в последовательности будет 2.

  • Переход к узлу 3 из узла 2

XOR npx узла 2 и узла 1
npx узла 1 = NULL XOR 2 = 2
npx узла 2 = 1 XOR 2 = 3

Как 1 XOR 2 = 3 и NULL XOR 2 = 2

1 = 0001
2 = 0010

0001 ^ 0010 = 0011

и что такое 0011 в десятичном исчислении, это 3

NULL = 0000
2 = 0010

0000 ^ 0010 = 0010, что в десятичной системе равно 2.

Надеюсь, вы получили представление о том, как мы обходим и вставляем узлы в этот список.

Смотрите код для лучшего понимания
Этот код является решением проблемы в GFG

struct Node
{
    int data;
    struct Node* npx;

    Node(int x){
        data = x;
        npx = NULL;
    }
};

Utility function to get XOR of two Struct Node pointer
use this function to get XOR of two pointers
struct Node* XOR (struct Node *a, struct Node *b)
{
    return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
*/

// function should insert the data to the front of the list



struct Node* insert(struct Node *head, int data)
{
   struct Node *new_node = new Node(data);
   new_node->npx = XOR(head,NULL);
   if (head!= NULL)
   {
   struct Node *next = XOR(head->npx, NULL);
   head->npx = XOR(new_node, next);
   }
   head = new_node;
}

vector<int> printList (struct Node *head)
{
   struct Node *curr = head;
   struct Node *prev = NULL;
   struct Node *next;

   vector<int> res;
   while (curr != NULL)
   {
   res.push_back(curr->data);
   next = XOR(prev, curr->npx);
   prev = curr;
   curr = next;
   }
   return res;
}

Войдите в полноэкранный режим Выход из полноэкранного режима

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *