Go 語言的雙向鏈表、list 操作和雙向循環鏈表- 這些誰認識？
雙向鏈表
1）雙向鏈表的結構
雙向鏈表結構中元素在內存中不是緊鄰空間，而是每個元素中存放上一個元素和後一個元素的地址
-
第一個元素稱爲（頭）元素，前連接（前置指針域）爲 nil
-
最後一個元素稱爲 尾（foot）元素，後連接（後置指針域）尾 nil
雙向鏈表的優點
-
在執行新增元素或刪除元素時效率高，獲取任意一個元素，可以方便的在這個元素前後插入元素
-
充分利用內存空間，實現內存靈活管理
-
可實現正序和逆序遍歷
-
頭元素和尾元素新增或刪除時效率較高
雙向鏈表的缺點
-
鏈表增加了元素的指針域，空間開銷比較大
-
遍歷時跳躍性查找內容，大量數據遍歷性能低
2）雙向鏈表容器 List
在 Go 語言標準庫的 container/list 包提供了雙向鏈表 List
List 結構體定義如下
-
root 表示根元素
-
len 表示鏈表中有多少元素
// 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
}其中 Element 結構體定義如下
-
next 表示下一個元素，使用 Next() 可以獲取到
-
prev 表示上一個元素，使用 Prev() 可以獲取到
-
list 表示元素屬於哪個鏈表
-
Value 表示元素的值，interface() 在 Go 語言中表示任意類型
// 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{}
}操作 List
- 直接使用 container/list 包下的 New() 新建一個空的 List
添加，遍歷，取首尾，取中間元素
package main
import (
"container/list"
"fmt"
)
func main() {
//實例化
mylist := list.New()
fmt.Println(mylist)
//添加
mylist.PushFront("a") //["a"]
mylist.PushBack("b") //["a","b"]
mylist.PushBack("c") //["a","b","c"]
//在最後一個元素的前面添加
mylist.InsertBefore("d",mylist.Back()) //["a","b","d","c"]
mylist.InsertAfter("e",mylist.Front()) //["a","e","b","d","c"]
//遍歷
for e := mylist.Front(); e != nil; e = e.Next(){
fmt.Print(e.Value, " ") //a e b d c
}
fmt.Println("")
//取首尾
fmt.Println(mylist.Front().Value) //a
fmt.Println(mylist.Back().Value) //c
//取中間的元素，通過不斷的Next()
n := 3
var curr *list.Element
if n > 0 && n <= mylist.Len(){
if n == 1 {
curr = mylist.Front()
}else if n == mylist.Len(){
curr = mylist.Back()
}else {
curr = mylist.Front()
for i := 1; i < n; i++{
curr = curr.Next()
}
}
}else {
fmt.Println("n的數值不對")
}
fmt.Println(curr.Value) //b
}2）移動元素
package main
import (
"container/list"
"fmt"
)
func main() {
//實例化
mylist := list.New()
fmt.Println(mylist)
//添加
mylist.PushFront("a") //["a"]
mylist.PushBack("b") //["a","b"]
mylist.PushBack("c") //["a","b","c"]
//在最後一個元素的前面添加
mylist.InsertBefore("d",mylist.Back()) //["a","b","d","c"]
mylist.InsertAfter("e",mylist.Front()) //["a","e","b","d","c"]
//移動，把第一個元素一道最後一個元素的前面
mylist.MoveBefore(mylist.Front(),mylist.Back())
//mylist.MoveAfter(mylist.Back(),mylist.Front())
//把最後一個元素移動到最前面
//mylist.MoveToFront(mylist.Back())
//把第一個元素移動到最後面
//mylist.MoveToBack(mylist.Front())
for e := mylist.Front(); e != nil; e = e.Next(){
fmt.Print(e.Value, " ") //e b d a c
}
}3）刪除
mylist.Remove(mylist.Front())雙向循環列表
1）循環鏈表特點是沒有節點的指針域爲 nil，通過任何一個元素都可以找到其它元素。環形鏈表結構如下
雙向循環鏈表和雙向鏈表區別
-
雙向循環鏈表沒有嚴格意義上的頭元素和尾元素
-
沒有元素的前連接和後連接爲 nil
-
一個長度爲 n 的雙向循環鏈表，通過某個元素向某個方向移動，在查找最多 n-1 次，一定會找到另一個元素
2）在 container/ring 包下結構體 Ring 源碼如下
-
官方明確說明了 Ring 是循環鏈表的元素，又是環形鏈表
-
實際使用時 Ring 遍歷就是環形鏈表第一個元素
// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
next, prev *Ring
Value interface{} // for use by client; untouched by this library
}3）創建和查看
package main
import (
"container/ring"
"fmt"
)
func main() {
//r代表整個循環鏈表，又代表第一個元素
r := ring.New(5)
r.Value = 0
r.Next().Value = 1
r.Next().Next().Value = 2
//r.Next().Next().Next().Value = 3
//r.Next().Next().Next().Next().Value = 4
r.Prev().Value = 4
r.Prev().Prev().Value = 3
//查看元素內容
//循環鏈表有幾個元素，func就執行幾次，i當前執行元素的內容
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 1 2 3 4
})
fmt.Println("")
//取中間元素，用移動
fmt.Println(r.Move(3).Value) //3
}4）增加
package main
import (
"container/ring"
"fmt"
)
func main() {
//r代表整個循環鏈表，又代表第一個元素
r := ring.New(5)
r.Value = 0
r.Next().Value = 1
r.Next().Next().Value = 2
//r.Next().Next().Next().Value = 3
//r.Next().Next().Next().Next().Value = 4
r.Prev().Value = 4
r.Prev().Prev().Value = 3
//增加
r1 := ring.New(2)
r1.Value = 5
r1.Next().Value = 6
r.Link(r1)
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 5 6 1 2 3 4
})
}5）刪除
package main
import (
"container/ring"
"fmt"
)
func main() {
//r代表整個循環鏈表，又代表第一個元素
r := ring.New(5)
r.Value = 0
r.Next().Value = 1
r.Next().Next().Value = 2
//r.Next().Next().Next().Value = 3
//r.Next().Next().Next().Next().Value = 4
r.Prev().Value = 4
r.Prev().Prev().Value = 3
//刪除
r.Unlink(1)
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 2 3 4
})
}刪除後面兩個
//刪除
r.Unlink(2)
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 3 4
})r.Next() 刪除
//刪除
r.Next().Unlink(2)
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 1 4
})qu超出範圍，取 5 的餘數
//刪除
r.Unlink(6)
r.Do(func(i interface{}) {
fmt.Print(i, " ") //0 2 3 4
})文章首發：https://www.cnblogs.com/derek1184405959/p/11298618.html
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/77cIKTJA_OxqY-7WSv2K_w