How to implement doubly LinkList using single LinkList?

Question

Say you have only this structure only to implement Doubly LL

struct Node
{
   int val;
   Node* p;
};

Answer 1

Basically each node will store the xor of previous and next node address. And rest will remain more or less same as normal Double Link List.

Class Node will look like this -

class node {
public: 
  int myValue;
  uintptr_t xor_prev_and_next;
  node *next(node *prev) {
    return (node*)((uintptr_t)prev ^ xor_prev_and_next);
  }
  node *prev(node *next) {
    return (node*)((uintptr_t)next ^ xor_prev_and_next);
  }
};

Answer 2

struct Node
{
int val;
Node* p; // self ref
};

In case of single list you will copy next node to p.

For DLL just do malloc (8) then copy prev node into first 4 bytes, copt next node to second 4 bytes.

Now you will get DLL with this structure.

Comments

I think it is related with xor operation...
p = prev xor next; but not very sure...