英文:
How to implement a linked list
问题
我正在尝试在Go语言中实现一个有序链表,但是我很难找到一种通用的方法,使得链表可以适用于任何可以与自身进行比较的类型。由于这是一个有序列表,我希望“Go编译器”能够确保插入链表的值是可以进行比较的。
例如,
import "linkedlist"
type Person struct {
name string
}
func main() {
l := linkedlist.New()
p := Person{"Jay"}
l.insert(p)
}
在上面的示例中,我如何让编译器确保具有类型Person
的值p
可以与另一个具有相同类型的值进行比较。我希望编译器能够在插入不合适的值时捕获错误。
我可以这样做,
import "linkedlist"
type Element interface {
func IsGreater(v Element{}) bool
}
type Person struct {
name string
age int
}
func (p *Person) IsGreater(p1 interface{}) bool {
if ok, v := p1.(Person); ok && p.age > v.age {
return true
}
return false
}
然后,在链表的“insert”函数中,我可以使用IsGreater
函数来决定在链表中放置元素的位置。
我的问题是...
- 有没有更好的方法来做到这一点?有没有比上面的解决方案更好的方法?
我已经研究了sort.Sort
并看到了它在该包中的实现方式。在那里的实现方式是为切片类型创建一个新类型,然后通过实现Len
、Less
和Swap
来使该新类型满足排序接口。
在我的情况下,我可能也可以做同样的事情。但是,当我一次只处理两个相同类型的值时,需要创建一个新的切片类型,然后实现几个函数来满足接口,似乎有点过度设计。
英文:
I'm trying to implement a sorted linked list in Go. And I'm having a hard time coming up with a generic way to make the linked list work with any type that can by compared with itself. Since its a sorted list, I want the 'go compiler' to ensure that the values being inserted into the linked list can be compared.
For example,
import "linkedlist"
type Person struct {
name string
}
func main() {
l := linkedlist.New()
p := Person{"Jay"}
l.insert(p)
}
In the above example, how do I make the compiler ensure that the value 'p' which has type 'Person' can be compared with another value which also has type 'Person'. I want the compiler to catch the error in those situations where the value being inserted is not an appropriate value.
I can do something like this,
import "linkedlist"
type Element interface {
func IsGreater(v Element{}) bool
}
type Person struct {
name string
age int
}
func (p *Person) IsGreater(p1 interface{}) bool {
if ok, v := p1.(Person); ok && p.age > v.age {
return true
}
return false
}
And then, within the "insert" function of the linked list I can use the IsGreater
function to decide where to place the Element in the linked list.
My question is...
- Is there a better way to do this? Something that is a lot better than the solution above.
I've already gone through sort.Sort and seen how its done in that package. The way its done there is to create a new type for a slice of the type and then make that new type fulfill the sort interface by implementing Len, Less and Swap.
I can probably do the same thing here in my case as well. But having to create a new slice type and then implement a few functions to satisfy an interface, when I'll only be dealing with 2 values of the same type at a time.. seems a bit overkill to me.
答案1
得分: 1
因为Golang不支持泛型,所以所有的容器都应该使用interface{}和类型断言,我认为对于你的需求没有更好的解决方案。
英文:
Because Golang do not support generics, So all of containers should use interface{} and type assert, I think no better solution for your requirement.
答案2
得分: 0
这里已经存在用于此目的的库函数:
http://golang.org/pkg/container/list/
http://golang.org/pkg/container/ring/
你可以使用 reflect.DeepEqual
来比较这些列表。
如果你想要实现一个使用类型检查的链表,可以创建一个嵌入式结构体作为列表的类型 type MyLinkedList struct { *list.List}
,以及一个作为列表中元素的类型 type Element struct{ *List.Element }
。然后,你可以实现 list.List
的所有方法,并根据需要进行类型检查的重写。
英文:
Library functions for this already exist:
http://golang.org/pkg/container/list/
http://golang.org/pkg/container/ring/
You can compare the lists with reflect.DeepEqual
.
If you want to implement a linked list that uses type checking, make an embedded struct for the list type MyLinkedList struct { *list.List}
and one for the items in the list type Element struct{ *List.Element }
. You can then implement all the methods of list.List
and over-ride as necessary with your type checks.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论