- **C++**
(*http://www.velocityreviews.com/forums/f39-c.html*)

- - **how to implement doubly linked lists using only one pointer?**
(*http://www.velocityreviews.com/forums/t459407-how-to-implement-doubly-linked-lists-using-only-one-pointer.html*)

how to implement doubly linked lists using only one pointer?I'm reading MIT's book "Introduction to Algorithms".
The following is one of the excercises from it: < 10.2-8 Explain how to implement doubly linked lists using only one pointer value np[x] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit "exclusive-or" of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. /> Could anybody tell me how to solve it? Thank you!!! |

Re: how to implement doubly linked lists using only one pointer?tonywinslow1986@hotmail.com wrote:
> I'm reading MIT's book "Introduction to Algorithms". > The following is one of the excercises from it: > < > 10.2-8 > Explain how to implement doubly linked lists using only one pointer > value np[x] per item instead of the usual two (next and prev). Assume > that all pointer values can be interpreted as k-bit integers, and > define np[x] to be np[x] = next[x] XOR prev[x], the k-bit > "exclusive-or" of next[x] and prev[x]. (The value NIL is represented by > > 0.) Be sure to describe what information is needed to access the head > of the list. Show how to implement the SEARCH, INSERT, and DELETE > operations on such a list. Also show how to reverse such a list in O(1) > > time. > /> > > Could anybody tell me how to solve it? Thank you!!! > The book all but told you how to solve it. If anything XOR'd with itself is zero, solve the equation np[x] = next[x] XOR prev[x] for next[x]. To reverse the list, how would you revers a regular doubly linked list with next and prev pointers? -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. |

Re: how to implement doubly linked lists using only one pointer?"tonywinslow1986@hotmail.com" <tonywinslow1986@hotmail.com> writes:
> Explain how to implement doubly linked lists using only one pointer > value np[x] per item instead of the usual two (next and prev). Assume > that all pointer values can be interpreted as k-bit integers, and > define np[x] to be np[x] = next[x] XOR prev[x], the k-bit > "exclusive-or" of next[x] and prev[x]. (The value NIL is represented by > > 0.) Be sure to describe what information is needed to access the head > of the list. Show how to implement the SEARCH, INSERT, and DELETE > operations on such a list. Also show how to reverse such a list in O(1) > time. http://en.wikipedia.org/wiki/XOR_linked_list -- Best regards, _ _ .o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o ..o | Computer Science, Michal "mina86" Nazarewicz (o o) ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo-- |

Re: how to implement doubly linked lists using only one pointer?> The book all but told you how to solve it. > If anything XOR'd with itself is zero, solve > the equation > > np[x] = next[x] XOR prev[x] > > for next[x]. That's the point! It seems that I know nothing about bit computations, so silly questions are raised here. |

Re: how to implement doubly linked lists using only one pointer?> If anything XOR'd with itself is zero, solve
> the equation > > np[x] = next[x] XOR prev[x] > > for next[x]. how to solve that equation? i'm confused! |

Re: how to implement doubly linked lists using only one pointer?<tonywinslow1986@hotmail.com> wrote in message
news:1166947590.564286.303400@73g2000cwn.googlegro ups.com... >> If anything XOR'd with itself is zero, solve >> the equation >> >> np[x] = next[x] XOR prev[x] >> >> for next[x]. > > how to solve that equation? i'm confused! Play with bit math. int X = 1; int Y = 3; now output X and Y, X or Y, X xor Y, etc... Find out why they come out the way they do. |

Re: how to implement doubly linked lists using only one pointer?> Play with bit math.
> > int X = 1; > int Y = 3; > > now output X and Y, X or Y, X xor Y, etc... Find out why they come out the > way they do. i've known that: if A ^ B = C, then B = A ^ C, A = B^C. but anyway how to solve that equation with only np[x] given? |

Re: how to implement doubly linked lists using only one pointer?Hello!
The original question is fun! tonywinslow1986@hotmail.com wrote: > > i've known that: > if A ^ B = C, then B = A ^ C, A = B^C. What's X ^ X? What's (X ^ X) ^ Y? > but anyway how to solve that equation with only np[x] given? > You won't have "only np[x] given". The answer, as they say, is in the (original) question. It's all a matter of knowing where to begin. You /will/ know where to begin. Just use your head. Start at the beginning. After all, nothing will come from nothing, as they say. :-) Simon -- What happens if I mention Leader Kibo in my .signature? |

Re: how to implement doubly linked lists using only one pointer?<tonywinslow1986@hotmail.com> wrote in message news:1166963413.462967.285970@48g2000cwx.googlegro ups.com... > > i've known that: > if A ^ B = C, then B = A ^ C, A = B^C. > but anyway how to solve that equation with only np[x] given? I think this is an easy way to communicate the concept: Instead of XOR, use addition and subtraction (they are essentially equivalent when it comes to implementing the trick of this method, but much easier to comprehend). First, every node has a field to hold the distance from its previous-node to its next-node. Note that this is exactly equal to the sum of the distances from its previous-node to itself, and from itself to its next-node. When you iterate, you need pointers to two successive nodes. Call them A and B. It is easy to compute the distance between the nodes (B-A), and from there it is easy to compute the address of A's previous-node [A's sum-of-distances is reduced by (B-A) and the remainder applied as an offset to A's address] or of B's next-node [left as an exercise]. - Risto - |

All times are GMT. The time now is 09:21 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.