Swift中结构体Node+类LinkedList的链表实现问题求助

这个问题我之前也碰到过，Swift的值类型特性确实会在这里给我们挖个小坑😅。先给你解释下为什么会报错：

结构体是值类型，每个值类型实例的内存大小在编译期就需要确定。如果结构体里直接存储自身类型的属性（哪怕是可选型），会导致无限递归的内存计算——Node包含Node，里面又包含Node，编译器根本算不出这个结构体到底要占多大内存，所以就会抛出value type 'Node' cannot have a stored property that references itself的错误。

解决方案：用引用类型包装下一个节点 #

我们可以用一个极简的类来包装下一个Node实例，因为类是引用类型，它的实例存储在堆上，结构体里只需要存一个指向这个类实例的指针（固定大小），就能完美避开值类型递归的问题。

下面是完整的实现代码：

1. 定义Node结构体和包装类

// 链表节点：结构体，存储值和下一个节点的包装器
struct Node<T> {
    let value: T
    var next: NodeWrapper<T>?
}

// 节点包装器：类，用来解决结构体无法引用自身的问题
class NodeWrapper<T> {
    var node: Node<T>
    
    init(node: Node<T>) {
        self.node = node
    }
}

2. 实现LinkedList类

class LinkedList<T> {
    // 链表的头节点包装器
    private var head: NodeWrapper<T>?
    
    // 向链表末尾添加节点
    func append(_ value: T) {
        let newNode = Node(value: value, next: nil)
        let newWrapper = NodeWrapper(node: newNode)
        
        // 如果链表为空，直接把头节点设为新节点
        guard var currentWrapper = head else {
            head = newWrapper
            return
        }
        
        // 遍历到链表最后一个节点
        while let nextWrapper = currentWrapper.node.next {
            currentWrapper = nextWrapper
        }
        
        // 把新节点挂到最后一个节点的next上
        currentWrapper.node.next = newWrapper
    }
    
    // 遍历链表，返回所有值的数组
    func traverse() -> [T] {
        var result = [T]()
        var currentWrapper = head
        
        while let wrapper = currentWrapper {
            result.append(wrapper.node.value)
            currentWrapper = wrapper.node.next
        }
        
        return result
    }
    
    // 可选：实现插入节点的方法
    func insert(at index: Int, value: T) {
        let newNode = Node(value: value, next: nil)
        let newWrapper = NodeWrapper(node: newNode)
        
        // 插入到头部的情况
        if index == 0 {
            newWrapper.node.next = head
            head = newWrapper
            return
        }
        
        var currentIndex = 0
        var currentWrapper = head
        
        // 找到目标位置的前一个节点
        while currentIndex < index - 1, let nextWrapper = currentWrapper?.node.next {
            currentWrapper = nextWrapper
            currentIndex += 1
        }
        
        guard let targetPrevWrapper = currentWrapper else {
            // 如果索引超出范围，默认添加到末尾
            append(value)
            return
        }
        
        // 插入新节点
        newWrapper.node.next = targetPrevWrapper.node.next
        targetPrevWrapper.node.next = newWrapper
    }
}

3. 使用示例

// 创建一个存储Int的链表
let numberList = LinkedList<Int>()
numberList.append(10)
numberList.append(20)
numberList.append(30)
print(numberList.traverse()) // 输出：[10, 20, 30]

// 插入节点到索引1的位置
numberList.insert(at: 1, value: 15)
print(numberList.traverse()) // 输出：[10, 15, 20, 30]

补充说明 #

你之前尝试的Next类思路是对的，可能是没处理好包装逻辑或者可选链的遍历问题。上面的实现里，NodeWrapper就是起到了类似Next类的作用——用引用类型来打破值类型的递归依赖。

如果之后需要扩展链表的功能（比如删除节点、反转链表等），只需要在LinkedList类里添加对应的方法即可，核心的节点结构不需要改动。

内容的提问来源于stack exchange，提问作者Mohan Patil