468,457 Members | 1,601 Online

# 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!!!

Dec 23 '06 #1
8 3618 to*************@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.
Dec 23 '06 #2
"to*************@hotmail.com" <to*************@hotmail.comwrites:
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--
Dec 23 '06 #3
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.

Dec 24 '06 #4
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!

Dec 24 '06 #5
<to*************@hotmail.comwrote in message
news:11**********************@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.
Dec 24 '06 #6
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?

Dec 24 '06 #7
Hello!

The original question is fun!

to*************@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?
Dec 29 '06 #8

<to*************@hotmail.comwrote in message
news:11**********************@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 -
Jan 2 '07 #9

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 3 posts views Thread by surrealtrauma | last post: by 4 posts views Thread by dssuresh6 | last post: by 8 posts views Thread by sudhirlko2001 | last post: by 1 post views Thread by drewy2k12 | last post: by 2 posts views Thread by murali | last post: by 3 posts views Thread by maruf.syfullah | last post: by 10 posts views Thread by kalar | last post: by 4 posts views Thread by valt | last post: by 4 posts views Thread by arnuld | last post: by reply views Thread by ravipankaj | last post: by reply views Thread by ravipankaj | last post: by reply views Thread by slotstar | last post: by 7 posts views Thread by isladogs | last post: by reply views Thread by captainhaddock | last post: by 2 posts views Thread by Zeeshan Ahmad | last post: by 1 post views Thread by adamb123 | last post: by 1 post views Thread by AlexK987 | last post: by 1 post views Thread by kimpoy0 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.