单指针实现双链表(Golang)

如何用单指针实现双链表？要解决这个问题，我们需要一些思维的铺垫，下面分三个步骤，由浅入深地带你实现！

正常：实现一个单链表

网上单链表的实现非常多，考虑到实用性，设计也不尽相同。下面选一个最直白简单的。

show me the code

gist.github.com/RBowind/1561ac542b0c33bbf1da20d47640d80f

//Element单链表每一个节点typeElementstruct{next*Element//索引下一个节点Valueinterface{}}typeListstruct{root*Element//整个链表tail*Element//索引最后一个节点，方便pushlenint//单链表的长度}

不正常：用单指针地址再实现一个单链表

假设现在我觉的上面的结构会嵌套很深，看起来难受（想炫技?），那么可以把头节点的的next 改成 ptr，指向下一个节点的指针地址，然后下一个节点的 ptr 指向 下下个节点的指针地址。

next*Element==>ptruintptr

show me the code

gist.github.com/RBowind/4d35bea89c61707ee150260ae632e341

typeElementstruct{ptruintptr//指向下一个节点的指针地址Valueinterface{}}typeListstruct{root*Elementtailuintptrlenint}

更不正常：单指针实现双链表

首先理解上面 用单指针地址再实现一个单链表 的思路，然后再看下去。

利用异或的特性：$a⨁(a⨁b)=b$a⨁(a⨁b)=b

每个节点的 ptr 不再存储下一个节点的的指针地址，而是上一个节点指针地址和下一个节点指针地址的 异或 结果。

如下图：P0 的 ptr 放的是上一个节点 0 与 下一个节点 P1 的指针地址的 异或 ,P1、P2 逻辑也如此。 这样，便可以既顺序遍历，又可以逆序遍历。

$$P0⨁(P0⨁P2)=P2$$

0^(0^P1)=P1//其中0^P1就是P0上存储的ptrP0^(P0^P2)=P2//其中P0^P2就是P1上存储的ptr

show me the code

gist.github.com/RBowind/f7d7fdce90a2c87efd27ec7461eb804d

typeElementstruct{ptruintptrValueinterface{}}typeListstruct{root*Elementtailuintptrlenint}//...更多细节查看上面gistfunc(l*List)insert(e*Element,tailuintptr)*Element{ifl.len==0{l.root.Value=e.Valuel.root.ptr=0l.tail=uintptr(unsafe.Pointer(l.root))}else{tailElement:=(*Element)(unsafe.Pointer(tail))//拿到最新的尾部节点tailElement.ptr=tailElement.ptr^uintptr(unsafe.Pointer(e))//异或修改尾部节点的指针e.ptr=tail//插入节点的ptr暂存上一个节点的指针，而这个就是下一个插入的tailElement.ptrl.tail=uintptr(unsafe.Pointer(e))//把tail指向最新的节点}l.len++returne}

缺陷

这种结构自然也有缺陷，比如只能顺序/逆序，从头/尾开始遍历，单单给到 P1 节点，是难以拿到 P0 和 P2的，不过，这也算实现了双向链表，这只是一种思维，目前看来并不实用。