XOR 連結列表

一個異或連結串列也被稱為記憶體效率連結串列。它是雙重連結串列的另一種形式。這高度依賴於 XOR 邏輯閘及其屬性。

為什麼這稱為記憶體高效連結列表？

之所以這樣稱呼是因為它使用的記憶體少於傳統的雙向連結串列。

這與雙重連結列表不同嗎？

是的，確實如此。

一個雙連結串列正儲存兩個指標，其在下一和前一節點指向。基本上，如果你想回去，你會轉到 back 指標指向的地址。如果你想繼續前進，你會轉到 next 指標指向的地址。就像是：

http://i.stack.imgur.com/t1RDM.gif

一個記憶體效率連結串列，或即異或連結串列是僅具有一個指標，而不是兩個。這將先前的地址（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++標準定義的。因此，上述實現可能無法在所有平臺上執行。

參考

• 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-efficient-doubly-linked-list-set-2/

請注意，我從主要的答案中獲取了很多內容。