站长网_站长创业_站长主页_站长之家_易采站长站

会员投稿 投稿指南 站长资讯通告: golang双链表的实现代码示例
搜索:
您的位置: 主页 > 教程 > 脚本教程 > 其他脚本 > » 正文

golang双链表的实现代码示例

来源: 易采站长站

双链表的实现

基本概念

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

实现思路

创建一个节点结构体

每个节点都有上节点指针与下节点指针 每个节点都有一个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
}

            
最新图文资讯
1 2 3 4 5 6
相关文章列表:
易采站长站 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 人才招聘 - 帮助 -