golang中container/ring包

ring包实现了环形双向链表的功能。

type Ring
        func New(n int) *Ring
        func (r *Ring) Do(f func(interface{}))
        func (r *Ring) Len() int
        func (r *Ring) Link(s *Ring) *Ring
        func (r *Ring) Move(n int) *Ring
        func (r *Ring) Next() *Ring
        func (r *Ring) Prev() *Ring
        func (r *Ring) Unlink(n int) *Ring

结构体：

type Ring

// 环形双向链表
type Ring struct {
        next, prev *Ring
        Value interface{}
}

1）next *Ring：指向链表中的下一个节点的指针
2）prev *Ring：指向链表中的上一个节点的指针
3）Value interface{}：该节点中存储的内容，可以是任何对象

方法：

（1）func (r *Ring) New(int) *Ring

参数列表：

n：环形双向链表的节点的个数

返回值：

*Ring：空链表的指针

功能说明：

创建一个有n个节点的环形双向链表，链表上的每个元素的初始值是nil

（2）func (r *Ring) Do(f func(interface{}))

参数列表：

f：一个回调函数，该函数的参数为环形双向链表中的节点的Value字段值

功能说明：

正向遍历环形双向链表，并对每个链表中的元素执行回调函数f，如果这个函数f会修改链表r，那这个回调函数的行为将不可确定

为环形双向链表实例并初始化以及将环形双向链表数据打印出来

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r := ring.New(10)
    for i := 1;i <= 10;i++ {
        r.Value = i
        r = r.Next()
    }
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
}

（3）func (r *Ring) Len() int

返回值：

int：环形链表中元素的个数

功能说明：获取环形链表中元素的个数

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r := ring.New(10)
    fmt.Println(r.Len())
}

（4）func (r *Ring) Move(n int) *Ring

参数列表：

n：指针r在双向链表上移动的位置的个数。当n>0时，为正向移动；反之为反向移动。

返回值：

*Ring：移动结束后，指针r指向的节点

功能说明：

指向节点r的指针，正向或者逆向移动n%r.Len()个节点，并返回指针移动后指向的节点，但是r.Move(n)不对改变r的值，r不能为空

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    // 创建一个循环双向链表，并初始化
    r := ring.New(10)
    for i := 1;i <= 10;i++{
        r.Value = i
        r = r.Next()
    }

    // 输出内容
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r = r.Move(3)
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()
}
输出结果：
1 2 3 4 5 6 7 8 9 10 
4 5 6 7 8 9 10 1 2 3

（5）func (r *Ring) Next() *Ring

返回值：

*Ring：指向下一个节点的指针

功能说明：

获得指向下一个节点的指针

（6）func (r *Ring) Prev() *Ring

返回值：

*Ring：指向上一个节点的指针

功能说明：

获得指向上一个节点的指针

（7）func (r *Ring) Link(s *Ring) *Ring

参数列表：

s：环形双向链表

返回值：

*Ring：s和r相连前s.Next()的值

功能说明：

把一个环形双向链表s与环形双向链表r相链接，并返回相连前时s.Next()的值。r不能为空。

环形双向链表r与s的关系存在以下几种情况：

1）如果s和r不是同一个环形链表，则相连后，值产生一个环形链表，并返回相连前时s.Next()的值，

2）如果s和r是同一个环形链表，但s!=r时，相连后，产生两个环形链表，并返回相连前的s.Next()

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    // 创建一个循环双向链表，并初始化
    r1 := ring.New(10)
    r2 := ring.New(10)
    for i := 1;i <= 10;i++{
        r1.Value = i
        r1 = r1.Next()
        r2.Value = i + 20
        r2 = r2.Next()
    }
    /* 情况一 */
    fmt.Println("情况一：")
    r := r1.Link(r2)
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r1.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r2.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()
    /* 情况2 */
    fmt.Println("情况二：")
    r3 := ring.New(10)
    for i := 1;i <= 10;i++ {
        r3.Value = i
        r3 = r3.Next()
    }
    r4 := r3.Move(2)
    r = r3.Link(r4)
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r3.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r4.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()
    /* 情况3 */
    fmt.Println("情况三：")
    r5 := ring.New(10)
    for i := 1;i <= 10;i++ {
        r5.Value = i
        r5 = r5.Next()
    }
    r6 := r5
    r = r5.Link(r6)
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })

    r5.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r6.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()
}
输出内容:
情况一：
2 3 4 5 6 7 8 9 10 1 21 22 23 24 25 26 27 28 29 30 
1 21 22 23 24 25 26 27 28 29 30 2 3 4 5 6 7 8 9 10 
21 22 23 24 25 26 27 28 29 30 2 3 4 5 6 7 8 9 10 1 
情况二：
2 
1 3 4 5 6 7 8 9 10 
3 4 5 6 7 8 9 10 1 
情况三：
2 3 4 5 6 7 8 9 10 1 
1

（8）func (r *Ring) Unlink(n int) *Ring

参数列表：

n：要被移除的节点的个数

功能说明：从节点r的下一个节点（包含该节点r.Next()）开始移除 n % r.Len() 个节点。如果 n % r.Len() == 0，则链表不会有改变。r 不能为空。

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r1 := ring.New(10)
    for i := 1;i <= 10;i++ {
        r1.Value = i
        r1 = r1.Next()
    }
    r2 := r1.Unlink(22)
    r1.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()

    r2.Do(func(i interface{}) {
        fmt.Print(i, " ")
    })
    fmt.Println()
}
输出结果：
1 4 5 6 7 8 9 10 
2 3

参考来自： https://github.com/astaxie/gopkg/blob/master/container