在Golang中,LinkedList的等效类型是list.List。

huangapple go评论82阅读模式
英文:

What is the equivalent for LinkedList<T> in Golang

问题

在我的使用案例中,我想知道以下Java代码在Go中如何实现:

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: 为了明确起见,我在这里添加了完整的代码。我正在尝试找到二叉树中每个深度的所有节点的链表。我使用了两个包listbinarytree。你可以在这里找到二叉树的源代码,这里找到列表的源代码。列表与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.PushFront(node.Left)
            }
            if node.Right != nil {
                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]:
英文:

In my use case, I would like to know how the following Java code would be implemented in Go

class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(){}
}
LinkedList&lt;TreeNode&gt; treeList = new LinkedList&lt;TreeNode&gt;();

I am able to import the container/list package and add an interface. But it is not allowing any generic object. Do I have to implement my own version of list with TreeNode struct?

I just need to know how LinkedList&lt;T&gt; would work in Go.

EDIT 1: To make it clear, I am adding the complete code here. I am trying to find the linked list of all nodes at each depth in a binary tree. I used two packages list and binary tree. You can find the source code for binarytree here and list here. list is same as container/list but I added few extra functions

package main
import (
&quot;fmt&quot;
&quot;go/chapter02-linkedlists/list&quot;
&quot;go/chapter04-treesandgraphs/binarytree&quot;
)
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(&quot;[ &quot;)
for x := value.Front(); x != nil; x = x.Next() {
fmt.Print(x.Value.(int), &quot; &quot;)
}
fmt.Println(&quot;]&quot;)
}
}
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() &gt; 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
}
}

And the error is,

./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

EDIT 2: Based on JamesHenstridge's comment I edited from

current = current.PushFront(node.Left)

to

current.PushFront(node.Left)

And the issue resolved. But now I am getting interface conversion error,

[ panic: interface conversion: interface is *binarytree.Tree, not int
goroutine 1 [running]:

答案1

得分: 10

Go语言不支持泛型类型(参见FAQ问题为什么Go语言不支持泛型类型?)。

你需要使用类型断言来获取你想要的类型化值。

例如,创建你的TreeNode类型:

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

然后遍历包含TreeNode值的列表:

l := list.New()
// 填充列表

for e := l.Front(); e != nil; e = e.Next() {
    if tn, ok := e.Value.(TreeNode); ok {
        // 对类型为TreeNode的tn进行操作
        fmt.Println(tn)
    } else {
        // e.Value不是TreeNode类型
    }
}

如果你组装的列表中只包含TreeNode类型的值,你可以省略类型断言中的错误检查,代码如下:

for e := l.Front(); e != nil; e = e.Next() {
    // 如果e.Value不是TreeNode类型,会发生运行时错误
    tn := e.Value.(TreeNode) // tn的类型为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()方法返回的是*list.Element类型的值。这是两种不同的类型,你不能将*Element赋值给类型为List的变量。

编辑2:

你的第二个错误:

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

是由以下代码行引起的:

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

你试图断言x.Value的类型为int,但实际上它的类型是*binarytree.Tree,所以断言显然会失败。

英文:

Go doesn't support generic types (see FAQ question Why does Go not have generic types?).

You have to use Type assertions to obtain the typed value you want.

E.g. create your TreeNode type:

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

And to iterate over a list containing TreeNode values:

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
}
}

If you assemble the list and you can be sure it only contains values of type TreeNode, you can omit the error check in the type assertion and it becomes like this:

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)
}

Edit:

The error you're getting:

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

At line:

current = current.PushFront(node.Left)

The current variable is of type list.List, and the method current.PushFront() returns a value of type *list.Element. These are 2 different types, you can't assign a *Element to a variable that has a type of List.

Edit 2:

Your 2nd error:

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

Is caused by the line:

fmt.Print(x.Value.(int), &quot; &quot;)

You try to assert that the value x.Value is of type int but it isn't! x.Value is of type *binarytree.Tree so the assertion will obviously fail.

huangapple
  • 本文由 发表于 2015年2月25日 16:47:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/28714641.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定