Thread: xor linked list

Code:

        while((cur != NULL) && (cur->data < newnode->data))
        {
                node *next = (node *)(cur->link ^ (unsigned long)prev);
                prev = cur;
                cur = next;
        }
        if(cur->data >= newnode->data)

Well, right here cur could be NULL, so when you hit your first if check, you could be dying there.

Quzah.

Typically, an XOR-linked list is circular, thus you never encounter the problem of running off the end.

Originally Posted by quzah

It also defeats the purpose of a double linked list, because you cannot just start with any random node and do whatever you like to it. You can't just start in the middle of the list and find your way through it. You also can't just chop out a node whenever you please. Which again, completely defeats the purpose of using a double linked list.

That's not true. How often do you start in the middle of any list anyway? You almost always have to have iterated to there at some point.
All an XOR list means is that the iterators have to be a little more complex to achieve about the same functionality. They have to store the pointer values of two adjacent nodes, rather than just the usual one (unless there is only one item). From this iterator it is possible to iterate forwards or backwards as you please, and thus clearly allowing you to remove the item currently pointed to by the iterator since you can find the nodes either side, similar for insertion.
All that's diferent (to the user) from a std::list, is the iterator invalidation rules. Erasing or inserting an item invalidates iterators to either side of that iterator (in addition to that iterator if erasing).

There's a lot more to it than you realise and I really do urge you to research it a little more. Things like this still have there place in embedded (okay "really embedded") devices.
It has no place in garbage collected languages because the pointers are obviously mutilated and would get collected erroneously.

Originally Posted by iMalc

That's not true. How often do you start in the middle of any list anyway?

Any time you use a function which ends up returning a node.

Originally Posted by iMalc

There's a lot more to it than you realise and I really do urge you to research it a little more. Things like this still have there place in embedded (okay "really embedded") devices.
It has no place in garbage collected languages because the pointers are obviously mutilated and would get collected erroneously.

Honestly I can't ever see myself using one of these, and the added complexity negates any benefit I could possibly hope to gain out of it. I'd have to be really really bored to want to implement one of these.


Quzah.

Originally Posted by quzah

Any time you use a function which ends up returning a node.

In reality you would actually return an iterator, so the iteration is there it's just done in another function. Unless of course you were actually trying to make things difficult for yourself, or it's an intrusive list (the case you're probably talking about).
You can throw the iterator away and only go for the thing it points to, any time you want to lose the ability to iterate over the other items in the list.
Agreed it's more complex and usually not worth using.