移除外部头引用后，ARC如何处理循环链表？

Question

我终于开始学习链表和所有相关知识了。我了解在垃圾收集环境中，当取消引用循环链表头时，整个列表最终都会被 GC。

我对 Objective-C 和 Swift 有很多经验，它们都使用自动引用计数而不是 GC。据我了解，这将创建一个强引用循环（as explained by Apple's ARC docs），因为头节点将持有对背面的强引用，这也持有对头的强引用。由于不小心这样做，我遇到了很强的保留周期。

在我看来，这会产生一个主要问题，因为它使循环链表完全不可释放，因为在 ARC 下，至少在 Objective C 和 Swift 下，您不能手动释放对象。

这里的解决方案是在每个节点上为 "front" 和 "back" 引用保留一个额外的弱引用属性，因为它们不能使用公共 next参考（因为这些需要很强，否则列表中间的节点将被释放）？或者我应该在删除对头部的最终引用之前通过破坏列表中的所有引用来伪手动释放我的列表？所有这些看起来都不够漂亮，而且比解决方案更多的是黑客。

Answer 1

确实，有一个循环链表，其中最后一个节点强烈引用第一个节点将导致第一个节点始终至少有一个引用，因此列表将始终保留在内存中。

虽然ARC Wikipedia article建议，有时这样的循环可以忽略，在这种情况下是不可接受的，因为作为数据结构设计者，我们不控制链表的大小——它可以而且应该能够根据定义无限增长。

我的解决方案是让节点知道它们的容器（即弱引用列表本身）。这样我们就可以通过使 next 成为节点的计算属性来删除循环引用。当实际的下一个节点被设置时，我们return它作为next。当它是 nil 时，我们 return container 的 startNode，所以我们有 API，它以循环链表的形式出现，但是在引擎盖下它只是一个普通的。

下面是一些代码示例：

class CircularLinkedList<T> {
    // MARK: - Internal structures
    class Node {
        let value: T
        private var _next: Node?

        weak fileprivate var container: CircularLinkedList<T>!

        var next: Node! {
            get {
                if let next = _next {
                    return next
                } else {
                    return container.startNode
                }
            }

            set {
                _next = newValue
            }
        }

        init(value: T) {
            self.value = value
        }
    }

    // MARK: - Properties
    var startNode: Node

    var endNode: Node

    // MARK: - Constructors
    init(initialValue: T) {
        startNode = Node(value: initialValue)
        endNode = startNode

        startNode.container = self
    }

    // MARK: - API
    func append(newValue: T) {
        let newNode = Node(value: newValue)
        newNode.container = self

        endNode.next = newNode
        endNode = newNode
    }
}

有人可能会说，让 Node 知道其容器列表并不是一个好主意 architecture-wise。但是使它成为 fileprivate 我们将它从外部世界隐藏起来，并且在我们知道我们应该正确使用它的数据结构内部。这似乎是比在列表的生命周期内手动中断引用循环更好的解决方案。

移除外部头引用后，ARC如何处理循环链表？

How does ARC deal with circular linked lists when the external head reference is removed?

algorithm

automatic-ref-counting

theory