Is it possible to create an XOR doubly-linked list in JavaScript?

Question

It appears that JavaScript objects aren't compatible with the ^ XOR operator. So is there any way to create an XOR doubly linked list?

I can do regular single/double linked lists fine. And I've searched on both SO and Google without success, so my guess is that it isn't possible. Or perhaps no one really cares about XOR lists...

var node = function(data, xor){
  this.data = data;
  this.xor = xor;
}
var myNode=new node('data', 0);
console.log(0 ^ myNode);  // shows 0, should show myNode
console.log(null ^ myNode);  // shows 0, too
console.log(5 ^ 0);  // 5 as expected

score 2 · Accepted Answer · answered Apr 12 '19 at 00:07

You can't implement a proper XOR linked list in JavaScript, because you can't access an object's memory address.

There's not really a practical reason to do this in JavaScript, either. From what I understand, the only benefit of an XOR linked list is a slightly reduced memory footprint. The amount of memory you would save with such a structure in JavaScript is offset by the overhead of the objects themselves.

Someone asked the same question about Python once; the answer also applies to JavaScript.

score 1 · Answer 2 · answered Apr 12 '19 at 04:58

Solely for the purpose of practice, I wrote a bit to simulate pointers using a map. Obviously, this is not for production code.

var node = function(data, xor){
  this.data = data;
  this.xor = xor;
}

var pointerFactory = function(){
    var pointers = {};
    var pointerCount = 0;
    this.get_pointer = function(node){
        if (pointers.hasOwnProperty(node)) return pointers[node];
        pointerCount++;
        pointers[node]=pointerCount;
        pointers[pointerCount]=node;
        return pointerCount;
    }
    this.dereference_pointer = function(pointer){
        return (pointers.hasOwnProperty(pointer)) ? pointers[pointer] : null;
    }
}

var myNode = new node('my data', 0);
var pf = new pointerFactory();
var p = pf.get_pointer(myNode);
console.log(pf.dereference_pointer(p).data); // my data
console.log(pf.dereference_pointer(2)); //null
console.log(0 ^ p);  // 1
console.log(p ^ p);  // 0

Is it possible to create an XOR doubly-linked list in JavaScript?

2 Answers2