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