data-structures XOR链接列表


XOR链接列表也称为内存高效链接列表 。它是双重链表的另一种形式。这高度依赖于XOR逻辑门及其属性。

为什么这称为内存高效链接列表?

之所以这样称呼是因为它使用的内存少于传统的双向链表。


这与双重链接列表不同吗?

是的 ,确实如此。

双向链表是存储两个指针,指向下一个节点和前一个节点。基本上,如果你想返回,你会转到back指针指向的地址。如果你想前进,你会转到next指针指向的地址。就像是:

在此处输入图像描述

内存高效的链接列表 ,或者XOR链接列表只有一个指针而不是两个。这将先前的地址(addr(prev)) XOR (^)存储到下一个地址(addr(next))。如果要移动到下一个节点,可以执行某些计算,并查找下一个节点的地址。这与前一个节点相同。它像是:

在此处输入图像描述


它是如何工作的?

要了解链表的工作原理,您需要知道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 。看起来像这样

从Head移动到下一个节点

假设您现在位于第一个节点或节点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>
 
// 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 */
    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 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked list in forward direction
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)
    {
        // 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
       head-->40<-->30<-->20<-->10   */
    struct node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // print the created list
    printList (head);
 
    return (0);
}

上面的代码执行两个基本功能:插入和横向。

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

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

请注意,指针的XOR不是由C / C ++标准定义的。因此,上述实现可能无法在所有平台上运行。


参考

请注意,我从主要的答案中获取了很多内容。