我想在python中实现xor链表，我搜索了它，试图更好地理解它，但我发现的唯一与python相关的是这篇stackoverflow文章如何在python中实施xor链表？这说明在python中实现xor链表是不可能的。它在那里说，你不能搞砸比特和指针。我认为我们实际上可以使用逐位运算符(对于xor，我们会有^(来"乱比特"，指针是什么意思？我们可以创建一个具有指针属性的节点类，就像我们在单链表中所做的那样：
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
这将是我们的节点"指针"->next。所以，问题是，为什么我们不能在python中实现XOR链表？如果可以，如何实现？
我可以成功地实现XOR链表。请注意，为了设置Node的邻居，您必须传递这两个邻居。如果不这样做，就不可能使用XOR运算(address_store = prev_address ^ curr_address(来计算地址。
get_by_address(address)函数将在运行时为您获取一个具有给定id的对象，Node.get_address(node)将为您获取Node的id。很明显，可以在Python中取消引用对象并获取其引用！
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))
输出：
Traversing forwards:
None <-> 1 <-> 2 <-> 3 <-> None
Traversing backwards:
None <-> 3 <-> 2 <-> 1 <-> None
异或链表存储两个地址的异或以节省存储空间。这在直接操作内存地址的低级语言中非常有用。在Python中就不那么多了，因为在Python中，您不直接处理内存。
Python名称(变量(是对由Python运行时管理的对象的引用但那个引用不是内存地址
在CPython中，您可以使用id()函数或多或少地获取对象的地址，但这是CPython的实现细节，而不是语言的属性。此外，Python对象比您想象的要大得多。在类C语言中，一个整数通常是4个字节。
Python为"有效的数值数组"提供了array。让我们创建一个4字节整数数组；
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])
让我们检查一下数组中第一个和第二个项目的地址之间的差异：
In [7]: id(a[1]) - id(a[0])
Out[7]: 32
因此，在我的机器上，作为CPython对象的4字节整数的大小实际上是32字节。这基本上是因为Python运行时必须在后台做大量工作来为您管理内存。