首页 > 代码库 > 异或链表(XOR linked list)
异或链表(XOR linked list)
异或链表(Xor Linked List)也是一种链式存储结构，它可以降低空间复杂度达到和双向链表一样目的，任何一个节点可以方便的访问它的前驱节点和后继结点。可以参阅wiki
普通的双向链表
class Node {public: int data; Node *prev; Node *next; };class BiLinkedList {public: Node *head; Node *tail;};
普通双向链表的一个节点表示如下：
完整的普通双向链表如下所示：
对于异或链表来说，只是用一个xorPtr指针取代prev和next两个指针，这对于空间效率是一个提升。
template<typename ElemType>class XorNode {public: ElemType data; XorNode<ElemType> *xorPtr; XorNode(ElemType data):data(data) { }};template<typename ElemType>class XorLinkedList {public: XorNode<ElemType> *head; XorNode<ElemType> *tail;}
异或链表如下图所示，每一个Node记录data数据和xorPtr异或指针，异或指针记录前后两个指针的地址值的异或值
B的异或指针如下构造
B->xorPtr = addr(A) ⊕ addr(C)
获取B的前驱A的地址
addr(A) = B->xorPtr ⊕ addr(C)
获取B的后继C的地址
addr(C) = B->xorPtr ⊕ addr(A)
通过以上的几种操作，就可以遍历整个链表，在处理添加、插入、删除等操作时同普通的双向链表类似，在纸上多画画之间的关系就OK。
记得处理边界，比如只剩一个节点进行删除操作时候，要判断前继和后驱Node是否为NULL，操作前要进行链表是否为空和越界的判断，xor是关键字。
另外，B的xorPtr也可以类似的使用加法运算A+C, 假设B的指针是ptr，B的前驱为B->ptr – C, B的后继为B->ptr-A。
指针转换为无符号整形，然后进行异或操作。
这些异或和加法相关的操作都是针对指针值的本身，即指针转换为无符号整型数的结构，不能跟指针的运算操作混淆。
下面就是完整的代码。
#include <bits/stdc++.h>using namespace std;#define ERROR -1// XorNode Classtemplate<typename ElemType>class XorNode {public: ElemType data; XorNode<ElemType> *xorPtr; XorNode(ElemType data):data(data) { }};// XorLinkedList Classtemplate<typename ElemType>class XorLinkedList {public: XorNode<ElemType> *head; XorNode<ElemType> *tail; int size; // constructor function XorLinkedList() { head = NULL; tail = NULL; size = 0; } // is xorlinkedlist empty bool isEmpty() { return head == NULL && tail == NULL; } // xorlinkedlist length int length() { return size; } // add element into back void addBack(ElemType e) { XorNode<ElemType> *newNode = new XorNode<ElemType>(e); if (isEmpty()) { newNode->xorPtr = xor_func(NULL, NULL); head = newNode; tail = newNode; } else { newNode->xorPtr = xor_func(tail, NULL); tail->xorPtr = xor_func(xor_func(tail->xorPtr, NULL), newNode); tail = newNode; } size++; } //add element into front void addFront(ElemType e) { XorNode<ElemType> *newNode = new XorNode<ElemType>(e); if (isEmpty()) { newNode->xorPtr = xor_func(NULL, NULL); head = newNode; tail = newNode; } else { newNode->xorPtr = xor_func(NULL, head); head->xorPtr = xor_func(newNode, xor_func(head->xorPtr, NULL)); head = newNode; } size++; } // pop element from back ElemType popBack() { if (isEmpty()) { cout << "XorLinkedList is empty." << endl; return ERROR; } XorNode<ElemType> *tmpNode = tail; ElemType ret = tail->data; tail = xor_func(tail->xorPtr, NULL); if (tail) tail->xorPtr = xor_func(xor_func(tail->xorPtr, tmpNode), NULL); else head = NULL; delete[] tmpNode; size--; return ret; } // pop element from front ElemType popFront() { if (isEmpty()) { cout << "XorLinkedList is empty." << endl; return ERROR; } XorNode<ElemType> *tmpNode = head; ElemType ret = head->data; head = xor_func(NULL, head->xorPtr); // if not pop last node, set the xorPtr if (head) head->xorPtr = xor_func(NULL, xor_func(head->xorPtr, tmpNode)); else tail = NULL; delete[] tmpNode; size--; return ret; } // return the value of pos ElemType getValue(int pos) { if (pos < 0 || pos >= length()) { cout << "pos ranges from " << 0 << " to " << length() - 1 << endl; return ERROR; } int step = 0; XorNode<ElemType> *curNode = NULL; if (pos <= length()/2) { curNode = head; step = pos; } else { curNode = tail; step = length() - pos - 1; } int i = 0; XorNode<ElemType> *otherNode = NULL, *tmpNode = NULL; while (i < step && curNode != NULL) { tmpNode = curNode; curNode = xor_func(curNode->xorPtr, otherNode); otherNode = tmpNode; i++; } return curNode->data; } // insert a node before pos void insert(ElemType e, int pos) { if (pos < 0 || pos > length()) { cout << "pos ranges from " << 0 << " to " << length() << endl; cout << "0: add element in front, " << length() << ": add element in back." << endl; return; } // deal with front and back if (pos == 0) addFront(e); else if(pos == length()) addBack(e); else { XorNode<ElemType> *curNode = NULL, *tmpNode = NULL, *otherNode = NULL; int i = 0; curNode = head; // find the pos while (i < pos && curNode != NULL) { tmpNode = curNode; curNode = xor_func(curNode->xorPtr, otherNode); otherNode = tmpNode; i++; } // insert the newNode before pos XorNode<ElemType> *newNode = new XorNode<ElemType>(e); newNode->xorPtr = xor_func(curNode, otherNode); otherNode->xorPtr = xor_func(xor_func(otherNode->xorPtr, curNode), newNode); curNode->xorPtr = xor_func(newNode, xor_func(otherNode, curNode->xorPtr)); size++; } } // delete the element at pos void remove(int pos) { if (isEmpty()) { cout << "XorLinkedList is empty" << endl; return; } if (pos < 0 || pos >= length()) { cout << "pos ranges from " << 0 << " to " << length()-1 << endl; return; } if (pos == 0) popFront(); else if (pos == length()) popBack(); else { int step = 0; XorNode<ElemType> *curNode = NULL; if (pos <= length()/2) { curNode = head; step = pos; } else { curNode = tail; step = length() - pos - 1; } int i = 0; XorNode<ElemType> *otherNode = NULL, *tmpNode = NULL, *nextNode = NULL; while (i < step && curNode != NULL) { tmpNode = curNode; curNode = xor_func(curNode->xorPtr, otherNode); otherNode = tmpNode; i++; } nextNode = xor_func(curNode->xorPtr, otherNode); if (otherNode) otherNode->xorPtr = xor_func(xor_func(otherNode->xorPtr, curNode), nextNode); if (nextNode) nextNode->xorPtr = xor_func(otherNode, xor_func(nextNode->xorPtr, curNode)); delete[] curNode; size--; } } // traverse the xorlinkedlist. // f: head -> tail // r: tail -> head void traverse(char direction = ‘f‘) { if (isEmpty()) { cout << "XorLinkedList is empty" << endl; return; } if (direction != ‘f‘ && direction != ‘r‘) { cout << "direction error, ‘f‘ or ‘r‘." << endl; return; } XorNode<ElemType> *curNode = NULL, *otherNode = NULL, *tmpNode = NULL; if (direction == ‘f‘) curNode = head; // head -> tail else if (direction == ‘r‘) curNode = tail; // tail -> head do { cout << curNode->data << " "; tmpNode = curNode; curNode = xor_func(curNode->xorPtr, otherNode); otherNode = tmpNode; } while (curNode != NULL); cout << endl; }private: XorNode<ElemType>* xor_func(XorNode<ElemType> *a, XorNode<ElemType> *b) { return (XorNode<ElemType>*)((unsigned long)(a) ^ (unsigned long)(b)); }};int main() { XorLinkedList<int> xll; xll.insert(1,0); xll.insert(2,1); xll.insert(3,1); xll.traverse(‘f‘); // for (int i = 0; i < 3; i++) // cout << xll.popBack() << endl; xll.remove(1); xll.traverse(‘f‘); cout << endl; return 0;}
异或链表(XOR linked list)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。