Golang 中 LinkedList<T> 的等价物是什么

Question

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

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

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

我可以导入 container/list 包并添加接口。但它不允许任何通用对象。我是否必须使用 TreeNode 结构实现我自己的列表版本？

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

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

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)

问题已解决。但是现在我得到接口转换错误，

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

goroutine 1 [running]:

Answer 1

Go 不支持泛型类型（参见常见问题 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
    }
}

如果你assemble这个列表，你可以确定它只包含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() returns 的值类型为 *list.Element。这是 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 所以断言显然会失败。

Golang 中 LinkedList<T> 的等价物是什么

What is the equivalent for LinkedList<T> in Golang

struct

linked-list

list

go