list - Golang 中 LinkedList 的等价物是什么

Question

在我的用例中，我想知道如何在 Go 中实现以下 Java 代码

class TreeNode {
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(){}
}

LinkedList<TreeNode> treeList = new LinkedList<TreeNode>();

我能够导入容器/列表包并添加接口(interface)。但它不允许任何通用对象。我是否必须使用 TreeNode 结构实现我自己的列表版本？

我只需要知道如何LinkedList<T>会在 Go 中工作。

编辑 1: 为了清楚起见，我在此处添加了完整的代码。我试图在二叉树的每个深度找到所有节点的链表。我使用了两个包列表和二叉树。你可以找到二进制树的源代码 here并列出 here .列表与容器/列表相同，但我添加了一些额外的功能

package main
import (
    "fmt"
    "go/chapter02-linkedlists/list"
    "go/chapter04-treesandgraphs/binarytree"
)
func main() {

    inArr := []int{4, 5, 7, 8, 9}
    t1 := binarytree.NewMinimalHeightBST(inArr, 0, len(inArr)-1)
    binarytree.InOrderTraverse(t1)
    var nodeList []*list.List

    nodeList = getLevelbasedList(t1, 0)

    fmt.Println()
    for _, value := range nodeList {
        fmt.Print("[ ")
        for x := value.Front(); x != nil; x = x.Next() {
            fmt.Print(x.Value.(int), " ")
        }
        fmt.Println("]")
    }
}

func getLevelbasedList(root *binarytree.Tree, level int) []*list.List {
    if root == nil {
        return nil
    }
    var nodeList []*list.List
    parents := list.New()
    current := list.New()

    current.PushFront(root)

    for current.Len() > 0 {
        nodeList = append(nodeList, current)
        parents = current
        current = list.New()

        for x := current.Front(); x != nil; x = x.Next() {
            node := x.Value.(*binarytree.Tree)
            if node.Left != nil {
                current = current.PushFront(node.Left)
            }
            if node.Right != nil {
                current = current.PushFront(node.Right)
            }
        }
        return nodeList
    }
}

错误是，

./question4_4b.go:56: cannot use current.PushFront((interface {})(node.Left)) (type *list.Element) as type *list.List in assignment
./question4_4b.go:59: cannot use current.PushFront((interface {})(node.Right)) (type *list.Element) as type *list.List in assignment

编辑 2: 根据我编辑的 JamesHenstridge 的评论

current = current.PushFront(node.Left)

到

current.PushFront(node.Left)

然后问题就解决了。但是现在我得到接口(interface)转换错误，

[ panic: interface conversion: interface is *binarytree.Tree, not int

goroutine 1 [running]:

Answer 1

Go 不支持泛型类型(参见 FAQ 问题 Why does Go not have generic types?)。

你必须使用 Type assertions获取您想要的键入值。

例如创建你的 TreeNode 类型:

type TreeNode struct {
    Data  int
    Left  *TreeNode
    Right *TreeNode
}

并遍历包含 TreeNode 值的列表:

l := list.New()
// Populate list

for e := l.Front(); e != nil; e = e.Next() {
    if tn, ok := e.Value.(TreeNode); ok {
        // do something with tn which is of type TreeNode
        fmt.Println(tn)
    } else {
        // e.Value is not of type TreeNode
    }
}

如果你组装列表并且你可以确定它只包含TreeNode类型的值，你可以省略类型断言中的错误检查，它变成这样:

for e := l.Front(); e != nil; e = e.Next() {
    // if e.Value would not be of type TreeNode, run-time panic would occur
    tn := e.Value.(TreeNode) // tn is of type TreeNode
    fmt.Println(tn)

}

编辑:

你得到的错误:

cannot use current.PushFront((interface {})(node.Left)) (type *list.Element)
    as type *list.List in assignment

在线:

current = current.PushFront(node.Left)

current 变量是 list.List 类型，方法 current.PushFront() 返回一个 类型的值*列表.元素。这是 2 种不同的类型，您不能将 *Element 分配给类型为 List 的变量。

编辑 2:

你的第二个错误:

panic: interface conversion: interface is *binarytree.Tree, not int

是线路造成的:

fmt.Print(x.Value.(int), " ")

您尝试断言值 x.Value 的类型为 int 但事实并非如此! x.Value 是 *binarytree.Tree 类型，因此断言显然会失败。