【一个神奇的数据结构-异或双链表】拥有单链表的空间，效率如双链表

Karos

修改于 2023-02-02 12:06:13

4890

修改于 2023-02-02 12:06:13

在此之前，先从入门的方面来讲一讲。

在最开始学编程的时候，我们交换两个变量，有两种方法

//方法一
c=a
a=b
b=c
//方法二
a=a+b
b=a-b
a=a-b

从第二种方法我们可以看出，我们可以通过两个数的相加，然后特别取出某个数

那么想一想？我们能否通过两个地址相加，取出一个地址呢？（这个在这里给大家引一个方向）

到了后面，接触了位运算，我们有可以通过异或来进行数据交换

//方法三
a=a^b;
b=a^b;
a=a^b;

这和位运算的自反性有关

那么，我们能否同地址进行异或运算来得出一个地址呢？思路和上面通过加法有点像

双链表

看这个的应该都会，我直接上图

我们把中间某一个节点单独提取出来，就会是这样

其中prev是上一个节点的地址，next是下一个节点的地址

属于两个指针域，那么我们能否用一个指针域来代替两个呢

如果能够代替，那么假设我们某个节点的前驱节点地址如果是已知的，那么他的后继节点地址也能够退出来，比如我们可以设当前节点的指针与为prev+next，然后上一个节点的地址是prev，那么下一个节点的地址不就是prev+next-prev吗？一个简单的函数

Node* sump(Node* a,Node *b){
 return (Node*)((unsigned long long)a+(unsigned long long)b)
}

但是为了运算效率快一点，我们直接用异或运算（在单位二进制的情况下，异或运算等同于加法，与运算等同于乘法）

Node* xorp(Node* a,Node *b){
 return (Node*)((unsigned long long)a^(unsigned long long)b)
}

我们可以这样存储数据

B的异或指针如下构造

B->xorPtr = addr(A) ⊕ addr(C)

获取B的前驱A的地址

addr(A) = B->xorPtr ⊕ addr(C)

获取B的后继C的地址

addr(C) = B->xorPtr ⊕ addr(A)

通过以上的几种操作，就可以遍历整个链表，在处理添加、插入、删除等操作时同普通的双向链表类似

注意：这些异或和加法相关的操作都是针对指针值的本身，即指针转换为无符号整型数的结构，不能跟指针的运算操作混淆。

下面是代码：

#include <iostream>
using namespace std;
//通过异或运算实现双链表
typedef struct node{
    int v;
    struct node *xorptr=NULL;//存储相邻两个节点地址的异或值
}Node;
inline Node* xorp(Node* a, Node* b){
    return (Node *)((unsigned long long)a^(unsigned long long)b);
}
class List{
    Node *Head=NULL;//头节点
    Node *Tail=NULL;//尾节点
    int Len=0;
public:
    List() {
        this->Head=new Node ;
        this->Tail=new Node ;
        Head->xorptr=Tail;
        Tail->xorptr=Head;
        Len=0;
    }
    void init(){
        int i=10;
        srand(time(NULL));
        while(i--) {
            int x=rand()%100+0;
            insert(x);
        }
    }
    void insert(int i){
        Node *p=new Node ;
        p->v=i;
        if(!Len){
            Head=p;
            p->xorptr=NULL;
            Tail=p;
        } else{
            p->xorptr= Head;
            Head->xorptr= xorp(p,Head->xorptr);
            Head=p;
        }
        Len++;
    }
    void display(bool flag=false){
        Node *p=NULL;
        Node *t=NULL;
        if (!flag)p=Head;
        else p=Tail;
        for(int i=0;i<Len;i++){
            cout<<p->v<<" ";
            Node *k=p;
            p= xorp(t,p->xorptr);
            t=k;
        }
    }

    bool remove(int v){
        Node *p=Head;
        Node *t=NULL;
        bool flag=false;
        for(int i=0;i<Len;i++){
            if (p->v==v){
                flag=true;
                Len--;
                if (p==Head){
                    Head=Head->xorptr;
                    Head->xorptr= xorp(p,Head->xorptr);
                    p=Head;
                    continue;
                }
                Node* m= xorp(t,p->xorptr);
                t->xorptr=xorp( t->xorptr,p);
                m->xorptr= xorp(m->xorptr,p);
                t->xorptr= xorp(t->xorptr,m);
                m->xorptr= xorp(m->xorptr,t);
                p=m;
            }
            else{
                Node *k=p;
                p=xorp(t,p->xorptr);
                t=k;
            }
        }
        return flag;
    }
};
int main(){
    List A;
    cout<<"头插顺序：";
    A.init();
    A.display(true);
    cout<<endl;
    cout<<"插入后的结果：";
    A.display();
    cout<<endl;
    cout<<"请输入要删除的数字：";
    int x;
    cin>>x;
    if (A.remove(x)){
        cout<<"删除成功：";
        A.display();
        cout<<endl;
    }
    else{
        A.insert(x);
        A.display();
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-10-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构