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

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 LinkedIn 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 {
  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
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Karnataka INDIA.