top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to implement doubly LinkList using single LinkList?

+4 votes
92 views

Say you have only this structure only to implement Doubly LL

struct Node
{
   int val;
   Node* p;
};
posted Oct 25, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

2 Answers

+1 vote

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 Oct 25, 2013 by Salil Agrawal
0 votes

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.

answer Oct 25, 2013 by sivanraj
I think it is related with xor operation...
p = prev xor next; but not very sure...
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...