T
tonywinslow1986
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 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!!!