雙鏈表的實現
基本概念
每一個節點都存儲上一個和下一個節點的指針
實現思路
創建一個節點結構體
- 每個節點都有上節點指針與下節點指針
- 每個節點都有一個key => value
創建一個鏈表結構體
- 鏈表容量大小屬性
- 鏈表大小屬性
- 鏈表鎖, 實現并發安全
- 鏈表頭節點
- 鏈表尾節點
實現鏈表操作方法
- 添加頭部節點操作AppendHead
- 添加尾部節點操作AppendTail
- 追加尾部節點操作Append
- 插入任意節點操作Insert
- 刪除任意節點操作Remove
- 刪除頭部節點操作RemoveHead
- 刪除尾部節點操作RemoveTail
- 獲取指定位置的節點Get
- 搜索任意節點Search
- 獲取鏈表大小GetSize
- 打印所有節點操作Print
- 反轉所有節點操作Reverse
總結
- 學好算法是一個不斷積累的過程
- 學習時還需做到知行合一
- 實現時需要多做用例測試.
代碼解析
定義節點的結構體
type DoubleNode struct {
Key int //鍵
Value interface{} //值
Prev *DoubleNode //上一個節點指針
Next *DoubleNode //下一個節點指針
Freq int //頻率次數.為了給LFU使用的
}
定義一個雙鏈表的結構體
//定義一個雙鏈表的結構
type DoubleList struct {
lock *sync.RWMutex //鎖
Capacity uint //最大容量
Size uint //當前容量
Head *DoubleNode //頭節點
Tail *DoubleNode //尾部節點
}
初使雙鏈表
//初使雙鏈表
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
}
添加頭部節點
實現思路
- 先判斷容量大小
- 判斷頭部是否為空,
- 如果為空則添加新節點
- 如果不為空則更改現有的節點,并添加上
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
}
添加尾部元素
實現思路
- 先判斷容量大小
- 判斷尾部是否為空,
- 如果為空則添加新節點
- 如果不為空則更改現有的節點,并添加上
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
//添加任意位置元素
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
}
刪除頭部節點
實現思路
- 判斷頭部是否為空
- 將頭部節點取出來
- 判斷頭部是否有下一個節點
- 沒有下一個節點,則說明只有一個節點, 刪除本身,無須移動指針位置
- 如果有下一個節點,則頭部下一個節點即是頭部節點.
//刪除頭部節點
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
}
刪除尾部節點
實現思路
- 判斷尾部節點是否為空
- 取出尾部節點
- 判斷尾部節點的上一個節點是否存在
- 不存在:則說明只有一個節點, 刪除本身,無須移動指針位置
- 如果存在上一個節點,則尾部的上一個節點即是尾部節點.
//刪除尾部節點
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
}
刪除任意元素
實現思路
- 判斷是否是頭部節點
- 判斷是否是尾部節點
- 否則為中間節點,需要移動上下節點的指針位置.并實現元素刪除
- 將上一個節點的下一節點指針指向下節點
- 將下一個節點的上一節點指針指向上節點
//刪除任意元素
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
}
查看完整源碼
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- 詳解go語言單鏈表及其常用方法的實現
- python/golang 刪除鏈表中的元素
- python/golang實現循環鏈表的示例代碼
- Go實現雙向鏈表的示例代碼
- Go語言單鏈表實現方法
- go實現反轉鏈表
