Can we implement an XOR related list in Java?

Question

Since Java does not provide a way to get the address of an object, is it possible to encode a linked XOR list ?

If so, can someone comment on how to do this?

Answer 1

You can never do this in Java.

Even if you use sun.misc.Unsafe to access the real addresses of objects, and even if you use a garbage collector that will not move objects (Concurrent Mark Sweep does not move objects, I believe it is "not compacted"), you have a more serious problem: by accessing the object links prev and next together as an integer, the garbage collector will not understand that they are object links. Therefore, he will think that the mentioned objects were not found, and, therefore, collects 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 do not believe that you can (at least not use object references for your "next" and "prev" pointers) for the reason you quote: Object addresses are officially opaque. Although we could access the bits of the link, the JVM can move objects in memory (for example, when managing memory), and although I do not immediately find the specification for it, I believe that it is allowed to handle this by changing it (literally every update goes field and such where the old link is used, giving it a new link). Therefore, if we converted the object reference to long (for example), and then XOR'd, that with another object reference converted to long , if any object is moved (how can they do this), as soon as any of them is XOR 'back and converted back to an object reference, it may already be invalid.

Therefore, I think you need to use something other than object references for pointers, such as indexes, in a large array of object references, after which I am sure that you have lost the memory advantage in the XOR linked list.