algorithm - 移除外部头引用后，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这表明，有时可以忽略这样的循环，在这种情况下这是 Not Acceptable ，因为作为数据结构设计者，我们无法控制链表的大小——根据定义，它可以而且应该能够无限增长。

我的解决方案是让节点知道它们的容器(即弱引用列表本身)。这样我们就可以通过使 next 成为节点的计算属性来移除循环引用。设置实际的下一个节点后，我们将其作为 next 返回。当它是 nil 时，我们返回 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 知道它的容器列表在架构方面并不是一个好主意。但是将它设置为 fileprivate 我们将它从外部世界隐藏起来，并且在我们知道我们应该正确使用它的数据结构中。这似乎是比在列表的生命周期内手动中断引用循环更好的解决方案。