Are there any results generalizing XOR Linked Lists to other types of data structures?

For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can imagine a two dimensional linked list where nodes are arranged on a plane and connected to eachother vertically and horizontally. Such a "Linked Mesh" can probably be iterated using 4 adjacent pointers in both directions and only storing one or two pointers for each node to its neighbor, instead of the full 4.

Are there any such results or similar results?

Is there a name for these type of structures?

  • 2
    $\begingroup$ You could probably apply the technique to any Zipper (a data structure with a 'focus point'). In general I think you can save one pointer. More, if you know multiple outgoing edges or if the edge you entered a node through predicts where you'll exit it. $\endgroup$ – Craig Gidney Mar 18 '16 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.