data-structures 异或链接列表
示例
一个异或链表也被称为内存效率链表。这是双向链接列表的另一种形式。这高度依赖于XOR逻辑门及其属性。
为什么将其称为“内存有效链表”？
之所以这样称呼，是因为与传统的双向链表相比，它使用的内存更少。
这与双向链接列表不同吗？
是的，是的。
甲双链表正存储两个指针，它指向下一个及前一个节点。基本上，如果要返回，则转到back指针指向的地址。如果要前进，请转到next指针指向的地址。就像是：
甲内存效率链表，或即链表XOR是仅具有一个指针，而不是两个。这将前一个地址（addr(prev)）与下一个地址（addr(next)）XOR（^）进行存储。当您想移至下一个节点时，您需要进行某些计算，然后找到下一个节点的地址。转到上一个节点是相同的。它就像是：
它是如何工作的？
要了解链表的工作原理，您需要了解XOR（^）的属性：
|-------------|------------|------------| | Name | Formula | Result | |-------------|------------|------------| | Commutative | A ^ B | B ^ A | |-------------|------------|------------| | Associative | A ^ (B ^ C)| (A ^ B) ^ C| |-------------|------------|------------| | None (1) | A ^ 0 | A | |-------------|------------|------------| | None (2) | A ^ A | 0 | |-------------|------------|------------| | None (3) | (A ^ B) ^ A| B | |-------------|------------|------------|
现在，我们将其放在一边，看看每个节点存储了什么。
第一个节点或头存储，0^addr(next)因为没有先前的节点或地址。看起来像这样。
然后第二个节点存储addr(prev)^addr(next)。看起来像这样。
列表的尾部没有任何下一个节点，因此存储addr(prev)^0。看起来像这样。
从头移动到下一个节点
假设您现在位于第一个节点或节点A上。现在您要移至节点B。这是这样做的公式：
Address of Next Node = Address of Previous Node ^ pointer in the current Node
因此，这将是：
addr (next) = addr (prev) ^ (0 ^ addr (next))
由于这是头，因此先前的地址将只是0，因此：
addr (next) = 0 ^ (0 ^ addr (next))
我们可以删除括号：
addr (next) = 0 ^ 0 addr (next)
使用该none(2)属性，我们可以说0^0它将始终为0：
addr (next) = 0 ^ addr (next)
使用该none(1)属性，我们可以将其简化为：
addr (next) = addr (next)
您获得了下一个节点的地址！
从一个节点移动到下一个节点
现在，我们处于一个中间节点，该节点具有上一个和下一个节点。
让我们应用公式：
Address of Next Node = Address of Previous Node ^ pointer in the current Node
现在替换值：
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
删除括号：
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
使用该none(2)属性，我们可以简化：
addr (next) = 0 ^ addr (next)
使用该none(1)属性，我们可以简化：
addr (next) = addr (next)
你明白了！
从一个节点移动到您先前所在的节点
如果您不理解标题，则基本上意味着如果您在节点X上，并且现在已移至节点Y，则您想返回先前访问的节点，或者基本上是节点X。
这不是一项繁琐的任务。请记住，我之前已经提到过，您将原来的地址存储在一个临时变量中。因此，您要访问的节点的地址位于一个变量中：
addr (prev) = temp_addr
从一个节点移动到上一个节点
这与上面提到的不同。我的意思是说，您在节点Z上，现在您在节点Y上，并且想要转到节点X。
这几乎与从一个节点移至下一个节点相同。反之亦然。编写程序时，将使用与从一个节点移至下一个节点时提到的步骤相同的步骤，只是在列表中查找的元素要比查找下一个元素的早。
C中的示例代码
/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
//高效内存双链表的节点结构
struct node
{
int data;
struct node* npx; /* XOR of next and previous node */
};
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
/* Insert a node at the begining of the XORed linked list and makes the
newly inserted node as head */
void insert(struct node **head_ref, int data)
{
//为新节点分配内存
struct node *new_node = (struct node *) malloc (sizeof (struct node) );
new_node->data = data;
/* Since new node is being inserted at the begining, npx of new node
will always be XOR of current head and NULL */
new_node->npx = XOR(*head_ref, NULL);
/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
if (*head_ref != NULL)
{
// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
//NULL，我们得到下一个
struct node* next = XOR((*head_ref)->npx, NULL);
(*head_ref)->npx = XOR(new_node, next);
}
//换头
*head_ref = new_node;
}
//向前打印双向链表的内容
void printList (struct node *head)
{
struct node *curr = head;
struct node *prev = NULL;
struct node *next;
printf ("Following are the nodes of Linked List: \n");
while (curr != NULL)
{
//打印当前节点
printf ("%d ", curr->data);
// get address of next node: curr->npx is next^prev, so curr->npx^prev
//将是下一个^上一个^上一个是下一个
next = XOR (prev, curr->npx);
//更新下一个和下一个迭代的curr
prev = curr;
curr = next;
}
}
//驱动程序测试上述功能
int main ()
{
/* Create following Doubly Linked List
head-->40<-->30<-->20<-->10 */
struct node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
//打印创建的列表
printList (head);
return (0);
}上面的代码执行两个基本功能：插入和横向。
插入：这是通过函数执行的insert。这将在开始处插入一个新节点。调用此函数时，它将新节点作为头，并将先前的头节点作为第二节点。
遍历：这是通过功能执行的printList。它只是遍历每个节点并输出值。
请注意，C/C++标准未定义指针的XOR。因此，上述实现可能无法在所有平台上都有效。
参考文献
https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/
http://www.geeksforgeeks.org/xor-linked-list-a-memory-ficient-doubly-linked-list-set-2/
请注意，我从main自己的答案中获得了很多内容。