python - 了解此示例代码中 ctypes 模块的用法

Question

上下文:
我发现一些代码实现了异或链表。在异或链表中，不是每个节点都有一个下一个指针，而是有一个 both 属性，该属性是前一个节点和下一个节点的异或。

import ctypes


# This is hacky. It's a data structure for C, not python.
class Node(object):
    def __init__(self, val):
        self.val = val
        self.both = 0


class XorLinkedList(object):
    def __init__(self):
        self.head = self.tail = None
        self.__nodes = [] # This is to prevent garbage collection

    def add(self, node):
        if self.head is None:
            self.head = self.tail = node
        else:
            self.tail.both = id(node) ^ self.tail.both
            node.both = id(self.tail)
            self.tail = node

        # Without this line, Python thinks there is no way to reach nodes between
        # head and tail.
        self.__nodes.append(node)


    def get(self, index):
        prev_id = 0
        node = self.head
        for i in range(index):
            next_id = prev_id ^ node.both

            if next_id:
                prev_id = id(node)
                node = _get_obj(next_id)
            else:
                raise IndexError('Linked list index out of range')
        return node


def _get_obj(id):
    return ctypes.cast(id, ctypes.py_object).value

问题:

1. 不明白 _get_obj() 函数的必要性及其尝试的用途在这里做什么？
2. self.__nodes = [] 有什么用处？以及它是如何实现的这里有垃圾收集吗？

3. 我不知道以下代码在做什么:

   # Without this line, Python thinks there is no way to reach nodes between
   # head and tail.
   self.__nodes.append(node)`
   

Answer 1

我可以回答您问题中的大部分子问题。

1. _get_obj() 函数是 Python 自己的逆函数id()函数(无论如何使用 CPython 解释器)。还有其他方法可以做到这一点。例如，参见问题 Is it possible to dereference variable id's? .

2. & 3. self.__nodes.append(node) 将 Node 实例添加到私有(private)列表，因为将其添加到 XOR 链表不会不要创建对它的引用，就像在更常见的正常实现中可能发生的那样(异或技巧消除了对它们的需要)。如果没有这个，Python 垃圾收集器可能会删除仍然是链接列表一部分的 Node 实例。