Can we implement an XOR linked list in Java?

Question

As Java doesn't provide a way to get the address of the object, is it feasible to code an XOR linked list?

If yes, can someone please elaborate, how to do that?

Answer 1

You can never do this in Java.

Even if you use sun.misc.Unsafe to get access to the real addresses of the objects, and even if you use a garbage collector that won't move objects around (Concurrent Mark Sweep doesn't move objects, I believe, as it's "non-compacting"), you have a bigger problem: By mangling the prev and next object references together in an integer, the garbage collector won't realize that they are object references. So it will think the referred objects are unreferenced, and consequently, will collect all your list nodes as garbage.

If you need to save memory, use an array-based list instead of a linked list.

Answer 2

I don't believe you can (at least, not using object references for your "next" and "prev" pointers), for the reason you cite: Object addresses are officially opaque. Although we could access the bits of a reference, the JVM can move objects in memory (e.g., when doing memory management), and although I'm not immediately finding a spec citation for it, I believe it's allowed to handle that by modifying the object reference values (literally going and updating every field and such where the old reference is, giving it the new reference). So if we converted the object reference to a long (for instance) and then XOR'd that with another object reference converted to a long, if either object moved (as they can do), once either of those is XOR'd back and converted back into an object reference, it may well no longer be valid.

Consequently, I think you'd need to use something other than object references for the pointers, such as indexes into a big array of object references, at which point I'm fairly sure you've lost the memory benefit of the XOR linked list.