how to implement doubly linked lists using only one pointer?

Discussion in 'C++' started by tonywinslow1986@hotmail.com, Dec 23, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Joe Seigh Guest

    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.
    Joe Seigh, Dec 23, 2006
    #2
    1. Advertising

  3. "" <> 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--
    Michal Nazarewicz, Dec 23, 2006
    #3
  4. Guest


    > 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, 2006
    #4
  5. Guest

    > 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, 2006
    #5
  6. Jim Langston Guest

    <> wrote in message
    news:...
    >> 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.
    Jim Langston, Dec 24, 2006
    #6
  7. Guest

    > 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, 2006
    #7
  8. Simon G Best Guest

    Hello!

    The original question is fun!

    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?
    Simon G Best, Dec 29, 2006
    #8
  9. <> wrote in message
    news:...
    >
    > 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 -
    Risto Lankinen, Jan 2, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andersen

    doubly linked objects

    Andersen, Oct 20, 2005, in forum: Java
    Replies:
    17
    Views:
    576
    Andrea Desole
    Nov 1, 2005
  2. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    910
    bugbear
    Mar 24, 2006
  3. darth
    Replies:
    0
    Views:
    440
    darth
    Apr 30, 2004
  4. chand
    Replies:
    7
    Views:
    305
    Terry Reedy
    Sep 5, 2005
  5. arnuld

    Stack using doubly linked list

    arnuld, Jun 1, 2011, in forum: C Programming
    Replies:
    1
    Views:
    2,584
    luser- -droog
    Jun 1, 2011
Loading...

Share This Page