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 ?

You might be able to mess with the result from id(). See this answer: https://stackoverflow.com/a/24815841/4834 — quamrana, Apr 26 '20 at 13:46
My implementation in one of the answers uses id() to get reference and uses a workaround for dereferencing. — nikhilbalwani, Apr 26 '20 at 17:32

nikhilbalwani · Accepted Answer · 2020-04-26T15:31:18.243

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

Roland Smith · Answer 2 · 2020-04-26T13:57:40.040

An xor linked list stores the xor of two addresses to save on storage space. This can be useful in low-level languages that manipulate memory addresses directly. In Python not so much, because in Python you're not handling memory directly.

Python names (variables) are references to objects that is managed by the Python runtime. But that reference isn't a memory address.

In CPython you can more or less get the address of an object by using the id() function, but this is an implementation detail of CPython, not a property of the language. Additionally, Python objects are a lot larger than you think they are. In C-like languages, an integer is usually 4 bytes.

Python provides the array for "efficient arrays of numeric values. Let's create an array of 4-byte integers;

In [5]: import array

In [6]: a = array.array('l', range(10))
Out[6]: array('l', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

Let's check out the differences between the addresses of the first and second item in the array:

In [7]: id(a[1]) - id(a[0])
Out[7]: 32

So on my machine, the size of a 4-byte integer as a CPython object is actually 32 bytes. This is basically because the Python runtime has to do a lot of work behind the scenes to manage the memory for you.

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

2 Answers2