# data-structures XOR链接列表

## 例

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      |
|-------------|------------|------------|
``````

``````Address of Next Node = Address of Previous Node ^ pointer in the current Node
``````

``````addr (next) = addr (prev) ^ (0 ^ addr (next))
``````

``````addr (next) = 0 ^ (0 ^ addr (next))
``````

``````addr (next) = 0 ^ 0 addr (next)
``````

``````addr (next) = 0 ^ addr (next)
``````

``````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)
``````

``````addr (next) = 0 ^ addr (next)
``````

``````addr (next) = addr (next)
``````

``````addr (prev) = temp_addr
``````

# C中的示例代码

``````/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>

// Node structure of a memory efficient doubly linked list
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)
{
// Allocate memory for new node
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 */

/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
{
// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
// it with NULL, we get next
struct node* next = XOR((*head_ref)->npx,  NULL);
}

}

// prints contents of doubly linked list in forward direction
{
struct node *prev = NULL;
struct node *next;

printf ("Following are the nodes of Linked List: \n");

while (curr != NULL)
{
// print current node
printf ("%d ", curr->data);

// get address of next node: curr->npx is next^prev, so curr->npx^prev
// will be next^prev^prev which is next
next = XOR (prev, curr->npx);

// update prev and curr for next iteration
prev = curr;
curr = next;
}
}

// Driver program to test above functions
int main ()
{
/* Create following Doubly Linked List

// print the created list

return (0);
}
``````

• 插入：这由功能`insert`执行。这会在开头插入一个新节点。调用此函数时，它将新节点作为头，将前一个头节点作为第二个节点。

• 遍历：这是由函数`printList`执行的。它只是遍历每个节点并打印出值。