Purpose of Xor Linked List?

Question

I stumbled on a Wikipedia article about the Xor linked list, and it's an interesting bit of trivia, but the article seems to imply that it occasionally gets used in real code. I'm curious what it's good for, since I don't see why it makes sense even in severely memory/cache constrained systems:

• The main advantage of a regular doubly linked list is the ability to insert or delete elements from the middle of the list given only a pointer to the node to be deleted/inserted after. This can't be done with an xor-linked list.
• If one wants O(1) prepending or O(1) insertion/removal while iterating then singly linked lists are good enough and avoid a lot of code complexity and caveats with respect to garbage collection, debugging tools, etc.
• If one doesn't need O(1) prepending/insertion/removal then using an array is probably more efficient in both space and time. Even if one only needs efficient insertion/removal while iterating, arrays can be pretty good since the insertion/removal can be done while iterating.

Given the above, what's the point? Are there any weird corner cases where an xor linked list is actually worthwhile?

Answer 1

Apart from saving memory, it allows for O(1) reversal, while still supporting all the other destructive update operations efficienctly, like

• concating two lists destructively in O(1)
• insertAfter/insertBefore in O(1), when you only have a reference to the node and its successor/predecessor (which differs slightly from standard doubly linked lists)
• remove in O(1), also with a reference to either the successor or predecessor.

I don't think the memory aspect is really important, since for most scenarios where you might use a XOR list, you can use a singly-linked list instead.