XOR链表–一种内存高效的双链表|集1-yiteyi-C++库

普通的双链表需要两个地址字段的空间来存储上一个和下一个节点的地址。如下图所示。从下图可以看出，前一个节点的地址由前一个指针保留并进行计算，而下一个节点的地址在指针之后。

null

图片[1]-XOR链表–一种内存高效的双链表|集1-yiteyi-C++库

现在有了一个内存高效的双链表版本，它可以在每个节点的地址字段中只使用一个空格来创建。这种节省内存的双链表被称为XOR链表，或者称为节省内存的链表，因为链表使用按位XOR操作来为一个地址节省空间。在XOR链表中，每个节点都存储上一个和下一个节点的地址的XOR，而不是存储实际的内存地址。

考虑上述双链表。以下是双链表的普通和XOR（或高效内存）表示。

图片[2]-XOR链表–一种内存高效的双链表|集1-yiteyi-C++库

现在，我们将讨论这两种方法，以确定XOR表示与普通表示的行为有何不同。

普通代表
异或列表表示

方式1：普通代表

Node A: prev = NULL, next = add(B) // previous is NULL and next is address of B Node B: prev = add(A), next = add(C) // previous is address of A and next is address of C Node C: prev = add(B), next = add(D) // previous is address of B and next is address of D Node D: prev = add(C), next = NULL // previous is address of C and next is NULL

方式2：异或列表表示

让我们调用XOR表示npx中的地址变量（下一个和上一个的XOR）

在遍历XOR链表时，我们可以正向和反向遍历XOR链表。在遍历列表时，我们需要记住之前访问的节点的地址，以便计算下一个节点的地址。

例如：当我们在节点C时，我们必须有地址B.XOR的add（B）和 npx C的函数给了我们加法（D）。

插图：

Node A: npx = 0 XOR add(B) // bitwise XOR of zero and address of B Node B: npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C Node C: npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D Node D: npx = add(C) XOR 0 // bitwise XOR of address of C and 0

npx(C) XOR add(B) => (add(B) XOR add(D)) XOR add(B) // npx(C) = add(B) XOR add(D)=> add(B) XOR add(D) XOR add(B) // a^b = b^a and (a^b)^c = a^(b^c)=> add(D) XOR 0  // a^a = 0=> add(D)     // a^0 = a

类似地，我们可以向后遍历列表。现在直接进入实现部分，以便更好地理解。

实施：

实例

C++

                         // C++ Implementation of Memory                       
                         // efficient Doubly Linked List                       
           
                         // Importing libraries                       
                         #include <bits/stdc++.h>                       
                         #include <cinttypes>                       
           
                         using                                     namespace                                     std;                       
           
                         // Class 1                       
                         // Helepr class(Node structure)                       
                         class                                     Node {                       
                                                 public                                     :                                     int                                     data;                       
                                                 // Xor of next node and previous node                       
                                                 Node* xnode;                       
                         };                       
           
                         // Method 1                       
                         // It returns Xored value of the node addresses                       
                         Node* Xor(Node* x, Node* y)                       
                         {                       
                                                 return                                     reinterpret_cast                                     <Node*>(                       
                                                 reinterpret_cast                                     <                                     uintptr_t                                     >(x)                       
                                                 ^                                     reinterpret_cast                                     <                                     uintptr_t                                     >(y));                       
                         }                       
           
                         // Method 2                       
                         // Insert a node at the start of the Xored LinkedList and                       
                         // mark the newly inserted node as head                       
                         void                                     insert(Node** head_ref,                                     int                                     data)                       
                         {                       
                                                 // Allocate memory for new node                       
                                                 Node* new_node =                                     new                                     Node();                       
                                                 new_node -> data = data;                       
           
                                                 // Since new node is inserted at the                       
                                                 // start , xnode of new node will always be                       
                                                 // Xor of current head and NULL                       
                                                 new_node -> xnode = *head_ref;                       
           
                                                 // If linkedlist is not empty, then xnode of                       
                                                 // present head node will be Xor of new node                       
                                                 // and node next to current head */                       
                                                 if                                     (*head_ref != NULL) {                       
                                                 // *(head_ref)->xnode is Xor of (NULL and next).                       
                                                 // If we Xor Null with next we get next                       
                                                 (*head_ref)                       
                                                 -> xnode = Xor(new_node, (*head_ref) -> xnode);                       
                                                 }                       
           
                                                 // Change head                       
                                                 *head_ref = new_node;                       
                         }                       
           
                         // Method 3                       
                         // It simply prints contents of doubly linked                       
                         // list in forward direction                       
                         void                                     printList(Node* head)                       
                         {                       
                                                 Node* curr = head;                       
                                                 Node* prev = NULL;                       
                                                 Node* next;                       
           
                                                 cout <<                                     "The nodes of Linked List are: "                                     ;                       
           
                                                 // Till condition holds true                       
                                                 while                                     (curr != NULL) {                       
                                                 // print current node                       
                                                 cout << curr -> data <<                                     " "                                     ;                       
           
                                                 // get address of next node: curr->xnode is                       
                                                 // next^prev, so curr->xnode^prev will be                       
                                                 // next^prev^prev which is next                       
                                                 next = Xor(prev, curr -> xnode);                       
           
                                                 // update prev and curr for next iteration                       
                                                 prev = curr;                       
                                                 curr = next;                       
                                                 }                       
                         }                       
           
                         // Method 4                       
                         // main driver method                       
                         int                                     main()                       
                         {                       
                                                 Node* head = NULL;                       
                                                 insert(&head, 10);                       
                                                 insert(&head, 100);                       
                                                 insert(&head, 1000);                       
                                                 insert(&head, 10000);                       
           
                                                 // Printing the created list                       
                                                 printList(head);                       
           
                                                 return                                     (0);                       
                         }                       

输出

The nodes of Linked List are: 10000 1000 100 10

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章