如何实现链表

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

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函数来决定在链表中放置元素的位置。

我的问题是...

  1. 有没有更好的方法来做到这一点?有没有比上面的解决方案更好的方法?

我已经研究了sort.Sort并看到了它在该包中的实现方式。在那里的实现方式是为切片类型创建一个新类型,然后通过实现LenLessSwap来使该新类型满足排序接口。

在我的情况下,我可能也可以做同样的事情。但是,当我一次只处理两个相同类型的值时,需要创建一个新的切片类型,然后实现几个函数来满足接口,似乎有点过度设计。

英文:

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

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

huangapple
  • 本文由 发表于 2014年2月11日 13:09:28
  • 转载请务必保留本文链接:https://go.coder-hub.com/21693619.html
匿名

发表评论

匿名网友

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

确定