[C] XOR linked list

一言以蔽之，這是個用 single linked list 的架構去做到 double linked list 的效果的東西，主要目的就是為了節省記憶體使用量

本來以為在這個記憶體用起來像不用錢的時代不會需要這東西，所以從來沒實作過，不過最近遇到的狀況是這樣：

1. 每一筆資料很小 (< 16 bytes)
2. 有非常多筆資料 (就算是比較小的測資也會有 billion 筆以上的資料)
3. 程式效能跟我能 cache 多少筆資料直接相關
4. cache 大概 2GB 就很大了 (所以很難把所有資料都放在記憶體中)

因為資料增增減減長度不固定，用動態的陣列會有浪費記憶體的可能性 (本來想說會有 100 筆，結果只來了 51 筆，就會多浪費了 49 筆資料的空間)，為了盡可能讓所有拿到的記憶體都能裝滿資料，所以最後決定用 linked list。想當然，為了存取方便，是採用了 double linked list，所以一開始是像這樣：

struct DoubleNode {
    int data;
    Node *prev, *next;
} Node;

常見的 double linked list 會有的結構，不過如果仔細分析的話會發現上面的結構你實際上只有 33% 的空間是真的存資料 (假設 data, prev, next 都是 4 bytes)，其實空間利用率非常差。但是改用如下的 single linked list

struct SingleNode {
    int data;
    Node *next;
} Node;

空間利用率是提高了 (來到 50%)，但又變成 traverse linked list 時會很不方便，這時候就是 XOR linked list 出場的時機了：

struct XorNode {
    int data;
    Node *neighbor;
} Node;

結構上跟 SingleNode 是一樣的，不一樣的地方是 XorNode 的 neighbor 存的其實是 DoubleNode 的 prev⊕next。直接看 code 吧：

XorNode* insert(XorNode* tail)
{
    XorNode* new_node = (XorNode*)malloc(sizeof(XorNode));
    new_node->neighbor = tail;
    tail->neighbor = tail->neighbor ^ new_node;
    return new_node;
}
void traverse(XorNode* head)
{
    while (NULL != head) {
        printf("data = %d\n", head->data);
        head = head ^ head->neighbor;
    }
};

差異主要就是標藍色的部分，本來 pointer 就是指向前/後一個 element，XOR linked list則是 前 & 後一個 element 的 pointer 做 XOR。利用

 A⊕(A⊕B) = B;

如果 neighbor = A⊕B，只要有 A 跟 neighbor 的值就能得到 B