Nodes of these XOR lists look like
typedef struct {
PTRS_AS_INT next_xor_prev;
DATA data;
} NODE;
You need 2 pointers to adjacent nodes to traverse. If p and q are
these pointers, then to advance to the next node,
tmp = p;
p = q ^ p->next_xor_prev; // not correct C; add casts to make it
work.
q = tmp;
This code is identical regardless of traversal direction. Initialize
with p as the next element "after" q, and the advance goes "forward."
Initialize with p as the previous element "before" q, and the advance
is in reverse.
This a convenient implementation is circular with the list header
containing a head and tail pointer. To traverse forward, initialize
the above with
p = header->head;
q = header->tail;
and to go backward
p = header->tail;
q = header ->head;
Now it's obvious that to reverse the list you need only swap the head
and tail pointers. There's no other way to do it.
You can reverse a regular doubly linked list in O(1) with the same
idea. Define nodes as
typedef struct node_s {
struct node_s *ptrs[2];
DATA data;
} NODE;
In the list header, keep a bit that says 0) whether ptrs[0] is "next"
and ptrs[1] is "prev" or 1) the opposite. Flipping this bit reverses
the list.
On Nov 30, 8:32 pm, Rajeev Kumar <[email protected]> wrote:
> --
> Thank You
> Rajeev Kumar
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
