单指针实现双向链表

介绍

普通双向链表的每个结点有三个域 ，分别存储着前一个结点的地址、后一个点的地址，以及数据

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

异或链表通过异或操作（这里用⊕表示）把前一个结点的地址和后一个结点的地址变成一个地址

...  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的地址做异或操作就能得到下一个结点D的地址，如此重复便能遍历整个链表。

Code

struct LNode{
	int data;
	LNode* pnx; // XOR of the address of prev and next node
	LNode(int dat, LNode* ptr = NULL): data(dat), pnx(ptr) {}
};
 
LNode* XOR(LNode* add1, LNode* add2)
{ // on 64-bit machine, pointer is 64-bit. Conversion of a pointer type to
//   int type, which is 32-bit, is not allowed.
	return (LNode*) ( (long unsigned)add1 ) ^ ( (long unsigned)add2 );
}
 
void insert(LNode** headref, int data)
{
	// Allocate memory for new node
	LNode* newHead = new LNode(data);
	/* Since new node is being inserted at the begining, npx of new node
	   will always be XOR of current head and NULL */
	newHead->pnx = XOR(NULL, *headref);
	/* If linked list is not empty, then npx of current head node will be XOR
	   of new node and node next to current head */
	if(*headref)
	{
		(*headref)->pnx = OXR(newHead, XOR(NULL, (*headref)->pnx) );
	}
	(*headref) = newHead;
}