Linked lists

This is a discussion on Linked lists within the C Programming forums, part of the General Programming Boards category; How can i implement doubly linked lists using only one pointer value "np[x]" per item instead of the usual two ...

  1. #1
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    Linked lists

    How can i implement doubly linked lists using only one pointer value "np[x]" per item
    instead of the usual two (next and prev). I am told to assume that all pointer values can be interpreted as k-bit integers. So, this has got to do with bit-wise operations.This has me totally stumped. Can anyone help me get started.
    In the middle of difficulty, lies opportunity

  2. #2
    Registered User
    Join Date
    Dec 2006
    Posts
    30

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You don't. It's one of those incredibly stupid things they think are good home work assignments, which have no practical purpose.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    @spoon! : thanks for that, will look into it
    @quzah : yeah, I do agree with you. Only use I could think of is saving space in each node.
    In the middle of difficulty, lies opportunity

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I've looked at the article, and I don't see how it's supposed to be useful:
    To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one.
    If I need two addresses to move a direction, why wouldn't I just use two pointers in my node? With this sort of list, you cannot start at a random node in the list, pick a direction, and go there, because you have to have two addresses in order to move. If all you have is a poitner to that node, you can't do anything! What's the point? The only way you can move through this list is to either start at the very first node, or the very last node. Otherwise, you can't navigate through it.

    Furthermore, you have to know you're at the first or last node, or you can't move through it either, because you won't have the two pieces of information you're supposed to be XORing with.

    They shouldn't call these XOR lists, they should call them "crippled linked lists". Half the space, half the functionality!


    Quzah.
    Last edited by quzah; 12-16-2006 at 01:28 AM.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 04:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21