列表中是否有任何自引用列表或循环引用的用法，例如。将列表附加到自身

Question

因此，如果我有一个列表 a 并将 a 附加到它，我将得到一个包含它自己的引用的列表。

>>> a = [1,2]
>>> a.append(a)
>>> a
[1, 2, [...]]
>>> a[-1][-1][-1]
[1, 2, [...]]

这基本上导致看似无限的递归。

不仅在列表中，在字典中也是如此：

>>> b = {'a':1,'b':2}
>>> b['c'] = b
>>> b
{'a': 1, 'b': 2, 'c': {...}}

将列表存储在最后一个元素中并修改其他元素可能是一种好方法，但这行不通，因为更改将在每个递归引用中看到。

我明白为什么会发生这种情况，即由于它们的可变性。但是，我对这种行为的实际用例很感兴趣。有没有大神能指教一下？

Answer 1

However, I am interested in actual use-cases of this behavior. Can somebody enlighten me?

我认为对此没有很多有用的用例。允许这样做的原因是因为它可能有一些实际用例并且禁止它会使这些容器的性能变差或增加它们的内存使用量。

Python 是动态类型的，您可以将任何 Python 对象添加到 list。这意味着需要采取特殊的预防措施来禁止向自己添加列表。这与（大多数）类型化语言不同，因为类型化系统，这种情况不会发生。

因此，为了禁止这种递归数据结构，如果新添加的对象已经参与数据结构的更高层，则需要检查每个 addition/insertion/mutation。这意味着在最坏的情况下，它必须检查新添加的元素是否在 anywhere 可以参与递归数据结构的地方。这里的问题是同一个列表可以在多个地方引用，并且可以已经是多个数据结构的一部分，并且 list/dict 之类的数据结构可以（几乎）任意深。该检测要么很慢（例如线性搜索），要么会占用相当多的内存（查找）。所以简单地允许它更便宜。

之所以 Python 在打印时检测到这一点，是因为您不希望解释器进入无限循环，或者出现 RecursionError 或 Whosebug。这就是为什么对于某些操作，如打印（以及深度复制）Python 临时创建一个查找来检测这些递归数据结构并适当地处理它们。

Answer 2

考虑构建一个解析数字串的状态机检查是否可以除以 25 你可以将每个节点建模为具有 10 个传出方向的列表考虑一些连接到它们自己

def canDiv25(s):
  n0,n1,n1g,n2=[],[],[],[]
  n0.extend((n1,n0,n2,n0,n0,n1,n0,n2,n0,n0))
  n1.extend((n1g,n0,n2,n0,n0,n1,n0,n2,n0,n0))
  n1g.extend(n1)
  n2.extend((n1,n0,n2,n0,n0,n1g,n0,n2,n0,n0))
  cn=n0
  for c in s:
    cn=cn[int(c)]
  return cn is n1g

for i in range(144):
  print("%d %d"%(i,canDiv25(str(i))),end='\t')

虽然这个状态机本身没有什么实际意义，但它显示了可能发生的情况。或者你可以有一个简单的冒险游戏，其中每个房间都表示为一个字典，你可以去例如 NORTH，但在那个房间里当然有一个返回 link 到 SOUTH。有时游戏开发者也会这样做，例如在某些地牢中模拟一条棘手的路径，北方向的路径将指向房间本身。

Answer 3

它的一个非常简单的应用是循环链表，其中列表中的最后一个节点引用第一个节点。这些对于创建无限资源、状态机或一般图形很有用。

def to_circular_list(items):
  head, *tail = items
  first = { "elem": head }
  current = first
  for item in tail:
    current['next'] = { "elem": item }
    current = current['next']
  current['next'] = first
  return first

to_circular_list([1, 2, 3, 4])

如果这与自引用对象的关系不是很明显，请考虑如果您只调用 to_circular_list([1]) 会发生什么，您最终会得到一个看起来像 [=13= 的数据结构]

item = {
  "elem": 1,
  "next": item
}

如果语言不支持这种直接的自引用，就不可能在 Python.[=13] 中使用循环链表和许多其他依赖自引用的概念作为工具=]

Answer 4

用例是 Python 是一种 动态类型语言 ，其中任何东西都可以引用任何东西，包括它自身。

列表元素是对其他对象的引用，就像字典中的变量名和属性以及键和值一样。引用没有类型，变量或列表不限于仅引用，比如说，整数或浮点值。每个引用都可以引用任何有效的 Python 对象。（Python 也是 强类型 ，因为对象有一个不会改变的特定类型；字符串仍然是字符串，列出保留列表）。

所以，因为 Python 是动态类型的，所以如下：

foo = []
# ...
foo = False

有效，因为 foo 不限于特定类型的对象，Python 列表对象也是如此。

当您的语言允许此时，您必须考虑递归结构，因为允许容器引用自身，直接或间接地。 list 表示通过在执行此操作时不会爆炸并要求字符串表示来考虑这一点。当存在循环引用时，它会向您显示 [...] 条目。这不仅适用于直接引用，您也可以创建间接引用：

>>> foo = []
>>> bar = []
>>> foo.append(bar)
>>> bar.append(foo)
>>> foo
[[[...]]]

foo 是最外面的 [/]] 对和 [...] 条目。 bar 是中间的 [/] 对。

在许多实际情况下您会需要自引用（循环）结构。例如，内置 OrderedDict 对象使用循环链表来跟踪项目顺序。这通常不容易看到，因为有该类型的 C 优化版本，但我们可以强制 Python 解释器使用纯 Python 版本（你想使用新的解释器，这有点骇人听闻):

>>> import sys
>>> class ImportFailedModule:
...     def __getattr__(self, name):
...         raise ImportError
...
>>> sys.modules["_collections"] = ImportFailedModule()  # block the extension module from being loaded
>>> del sys.modules["collections"]  # force a re-import
>>> from collections import OrderedDict

现在我们有了一个纯python版本，我们可以自省：

>>> od = OrderedDict()
>>> vars(od)
{'_OrderedDict__hardroot': <collections._Link object at 0x10a854e00>, '_OrderedDict__root': <weakproxy at 0x10a861130 to _Link at 0x10a854e00>, '_OrderedDict__map': {}}

因为这个有序的字典是空的，根引用它自己：

>>> od._OrderedDict__root.next is od._OrderedDict__root
True

就像列表可以引用自己一样。添加一两个键，链表会增长，但最终会保持与自身的链接：

>>> od["foo"] = "bar"
>>> od._OrderedDict__root.next is od._OrderedDict__root
False
>>> od._OrderedDict__root.next.next is od._OrderedDict__root
True
>>> od["spam"] = 42
>>> od._OrderedDict__root.next.next is od._OrderedDict__root
False
>>> od._OrderedDict__root.next.next.next is od._OrderedDict__root
True

循环链表使得更改键顺序变得容易，而无需重建整个底层哈希 table。

Answer 5

这可能的原因仅仅是因为 Python 的语法没有禁止它，就像任何 C 或 C++ 对象都可以包含对自身的引用一样。一个例子可能是：https://www.geeksforgeeks.org/self-referential-structures/

正如@MSeifert 所说，如果您尝试从列表本身重复访问列表，您通常会在某个时候遇到 RecursionError。使用这种模式的代码如下：

a = [1, 2]
a.append(a)

def loop(l):
    for item in l:
        if isinstance(item, list):
            loop(l)
        else: print(item)

最终会在没有某种条件的情况下崩溃。我相信连print(a)也会崩溃。然而：

a = [1, 2]
while True:
    for item in a:
        print(item)

将运行无限地具有与上述相同的预期输出。很少有递归问题不分解为简单的 while 循环。有关确实需要自引用结构的递归问题的示例，请查看 Ackermann 函数：http://mathworld.wolfram.com/AckermannFunction.html。可以修改此函数以使用自引用列表。

当然有自引用容器或树结构的先例，特别是在数学中，但在计算机上它们都受到调用堆栈大小和 CPU 时间的限制，因此研究起来不切实际他们没有某种约束。

列表中是否有任何自引用列表或循环引用的用法，例如。将列表附加到自身

Is there any usage of self-referential lists or circular reference in list, eg. appending a list to itself

python

list

dictionary

circular-reference

circular-list