雙鏈表的實現
基本概念
每一個節點都存儲上一個和下一個節點的指針
實現思路
創建一個節點結構體
- 每個節點都有上節點指針與下節點指針
- 每個節點都有一個key => value
創建一個鏈表結構體
- 鏈表容量大小屬性
- 鏈表大小屬性
- 鏈表鎖, 實現并發安全
- 鏈表頭節點
- 鏈表尾節點
實現鏈表操作方法
- 添加頭部節點操作AppendHead
- 添加尾部節點操作AppendTail
- 追加尾部節點操作Append
- 插入任意節點操作Insert
- 刪除任意節點操作Remove
- 刪除頭部節點操作RemoveHead
- 刪除尾部節點操作RemoveTail
- 獲取指定位置的節點Get
- 搜索任意節點Search
- 獲取鏈表大小GetSize
- 打印所有節點操作Print
- 反轉所有節點操作Reverse
總結
- 學好算法是一個不斷積累的過程
- 學習時還需做到知行合一
- 實現時需要多做用例測試.
代碼解析
定義節點的結構體
|
1
2
3
4
5
6
7
|
type DoubleNode struct { Key int //鍵 Value interface{} //值 Prev *DoubleNode //上一個節點指針 Next *DoubleNode //下一個節點指針 Freq int //頻率次數.為了給LFU使用的} |
定義一個雙鏈表的結構體
|
1
2
3
4
5
6
7
8
|
//定義一個雙鏈表的結構type DoubleList struct { lock *sync.RWMutex //鎖 Capacity uint //最大容量 Size uint //當前容量 Head *DoubleNode //頭節點 Tail *DoubleNode //尾部節點} |
初使雙鏈表
|
1
2
3
4
5
6
7
8
9
10
|
//初使雙鏈表func New(capacity uint) *DoubleList { list := new(DoubleList) list.Capacity = capacity list.lock = new(sync.RWMutex) list.Size = 0 list.Head = nil list.Tail = nil return list} |
添加頭部節點
實現思路
- 先判斷容量大小
-
判斷頭部是否為空,
- 如果為空則添加新節點
- 如果不為空則更改現有的節點,并添加上
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func (list *DoubleList) AddHead(node *DoubleNode) bool { //判斷容量是否為0 if list.Capacity == 0 { return false } list.lock.Lock() defer list.lock.Unlock() //判斷頭部節點是否為nil if list.Head == nil { list.Head = node list.Tail = node } else { //存在頭部節點 list.Head.Prev = node //將舊頭部節點上一個節點指向新節點 node.Next = list.Head //新頭部節點下一個節點指向舊頭部節點 list.Head = node //設置新的頭部節點 list.Head.Prev = nil //將新的頭部節點上一個節點設置NIL } list.Size++ return true} |
添加尾部元素
實現思路
- 先判斷容量大小
-
判斷尾部是否為空,
- 如果為空則添加新節點
- 如果不為空則更改現有的節點,并添加上
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func (list *DoubleList) AddTail(node *DoubleNode) bool { //判斷是否有容量, if list.Capacity == 0 { return false } list.lock.Lock() defer list.lock.Unlock() //判斷尾部是否為空 if list.Tail == nil { list.Tail = node list.Head = node } else { //舊的尾部下個節點指向新節點 list.Tail.Next = node //追加新節點時,先將node的上節點指向舊的尾部節點 node.Prev = list.Tail //設置新的尾部節點 list.Tail = node //新的尾部下個節點設置為空 list.Tail.Next = nil } //雙鏈表大小+1 list.Size++ return true} |
添加任意位置元素
實現思路
- 判斷容量大小
- 判斷鏈表大小
- 第一種: 如果插入的位置大于當前長度則尾部添加
- 第二種: 如果插入的位置等于0則,頭部添加
-
第三種: 中間插入節點
- 先取出要插入位置的節點,假調為C節點
- 介于A, C之間, 插入一個B節點
- A的下節點應該是B, 即C的上節點的下節點是B
- B的上節點是C的上節點
- B的下節點是C
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
//添加任意位置元素func (list *DoubleList) Insert(index uint, node *DoubleNode) bool { //容量滿了 if list.Size == list.Capacity { return false } //如果沒有節點 if list.Size == 0 { return list.Append(node) } //如果插入的位置大于當前長度則尾部添加 if index > list.Size { return list.AddTail(node) } //如果插入的位置等于0則,頭部添加 if index == 0 { return list.AddHead(node) } //取出要插入位置的節點 nextNode := list.Get(index) list.lock.Lock() defer list.lock.Unlock() //中間插入: //假設已有A, C節點, 現在要插入B節點 // nextNode即是C節點, //A的下節點應該是B, 即C的上節點的下節點是B nextNode.Prev.Next = node //B的上節點是C的上節點 node.Prev = nextNode.Prev //B的下節點是C node.Next = nextNode //C的上節點是B nextNode.Prev = node list.Size++ return true} |
刪除頭部節點
實現思路
- 判斷頭部是否為空
- 將頭部節點取出來
-
判斷頭部是否有下一個節點
- 沒有下一個節點,則說明只有一個節點, 刪除本身,無須移動指針位置
- 如果有下一個節點,則頭部下一個節點即是頭部節點.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//刪除頭部節點func (list *DoubleList) RemoveHead() *DoubleNode { //判斷頭部節點是否為空 if list.Head == nil { return nil } list.lock.Lock() defer list.lock.Unlock() //將頭部節點取出來 node := list.Head //判斷頭部是否有下一個節點 if node.Next != nil { list.Head = node.Next list.Head.Prev = nil } else { //如果沒有下一個節點, 說明只有一個節點 list.Head, list.Tail = nil, nil } list.Size-- return node} |
刪除尾部節點
實現思路
- 判斷尾部節點是否為空
- 取出尾部節點
-
判斷尾部節點的上一個節點是否存在
- 不存在:則說明只有一個節點, 刪除本身,無須移動指針位置
- 如果存在上一個節點,則尾部的上一個節點即是尾部節點.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//刪除尾部節點func (list *DoubleList) RemoveTail() *DoubleNode { //判斷尾部節點是否為空 if list.Tail == nil { return nil } list.lock.Lock() defer list.lock.Unlock() //取出尾部節點 node := list.Tail //判斷尾部節點的上一個是否存在 if node.Prev != nil { list.Tail = node.Prev list.Tail.Next = nil } list.Size-- return node} |
刪除任意元素
實現思路
- 判斷是否是頭部節點
- 判斷是否是尾部節點
-
否則為中間節點,需要移動上下節點的指針位置.并實現元素刪除
- 將上一個節點的下一節點指針指向下節點
- 將下一個節點的上一節點指針指向上節點
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
//刪除任意元素func (list *DoubleList) Remove(node *DoubleNode) *DoubleNode { //判斷是否是頭部節點 if node == list.Head { return list.RemoveHead() } //判斷是否是尾部節點 if node == list.Tail { return list.RemoveTail() } list.lock.Lock() defer list.lock.Unlock() //節點為中間節點 //則需要: //將上一個節點的下一節點指針指向下節點 //將下一個節點的上一節點指針指向上節點 node.Prev.Next = node.Next node.Next.Prev = node.Prev list.Size-- return node} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://segmentfault.com/a/1190000020042196
