pointers - 将 nil 分配给指针

Question

我正在尝试对列表实现 delete() 方法(无 HEAD 引用)

我发现我可以将参数修改为结构体。

func (l *LinkedList) Delete(n *Node) {
    if n.next == nil {
        n = nil
    } else {
        current := &n
        *n = *n.next
        *current = nil
    }

}

“else”部分工作正常，但删除最后一个节点不会修改列表

尝试使用

*n = nil

但是我遇到了编译错误。

cannot use nil as type Node in assignment

在这个 playground 中完成代码:

http://play.golang.org/p/Dhzyd7QHEw

Answer 1

你只是做错了。我的意思是从单链表中删除经典元素。正确的方法:

func (l *LinkedList) Delete(n *Node) {
    // if we want to delete the head element - just move the head pointer
    if l.head == n {
        l.head = n.next
        return
    }
    // otherwise find previous element to the one we are deleting
    current := l.head
    for current != nil && current.next != n {
        current = current.next
    }
    // and move that previous element next pointer to the next element
    if current != nil {
        current.next = n.next
    }
}

https://play.golang.org/p/_NlJw_fPWQD

那么你的例子有什么问题呢？在您的 Delete 函数中，您将收到指向某个节点的指针。这个指针对你的函数来说是局部的，它就像一个局部变量。将 nil 分配给函数内的局部变量并不重要。外面 - 没有人会看到这样的任务。您要做的是更改上一个列表项的 next 指针。这样该项目将不再在列表中。 GC 将删除实际分配的内存。

更新:

因为 go 指针是“真正的”指针，这可以在没有特殊情况下移除头部的情况下实现，通过使用额外的间接级别，正如 Linus 在其著名的 TED talk 中所建议的那样(以及更早的 slashdot Q&A - 请参阅“最喜欢的黑客”问题):

func (l *LinkedList) Delete(n *Node) {
    // initialize indirect with the address of a head pointer
    indirect := &(l.head)
    // until indirect has address of a pointer to the node we're deleting
    for *indirect != n {
        // check that it's not the end of the list
        if (*indirect).next == nil {
            // the node we're tryign to delete is not in the list
            return
        }
        // set indirect to the address of the next pointer
        indirect = &(*indirect).next
    }
    // indirect has address of a pointer we need to modify to delete the node
    *indirect = n.next
}

https://play.golang.org/p/hDy3hB5LUME

与删除 head 元素的简单特例相比，IMO 两级间接更难理解，但 Linus 并不完全是像我这样的普通开发人员:)