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 <rajeevprasa...@gmail.com> 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 algogeeks@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.