Part 1 of the trick is that if you know A xor B and you have either A
or B, you can get the other value. This is because A xor (A xor B) =
B and B xor (A xor B) = B.
[Incidentally, you can use subtraction rather than XOR. If you know A
- B and have A, you can compute A - (A - B) to get B. If you have B,
you can compute B + (A - B) to get A.]
Part 2 of the trick is that as you are traversing a list, you always
know the address of the node you just came from. Consequently, if you
store the xor of the next and previous pointers in a single location
within the node, you always have enough information to learn the
pointer you don't know.
I.e. if your nodes look like:
struct node {
struct node *next_xor_prev;
... other fields;
}
and you have pointers to two adjacent notes p0 and p1, you can advance
them to the successor node with
tmp = p1;
p1 = p0 xor p1->next_xor_prev
p0 = tmp
Which direction you go depends on the values of p0 and p1. If p0 =
previous(p1), then you'll advance both pointers 1 node forward. If p0
= next(p1), then you'll advance to the previous node.
To make all this work, you must represent the entire list as a head
_and_ tail pointer.
struct list {
struct node *head, *tail;
}
so a forward traversal is initialized with p1 = head; p0 = tail;
and backward traversal is p1 = tail; p0 = head.
So the price you pay for this method is that if you want to pass
around pointers into the middle of the list that allow you to start a
traversal from that point, you must pass around a pair pointers to two
adjacent list nodes rather than a single one.
The other price is that no language I know of provides a portable way
to store the xor of two pointers, so it's a risky thing to do in
production software.
On Aug 14, 11:15 am, UMESH KUMAR <kumar.umesh...@gmail.com> wrote:
> explain ,if anybody known how to back tracking a Singly link list as a
> Doubly list with XOR -operation or any method if implementation of a Doubly
> link list using only one pointer .
>
> Explain with help of example
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
