Why can't you build a xor linked list in python 3?

Question

I wanted to implement a xor linked list in python and I searched for it to try understand it better but the only thing related to python that I found was this stackoverflow post How to implement an XOR Linked List in Python? that says that it's impossible to implement a xor linked list in python. It said there that you can't mess with bits and pointers. I think that we can actually 'mess with bits', using bitwise operators ( for xor we would have ^ ) and what does it mean by pointers ? We can create a node class with a pointer property like we would do in a singly linked list :

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

And that would be our node with the 'pointer' -> .next. So, the question is, why can't we implement a XOR linked list in python and if we can, how ?

Answer 1

I could successfully implement an XOR linked list. Notice that in order to set a Node's neighbors, you have to pass both the neighbors. If you don't do that, it is not possible to calculate the address using XOR operation (address_store = prev_address ^ curr_address).

get_by_address(address) function will get you an object with a given id at runtime, and Node.get_address(node) will get you a Node's id. Clearly, it is possible to dereference an object in Python and also get its reference!

def get_by_address(address, global_vars):
    if address == 0:
        return None

    return [x for x in global_vars.values() if id(x) == address][0]

class Node(object):
    def __init__(self, data):
        self.data = data
        self.address_store = None

    def get_address(self):
        return id(self)

    def set_neighbors(self, prev_node=None, next_node=None):
        local_address = self.get_address()

        if prev_node == None:
            prev_address = 0
        else:
            prev_address = prev_node.get_address()

        if next_node == None:
            next_address = 0
        else:
            next_address = next_node.get_address()

        self.address_store = prev_address ^ next_address

    def get_next(self, prev_node, global_vars):
        if self.address_store == None:
            raise Exception('set_neighbors not called yet, no next node!')

        if prev_node == None:
            prev_address = 0
        else:
            prev_address = prev_node.get_address()

        next_address = self.address_store ^ prev_address

        return get_by_address(address=next_address, global_vars=global_vars)

    def get_prev(self, next_node, global_vars):
        if self.address_store == None:
            raise Exception('set_neighbors not called yet, no next node!')

        if next_node == None:
            next_address = 0
        else:
            next_address = next_node.get_address()

        prev_address = self.address_store ^ next_address

        return get_by_address(prev_address, global_vars=global_vars)

node1 = Node(data=1)
node2 = Node(data=2)
node3 = Node(data=3)

node1.set_neighbors(prev_node=None, next_node=node2)
node2.set_neighbors(prev_node=node1, next_node=node3)
node3.set_neighbors(prev_node=node2, next_node=None)

curr_node = node1
prev_node = None

print('Traversing forwards:')

print(str(None), '<->', end=' ')

while curr_node != None:
    print(curr_node.data, '<->', end=' '),

    prev_node_temp = curr_node
    curr_node = curr_node.get_next(prev_node=prev_node, global_vars=globals())
    prev_node = prev_node_temp

print(str(None))

curr_node = node3
prev_node = None

print('Traversing backwards:')

print(str(None), '<->', end=' ')

while curr_node != None:
    print(curr_node.data, '<->', end=' '),

    prev_node_temp = curr_node
    curr_node = curr_node.get_next(prev_node=prev_node, global_vars=globals())
    prev_node = prev_node_temp

print(str(None))

Output:

Traversing forwards:
None <-> 1 <-> 2 <-> 3 <-> None
Traversing backwards:
None <-> 3 <-> 2 <-> 1 <-> None