Go 標準庫閱讀：Container-ring
【導讀】Go 標準庫 Container 中實現了一些數據結構，可以方便直接地利用這些庫實現邏輯。本文介紹了 ring 的實現。
相較於 List , ring 因爲不需要哨兵快速找到頭尾，所以只有一個 struct ring （環）
type Ring struct {
// 前後節點
next, prev *Ring
Value interface{}
}創建一個環，使用 New 函數，創建一個有 n 個容量的環
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
}同時提供 Len() 函數，獲取當前 ring 的容量
func (r *Ring) Len() int {
n := 0
if r != nil {
n = 1
// 即時的去遍歷一次 ring 獲取當前長度
for p := r.Next(); p != r; p = p.next {
n++
}
}
return n
}爲在 ring 中移動當前操作的指針，提供了 move 方法，支持正向移動和反方向移動 （向左或向右移動）
func (r *Ring) Move(n int) *Ring {
if r.next == nil {
/*
避免 a:=&ring.Ring{}
然後直接拿來用而沒有初始化從而報錯的情況
*/
return r.init()
}
switch {
case n < 0:
// 負數加到 0
for ; n < 0; n++ {
r = r.prev
}
case n > 0:
// 正數減到 0
for ; n > 0; n-- {
r = r.next
}
}
return r
}也可以給加入環節點或者刪除環節點 （類似於）
func (r *Ring) Link(s *Ring) *Ring {
/**
┌-----------------------┐
∨ ∨
a <---> r <---> b <---> c
^
add s
___
OR
__
┌-----------------------┐
∨ ∨
a <---> r <---> b <---> c
^
┌-----------------------┐
∨ ∨
d <---> f <---> s <---> g
^
s will add after r
*/
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---> b <---> c
┌-----------------------┐
∨ ∨
d <---> f <---> s <---> g
*/
n := r.Next()
if s != nil {
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---> b <---> c
┌-----------------------┐
∨ p| ∨
d <---> f <---> s <---> g
*/
p := s.Prev()
// Note: Cannot use multiple assignment because
// evaluation order of LHS is not specified.
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---- b <---> c
└----┐
|
p| └--↓
d <---> f <---> s <---> g
^ ^
└-----------------------┘
*/
r.next = s
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---- b <---> c
↑----┐
|
p| └--↓
d <---> f ----> s <---> g
^ ^
└-----------------------┘
*/
s.prev = r
/*
┌-----------------------┐
∨ n| ∨
a <---> r b <---> c
↑----┐ |
┌----┼--┘
p| └--↓
d <---> f ----> s <---> g
^ ^
└-----------------------┘
*/
n.prev = p
/*
┌-----------------------┐
∨ n| ∨
a <---> r b <---> c
↑----┐ ↑
┌----┼--┘
p↓ └--↓
d <---> f s <---> g
^ ^
└-----------------------┘
*/
p.next = n
/*
┌-------------------------------------------------------┐
∨ p| n| ∨
a <---> r <---> s <---> g <---> d <---> f <---> b <---> c
*/
}
return n
}所以最終是將 r 節點和 s 節點進行鏈接，將 r 的後驅節點和 s 的前驅節點進行鏈接，組成一個新的雙向鏈表實現的環
而 Unlink() 方法則是 調用的 link 方法並做了一些變化
func (r *Ring) Unlink(n int) *Ring {
if n <= 0 {
return nil
}
return r.Link(
// 獲取 r 的 n 個節點之後的那個 b 節點
r.Move(n + 1)
// 然後將 當前的 r 節點和 b 節點連接起來
// 則中間的這些節點相當於從環中被排除掉
)
}最後，Ring 還提供一個 Do() 方法，允許使用閉包函數遍歷 整個 Ring
func (r *Ring) Do(f func(interface{})) {
if r != nil {
f(r.Value)
for p := r.Next(); p != r; p = p.next {
f(p.Value)
}
}
}【導讀】阿斯頓發
ring
type Ring struct {
// 前後節點
next, prev *Ring
Value interface{}
}
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
}
func (r *Ring) Len() int {
n := 0
if r != nil {
n = 1
// 即時的去遍歷一次 ring 獲取當前長度
for p := r.Next(); p != r; p = p.next {
n++
}
}
return n
}
func (r *Ring) Move(n int) *Ring {
if r.next == nil {
/*
避免 a:=&ring.Ring{}
然後直接拿來用而沒有初始化從而報錯的情況
*/
return r.init()
}
switch {
case n < 0:
// 負數加到 0
for ; n < 0; n++ {
r = r.prev
}
case n > 0:
// 正數減到 0
for ; n > 0; n-- {
r = r.next
}
}
return r
}
func (r *Ring) Link(s *Ring) *Ring {
/**
┌-----------------------┐
∨ ∨
a <---> r <---> b <---> c
^
add s
___
OR
__
┌-----------------------┐
∨ ∨
a <---> r <---> b <---> c
^
┌-----------------------┐
∨ ∨
d <---> f <---> s <---> g
^
s will add after r
*/
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---> b <---> c
┌-----------------------┐
∨ ∨
d <---> f <---> s <---> g
*/
n := r.Next()
if s != nil {
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---> b <---> c
┌-----------------------┐
∨ p| ∨
d <---> f <---> s <---> g
*/
p := s.Prev()
// Note: Cannot use multiple assignment because
// evaluation order of LHS is not specified.
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---- b <---> c
└----┐
|
p| └--↓
d <---> f <---> s <---> g
^ ^
└-----------------------┘
*/
r.next = s
/*
┌-----------------------┐
∨ n| ∨
a <---> r <---- b <---> c
↑----┐
|
p| └--↓
d <---> f ----> s <---> g
^ ^
└-----------------------┘
*/
s.prev = r
/*
┌-----------------------┐
∨ n| ∨
a <---> r b <---> c
↑----┐ |
┌----┼--┘
p| └--↓
d <---> f ----> s <---> g
^ ^
└-----------------------┘
*/
n.prev = p
/*
┌-----------------------┐
∨ n| ∨
a <---> r b <---> c
↑----┐ ↑
┌----┼--┘
p↓ └--↓
d <---> f s <---> g
^ ^
└-----------------------┘
*/
p.next = n
/*
┌-------------------------------------------------------┐
∨ p| n| ∨
a <---> r <---> s <---> g <---> d <---> f <---> b <---> c
*/
}
return n
}
r
s
r
s
Unlink()
link
func (r *Ring) Unlink(n int) *Ring {
if n <= 0 {
return nil
}
return r.Link(
// 獲取 r 的 n 個節點之後的那個 b 節點
r.Move(n + 1)
// 然後將 當前的 r 節點和 b 節點連接起來
// 則中間的這些節點相當於從環中被排除掉
)
}
func (r *Ring) Do(f func(interface{})) {
if r != nil {
f(r.Value)
for p := r.Next(); p != r; p = p.next {
f(p.Value)
}
}
}轉自：juejin.cn/post/6844903865821691918
Go 開發大全
參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/69gmtfu6YalZT566lHXifA