Instead of storing next and previous pointer, store xor of next and previous pointers. Implementation is given below -

struct Node

{

int data;

int xor;

Node(int d=0, int x=0):data(d), xor(x){}

};

class DList

{

public:

DList(Node* h=0, Node* t=0):head(h){}

void insert(int val); //insert at last position

void traverse();

private:

Node* head;

};

void DList::insert(int val)

{

if(!head)

{

head = new Node(val);

}

else

{

Node* prev = head, *temp = (Node*)(head->xor);

while(temp)

{

Node* temp1 = temp;

temp = (Node*)((int)prev ^ temp->xor);

prev = temp1;

}

temp = new Node(val, (int)prev);

prev->xor ^= (int)temp;

}

}

void DList::traverse()

{

if(!head)

return;

Node* prev = head, *temp = (Node*)(head->xor);

while(temp)

{

cout<<prev->data<<'\t';

Node* temp1 = temp;

temp = (Node*)((int)prev ^ temp->xor);

prev = temp1;

}

cout<<prev->data<<'\n';

}

* Limitation of this approach is, we can traverse list only from head or tail (if given).

## No comments:

## Post a Comment