XOR鏈結串列

XOR鏈結串列（英語：XOR linked list）是資料結構裡面的一種鏈式儲存結構,可以在降低空間複雜度的情況下達到和雙向鏈結串列一樣的目的，使得在任何一個節點都能方便地訪問它的前驅節點和後繼節點。

概述

普通雙向鏈結串列的每個節點有三個域 ，分別儲存著前一個節點的位址、後一個點的位址，以及資料

 ...  A       B         C         D         E  ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

XOR鏈結串列通過XOR操作（這裡用⊕表示）把前一個節點的位址和後一個節點的位址變成一個位址

 ...  A         B               C                D            E  ...
          <–>  A⊕C     <->    B⊕D     <->      C⊕E  <->
  
      link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), …

當從左往右遍歷的時候，如果當前節點是C，指標域是內容是B⊕D,通過和前一個節點B的位址做XOR操作就能得到下一個節點D的位址，如此重複便能遍歷整個鏈結串列。

C語言範例（XOR指標雙向鏈結串列）

XOR鏈結串列節點結構

typedef struct XorNode {
    char data;
    struct XorNode *LRPtr;
}
XorNode, *XorPointer;

XOR指標雙向鏈結串列結構

typedef struct XorLinkedList {
    XorPointer left, right;
}
XorLinkedList;

XOR操作

XorPointer xor(XorPointer a, XorPointer b) {
    return (XorPointer)((unsigned long)(a) ^ (unsigned long)(b));
}

建立XOR雙向鏈結串列

void createXorLinkedList(XorLinkedList *list) {
    char ch;
    XorPointer lastNode = NULL;
    int isFirstNode = 1;
    while ((ch = getchar()) != '\n') {
        XorPointer newNode = (XorPointer) malloc(sizeof(XorNode));
        newNode -> data = ch;
        newNode -> LRPtr = NULL;
        if (lastNode) {
            newNode -> LRPtr = xor(lastNode, NULL);
            lastNode -> LRPtr = xor(xor(lastNode -> LRPtr, NULL), newNode);
        }
        lastNode = newNode;
        if (isFirstNode) {
            isFirstNode = 0;
            list -> left = newNode;
        }
    }
    list -> right = lastNode;
}

按任意方向依次輸出各節點值

void print(XorPointer a, XorPointer b) {
    XorPointer nullFirst = a == NULL ? a : b;
    XorPointer nonNullFirst = a != NULL ? a : b;
    XorPointer tmp = NULL;
    do {
        printf("%c ", nonNullFirst -> data);
        tmp = nonNullFirst;
        nonNullFirst = xor(nullFirst, nonNullFirst -> LRPtr);
        nullFirst = tmp;
    } while (nonNullFirst != NULL);
}

在第i個節點之前插入一個節點

void XorLinkedListInsert(XorLinkedList *list, int pos, char data) {
    XorPointer node = list -> left, tmp = NULL;
    XorPointer last = NULL;
    XorPointer newNode = NULL;
    int i = 1;
    while (i < pos && node != NULL) {
        tmp = node;
        node = xor(last, node -> LRPtr);
        last = tmp;
        i++;
    }
    newNode = (XorPointer) malloc(sizeof(XorNode));
    newNode -> data = data;
    newNode -> LRPtr = xor(last, node);
    if (node != NULL) {
        node -> LRPtr = xor(newNode, xor(last, node -> LRPtr));
    }
    if (last != NULL) {
        last -> LRPtr = xor(xor(last -> LRPtr, node), newNode);
    }
    if (pos == 1) {
        list -> left = newNode;
    }
}

刪除第i個節點

void XorLinkedListDelete(XorLinkedList *list, int pos) {
    XorPointer node = list -> left, last = NULL, next = NULL, tmp = NULL;
    int i = 1;
    while (i < pos && node != NULL) {
        i++;
        tmp = node;
        node = xor(last, node -> LRPtr);
        last = tmp;
    }
    next = xor(last, node -> LRPtr);
    if (last != NULL) {
        last -> LRPtr = xor(xor(last -> LRPtr, node), next);
    }
    if (next != NULL) {
        next -> LRPtr = xor(last, xor(node, next -> LRPtr));
    } else {
        list -> right = last; //删除了最后一个结点
    }
    if (pos == 1) {
        list -> left = next;
    }
    free(node);
}

C++ 範例

• XORList: Efficient C++ Linked List (MIT License) （頁面存檔備份，存於網際網路檔案館） - A GitHub repository providing an efficient implementation of XOR linked lists in C++.