英文:
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: 为了明确起见,我在这里添加了完整的代码。我正在尝试找到二叉树中每个深度的所有节点的链表。我使用了两个包list
和binarytree
。你可以在这里找到二叉树的源代码,这里找到列表的源代码。列表与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<TreeNode> treeList = new LinkedList<TreeNode>();
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<T>
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 (
"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
}
}
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), " ")
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论