XOR 連結列表
一個異或連結串列也被稱為記憶體效率連結串列。它是雙重連結串列的另一種形式。這高度依賴於 XOR 邏輯閘及其屬性。
為什麼這稱為記憶體高效連結列表?
之所以這樣稱呼是因為它使用的記憶體少於傳統的雙向連結串列。
這與雙重連結列表不同嗎?
是的,確實如此。
一個雙連結串列正儲存兩個指標,其在下一和前一節點指向。基本上,如果你想回去,你會轉到 back
指標指向的地址。如果你想繼續前進,你會轉到 next
指標指向的地址。就像是:
http://i.stack.imgur.com/t1RDM.gif
一個記憶體效率連結串列,或即異或連結串列是僅具有一個指標,而不是兩個。這將先前的地址(addr(prev)
) XOR (^)儲存到下一個地址(addr(next)
)。如果要移動到下一個節點,可以執行某些計算,並查詢下一個節點的地址。這與前一個節點相同。它像是:
它是如何工作的?
要了解連結串列的工作原理,你需要知道 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++標準定義的。因此,上述實現可能無法在所有平臺上執行。
參考
-
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/
請注意,我從主要的答案中獲取了很多內容。