XOR 連結列表

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


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

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


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

是的,確實如此。

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

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

一個記憶體效率連結串列,或即異或連結串列是僅具有一個指標,而不是兩個。這將先前的地址(addr(prev)XOR (^)儲存到下一個地址(addr(next))。如果要移動到下一個節點,可以執行某些計算,並查詢下一個節點的地址。這與前一個節點相同。它像是:

StackOverflow 文件


它是如何工作的?

要了解連結串列的工作原理,你需要知道 XOR(^)的屬性:

 placeholderCopy|-------------|------------|------------|
|    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 處移動。這是執行此操作的公式:

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

所以這將是:

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

由於這是頭部,以前的地址只是 0,所以:

 placeholderCopyaddr (next) = 0 ^ (0 ^ addr (next))

我們可以刪除括號:

 placeholderCopyaddr (next) = 0 ^ 0 addr (next)

使用 none (2) 屬性,我們可以說 0 ^ 0 將始終為 0:

 placeholderCopyaddr (next) = 0 ^ addr (next)

使用 none (1) 屬性,我們可以將其簡化為:

 placeholderCopyaddr (next) = addr (next)

你得到了下一個節點的地址!

從節點移動到下一個節點

現在假設我們處於一箇中間節點,它有一個上一個和下一個節點。

讓我們應用公式:

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

現在替換值:

 placeholderCopyaddr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

刪除括號:

 placeholderCopyaddr (next) = addr (prev) ^ addr (prev) ^ addr (next)

使用 none (2) 屬性,我們可以簡化:

 placeholderCopyaddr (next) = 0 ^ addr (next)

使用 none (1) 屬性,我們可以簡化:

 placeholderCopyaddr (next) = addr (next)

你明白了!

從節點移動到之前的節點

如果你不理解標題,它基本上意味著如果你在節點 X,現在已經移動到節點 Y,你想要回到之前訪問過的節點,或者基本上是節點 X.

這不是一項繁瑣的任務。請記住,我上面提到過,你將所處的地址儲存在臨時變數中。因此,你要訪問的節點的地址位於變數中:

 placeholderCopyaddr (prev) = temp_addr

從節點移動到上一個節點

這與上面提到的不同。我的意思是說,你在節點 Z,現在你在節點 Y,並且想要去節點 X.

這與從節點移動到下一個節點幾乎相同。只是這是反之亦然。當你編寫一個程式時,你將使用我在從一個節點移動到下一個節點時提到的相同步驟,只是你在列表中找到了比查詢下一個元素更早的元素。


C 中的示例程式碼

 placeholderCopy/* 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++標準定義的。因此,上述實現可能無法在所有平臺上執行。


參考

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