关于ring，可以参考Golang源码 container 系列一 ring环形链表,list也是个链表，但是稍有差别。
参考【Go】笔记五 | container包中的list与ring
一、基本用法
type Element struct {
Value interface{} //在元素中存储的值
}
- func (e *Element) Next() *Element //返回该元素的下一个元素，如果没有下一个元素则返回nil
- func (e *Element) Prev() *Element//返回该元素的前一个元素，如果没有前一个元素则返回nil。
type List
- func New() *List //返回一个初始化的list
- func (l *List) Back() *Element //获取list l的最后一个元素
- func (l *List) Front() *Element //获取list l的第一个元素
- func (l *List) Init() *List //list l初始化或者清除list l
- func (l *List) InsertAfter(v interface{}, mark *Element) *Element //在list l中元素mark之后插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。
- func (l *List) InsertBefore(v interface{}, mark *Element) *Element//在list l中元素mark之前插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。
- func (l *List) Len() int //获取list l的长度
- func (l *List) MoveAfter(e, mark *Element) //将元素e移动到元素mark之后，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。
- func (l *List) MoveBefore(e, mark *Element)//将元素e移动到元素mark之前，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。
- func (l *List) MoveToBack(e *Element)//将元素e移动到list l的末尾，如果e不属于list l，则list不改变。
- func (l *List) MoveToFront(e *Element)//将元素e移动到list l的首部，如果e不属于list l，则list不改变。
- func (l *List) PushBack(v interface{}) *Element//在list l的末尾插入值为v的元素，并返回该元素。
- func (l *List) PushBackList(other *List)//在list l的尾部插入另外一个list，其中l和other可以相等。
- func (l *List) PushFront(v interface{}) *Element//在list l的首部插入值为v的元素，并返回该元素。
- func (l *List) PushFrontList(other *List)//在list l的首部插入另外一个list，其中l和other可以相等。
- func (l *List) Remove(e *Element) interface{}//如果元素e属于list l，将其从list中删除，并返回元素e的值。
二、并发安全的list
参考golang list使用
最近需要使用到一个Queue队列, 并发写入的.
作为gopher, 第一个马上想到的是channel, channel用起来是很爽, 并发安全, 直接一端取, 一端塞, 非常和谐友好. 但是, channel不支持动态扩容啊, 当一个channel满了之后, 想要扩容, 只能make一个新的, 然后做一个迁移, 这会卡住好长时间, 业务需求不满足.
然后找到了container/list这个包, 有个list结构体, 使用简单, 接口清晰, 代码实现也简单, 用着也挺舒服的. 就是不是并发安全的, 只能自己动手包了一层并发的皮:
import (
"container/list"
"sync"
)
type Queue struct {
l *list.List
m sync.Mutex
}
func NewQueue() *Queue {
return &Queue{l: list.New()}
}
func (q *Queue) PushBack(v interface{}) {
if v == nil {
return
}
q.m.Lock()
defer q.m.Unlock()
q.l.PushBack(v)
}
func (q *Queue) Front() *list.Element {
q.m.Lock()
defer q.m.Unlock()
return q.l.Front()
}
func (q *Queue) Remove(e *list.Element) {
if e == nil {
return
}
q.m.Lock()
defer q.m.Unlock()
q.l.Remove(e)
}
func (q *Queue) Len() int {
q.m.Lock()
defer q.m.Unlock()
return q.l.Len()
}
这样就基本满足了.
使用过程中, 发现list有个小坑: 遍历的时候不能Remove
for e := l.Front(); e != nil; e = e.Next {
l.Remove(e)
}
按照设想, 这应该会移除list里所有的元素, 但是, 结果是只移除了第一个. 原因是: Remove时候, e.next = nil, 使得for判断中, e != nil不成立了, 所以退出了循环.
这时候有两种解决办法:
var next *list.Element
for e := l.Front(); e != nil; e = next {
next = e.Next()
l.Remove(e)
}
for {
e := l.Front()
if e == nil {
break
}
l.Remove(e)
}
三、 参考go实现排序的链表
package codeforfun
import (
"container/list"
)
type SortedLinkedList struct {
*list.List
Limit int
compareFunc func (old, new interface{}) bool
}
func NewSortedLinkedList(limit int, compare func (old, new interface{}) bool) *SortedLinkedList {
return &SortedLinkedList{list.New(), limit, compare}
}
func (this SortedLinkedList) findInsertPlaceElement(value interface{}) *list.Element {
for element := this.Front(); element != nil; element = element.Next() {
tempValue := element.Value
if this.compareFunc(tempValue, value) {
return element
}
}
return nil
}
func (this SortedLinkedList) PutOnTop(value interface{}) {
if this.List.Len() == 0 {
this.PushFront(value)
return
}
if this.List.Len() < this.Limit && this.compareFunc(value, this.Back().Value) {
this.PushBack(value)
return
}
if this.compareFunc(this.List.Front().Value, value) {
this.PushFront(value)
} else if this.compareFunc(this.List.Back().Value, value) && this.compareFunc(value, this.Front().Value) {
element := this.findInsertPlaceElement(value)
if element != nil {
this.InsertBefore(value, element)
}
}
if this.Len() > this.Limit {
this.Remove(this.Back())
}
}
使用方法
package main
import (
"fmt"
"codeforfun"
)
type WordCount struct {
Word string
Count int
}
func compareValue(old, new interface {}) bool {
if new.(WordCount).Count > old.(WordCount).Count {
return true
}
return false
}
func main() {
wordCounts := []WordCount{
WordCount{"kate", 87},
WordCount{"herry", 92},
WordCount{"james", 81}}
var aSortedLinkedList = codeforfun.NewSortedLinkedList(10, compareValue)
for _, wordCount := range wordCounts {
aSortedLinkedList.PutOnTop(wordCount)
}
for element := aSortedLinkedList.List.Front(); element != nil; element = element.Next() {
fmt.Println(element.Value.(WordCount))
}
}
四、Ring和List源码对比
type Ring struct {
next, prev *Ring
Value interface{}
}
// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value interface{}
}
// New creates a ring of n elements.
func New(n int) *Ring {
if n <= 0 {
return nil
}
r := new(Ring)
p := r
for i := 1; i < n; i++ {
p.next = &Ring{prev: p}
p = p.next
}
p.next = r
r.prev = p
return r
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
// Init initializes or clears list l.
func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}
// New returns an initialized list.
func New() *List { return new(List).Init() }
五、Ring和List区别
1.经过语句var l list.List声明的变量l的值将会是怎样的？
这个零值将会是一个长度为0的链表。这个链表持有的根元素也将会是一个空壳，其中只会包含缺省的内容。
2.那这样的链表我们可以直接拿来使用吗？
可以的。这被称为“开箱即用”。Go 语言标准库中的很多结构体，都做到了开箱即用。这也是在编写可供别人使用的代码包（或者说.程序库）时我们推荐遵循的最佳实践之一。
3.可以把自己生成的Element类型值传给链表吗？
不会接受，这些方法将不会对链表做出任何改动。因为我们自己生成的值并不在链表中，所以也就谈不上“在链表中移动元素”。更何况链表不允许我们把自己生成的值插入其中。
4.为什么不接受自己生成的Element类型值？
在List包含的方法中，用于插入新元素的那些方法都只接受interface{}类型的值。这些方法在内部会使用Element值包装接收到的新元素。这样做正是为了避免直接使用我们自己生成的元素，主要原因是避免链表的内部关联遭到外界破坏，这对于链表本身以及我们这些使用者来说，都是有益的。
//InsertBefore和InsertAfter分别用于在指定的元素之前和之后插入数据.
//PushFront和PushBack则是向链表最前端和最后端插入数据.
func (l *List) InsertBefore( v interface{}, mark *Element) *Element
func (l *List) InsertAfter (v interface{},mark *Element) *Element
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element
5.Ring与List的区别在哪儿？
container/ring包中的Ring类型实现的是一个循环链表，也就是我们俗称的环。其实List在内部就是一个循环链表。它的根元素永远不会持有任何实际的元素值，而该元素的存在，就是为了连接这个循环链表的首尾两端。
所以也可以说，List的零值是一个只包含了根元素，但不包含任何实际元素值的空链表。两者本质都是循环链表，最主要的不同有下面几种。
- Ring类型的数据结构仅由它自身即可代表，而List类型则需要由它以及Element类型联合表示。这是表示方式上的不同，也是结构复杂度上的不同。
- 一个Ring类型的值严格来讲，只代表了其所属的循环链表中的一个元素，而一个List类型的值则代表了一个完整的链表。这是表示维度上的不同。
- 在创建并初始化一个Ring值的时候，我们可以指定它包含的元素的数量，但是对于一个List值来说，却不能这样做（也没有必要这样做）。循环链表一旦被创建，其长度是不可变的。这是两个代码包中的New函数在功能上的不同，也是两个类型在初始化值方面的第一个不同。
- 仅通过var r ring.Ring语句声明的r将会是一个长度为1的循环链表，而List类型的零值则是一个长度为0的链表。别忘了List中的根元素不会持有实际元素值，因此计算长度时不会包含它。这是两个类型在初始化值方面的第二个不同。
- Ring值的Len方法的算法复杂度是 O(N) 的，而List值的Len方法的算法复杂度则是 O(1)的。这是两者在性能方面最显而易见的差别。
六、自己使用中出现的问题
queue.go
import (
"container/list"
"fmt"
"sync"
)
//1 自定义排序
//2 并发安全
//3 限制数量 如果插入位置不在topLimit之内，插入失败
type Queue struct {
list *list.List
compareFunc func(a, b interface{}) bool
topLimit int //
m sync.Mutex
}
func NewQueue(compare func(a, b interface{}) bool, topLimit int) *Queue {
return &Queue{list: list.New(), compareFunc: compare, topLimit: topLimit}
}
//从后往前遍历，找到符合要求的元素element,放在element后面
func (q *Queue) PutOnBack(value interface{}) *list.Element {
q.m.Lock()
defer q.m.Unlock()
if q.list.Len() == 0 {
return q.list.PushBack(value)
} else {
//先判断第一个是否符合要求
if q.compareFunc(value, q.list.Front().Value) {
return q.list.PushFront(value)
} else {
//从后往前找
findCount := 0
var element *list.Element = nil
for e := q.list.Back(); e != nil; e = e.Prev() {
if q.compareFunc(e.Value, value) {
element = e
break
} else {
findCount++
}
}
//在list l中元素mark之后插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变
if element != nil {
if q.list.Len()-findCount < q.topLimit {
fmt.Println("PutOnBack:", value)
return q.list.InsertAfter(value, element)
}
}
} //not first element
} //not length == 0
return nil
}
func (q *Queue) RemoveAll() {
q.m.Lock()
defer q.m.Unlock()
for {
e := q.list.Front()
if e == nil {
break
}
q.list.Remove(e)
}
}
//将value值遍历出来，放入Slice
func (q *Queue) ValueSlice() []interface{} {
q.m.Lock()
defer q.m.Unlock()
var s = make([]interface{}, 0)
fmt.Println("print all:")
for item := q.list.Front(); nil != item; item = item.Next() {
fmt.Println("v:", item.Value)
s = append(s, item.Value)
}
return s
}
//删除最前面那个元素
//Remove(e *Element) interface{}//如果元素e属于list l，将其从list中删除，并返回元素e的值。
func (q *Queue) Shift() interface{} {
q.m.Lock()
defer q.m.Unlock()
fmt.Println("shift one:", q.list.Front().Value)
return q.list.Remove(q.list.Front())
}
简单使用一下：
main.go:
type Bag struct {
Uid int64
TotalMoney int64
TotalCount int32
Bomb int32
CreateTime int64
}
q := NewQueue(compareValue, 4)
q.PutOnBack(Bag{TotalMoney: 100, CreateTime: 0})
q.PutOnBack(Bag{TotalMoney: 120, CreateTime: 0})
q.PutOnBack(Bag{TotalMoney: 20, CreateTime: 2})
提前说明，queue.go和main.go不在一个包里。目前这样用，实现了并发的list，数据也排序写入了。问题来了，如果我想查找TotalMoney=120的数据怎么办呢，那个list取出来的值是interface{}类型的，必须进行类型断言才能比对。
第一种办法，在main.go里对queue取出来的数据进行Bag断言，但是这个过程中还要Lock,Unlock，遍历list，就得把queue里面的list和mutex变成公共属性，有破坏性。
第二种办法，在queue.go里用反射查询，写个方法，把要查询的属性和相应值传进来，遍历list中的值，将其key,value比对一下，但是要遍历几层才是要查的key,value也是个问题，不够灵活，效率也差。
第三种办法，在queue.go同一个包里另一个文件，比如xx.go里引用main.go里的Bag进行断言，这就不像第一种办法，需要把list和mutex变成公共属性了。相当于对queue.go新增了一些方法，但实际上还是挂在Queue的结构体上。
目前使用了第三种方法，感觉还是有点怪
