异或链表

数据结构

异或链表

一.简介

今天在重新翻看数据结构与算法的时候，再次看到了异或链表，松散链表等，借此机会总结记录一下关于异或链表的相关知识。（异或链表增加了操作复杂度，但是节省了存储空间，一般只会在嵌入式场景中可能会使用）

传统的双向链表，每一个节点需要有两个指针（pre和next），但是异或链表可以只适用一个数据变量即可同时找到前后两个节点元素。 异或链表(Xor Linked List)也是一种链式存储结构，它可以降低空间复杂度达到和双向链表一样目的，任何一个节点可以方便的访问它的前驱节点和后继结点。

二.概念介绍

异或操作的性质： 异或操作，也称为XOR操作，是一种逻辑运算，当两个操作数相同时返回0，否则返回1。 异或操作具有交换律和结合律，即a XOR b = b XOR a，(a XOR b) XOR c = a XOR (b XOR c)。 异或操作的逆操作是其自身，即a XOR b XOR a = b。

之前的位运算博客中也有重点说明异或的本质。

所以，实际存储在异或链表中的指针数据如下所示：

所以，总结一下就是，如果想遍历整个异或链表，要么就是知道head，要么就是知道tail，因为head和tail的指针就是下一个节点和上一个节点。或者就是知道中间的连续两个节点，这样就可以通过异或得到上一个或者下一个。

三.实现案例

#include <bits/stdc++.h>
using namespace std;
#define ERROR -1

// XorNode Class
template<typename ElemType>
class XorNode {
public:
    ElemType data;
    XorNode<ElemType> *xorPtr;
    XorNode(ElemType data):data(data) { }
};

// XorLinkedList Class
template<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;
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/03/18 23:31