雙鏈表的實現(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
- 反轉所有節(jié)點操作Reverse
總結
- 學好算法是一個不斷積累的過程
- 學習時還需做到知行合一
- 實現(xiàn)時需要多做用例測試.
代碼解析
定義節(jié)點的結構體
type DoubleNode struct {
Key int //鍵
Value interface{} //值
Prev *DoubleNode //上一個節(jié)點指針
Next *DoubleNode //下一個節(jié)點指針
Freq int //頻率次數(shù).為了給LFU使用的
}
定義一個雙鏈表的結構體
//定義一個雙鏈表的結構
type DoubleList struct {
lock *sync.RWMutex //鎖
Capacity uint //最大容量
Size uint //當前容量
Head *DoubleNode //頭節(jié)點
Tail *DoubleNode //尾部節(jié)點
}
初使雙鏈表
//初使雙鏈表
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é)點,并添加上
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é)點,并添加上
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é)點,假調為C節(jié)點
- 介于A, C之間, 插入一個B節(jié)點
- A的下節(jié)點應該是B, 即C的上節(jié)點的下節(jié)點是B
- B的上節(jié)點是C的上節(jié)點
- B的下節(jié)點是C
//添加任意位置元素
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é)點.
//刪除頭部節(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é)點.
//刪除尾部節(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é)點
//刪除任意元素
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
}
查看完整源碼
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- 詳解go語言單鏈表及其常用方法的實現(xiàn)
- python/golang 刪除鏈表中的元素
- python/golang實現(xiàn)循環(huán)鏈表的示例代碼
- Go實現(xiàn)雙向鏈表的示例代碼
- Go語言單鏈表實現(xiàn)方法
- go實現(xiàn)反轉鏈表
