我是靠谱客的博主 瘦瘦台灯,这篇文章主要介绍golang双链表的实现代码示例,现在分享给大家,希望可以做个参考。

双链表的实现

基本概念

每一个节点都存储上一个和下一个节点的指针

实现思路

创建一个节点结构体

  • 每个节点都有上节点指针与下节点指针
  • 每个节点都有一个key => value

创建一个链表结构体

  • 链表容量大小属性
  • 链表大小属性
  • 链表锁, 实现并发安全
  • 链表头节点
  • 链表尾节点

实现链表操作方法

  • 添加头部节点操作AppendHead
  • 添加尾部节点操作AppendTail
  • 追加尾部节点操作Append
  • 插入任意节点操作Insert
  • 删除任意节点操作Remove
  • 删除头部节点操作RemoveHead
  • 删除尾部节点操作RemoveTail
  • 获取指定位置的节点Get
  • 搜索任意节点Search
  • 获取链表大小GetSize
  • 打印所有节点操作Print
  • 反转所有节点操作Reverse

总结

  1. 学好算法是一个不断积累的过程
  2. 学习时还需做到知行合一
  3. 实现时需要多做用例测试.

代码解析

定义节点的结构体

复制代码
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. 判断头部是否为空,
    1. 如果为空则添加新节点
    2. 如果不为空则更改现有的节点,并添加上
复制代码
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. 判断头部是否有下一个节点
    1. 没有下一个节点,则说明只有一个节点, 删除本身,无须移动指针位置
    2. 如果有下一个节点,则头部下一个节点即是头部节点.
复制代码
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. 判断尾部节点的上一个节点是否存在
    1. 不存在:则说明只有一个节点, 删除本身,无须移动指针位置
    2. 如果存在上一个节点,则尾部的上一个节点即是尾部节点.
复制代码
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. 否则为中间节点,需要移动上下节点的指针位置.并实现元素删除
    1. 将上一个节点的下一节点指针指向下节点
    2. 将下一个节点的上一节点指针指向上节点
复制代码
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 }

查看完整源码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持靠谱客。

最后

以上就是瘦瘦台灯最近收集整理的关于golang双链表的实现代码示例的全部内容,更多相关golang双链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(160)

评论列表共有 0 条评论

立即
投稿
返回
顶部