golang双链表的实现代码示例

双链表的实现

基本概念

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

实现思路

创建一个节点结构体

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

创建一个链表结构体

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

实现链表操作方法

• 添加头部节点操作appendhead
• 添加尾部节点操作appendtail
• 追加尾部节点操作append
• 插入任意节点操作insert
• 删除任意节点操作remove
• 删除头部节点操作removehead
• 删除尾部节点操作removetail
• 获取指定位置的节点get
• 搜索任意节点search
• 获取链表大小getsize
• 打印所有节点操作print
• 反转所有节点操作reverse

总结

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

代码解析

定义节点的结构体

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
}

添加头部节点

实现思路

1. 先判断容量大小
2. 判断头部是否为空,
   1. 如果为空则添加新节点
   2. 如果不为空则更改现有的节点,并添加上

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
}

删除头部节点

实现思路

1. 判断头部是否为空
2. 将头部节点取出来
3. 判断头部是否有下一个节点
   1. 没有下一个节点,则说明只有一个节点, 删除本身,无须移动指针位置
   2. 如果有下一个节点,则头部下一个节点即是头部节点.

//删除头部节点
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. 如果存在上一个节点,则尾部的上一个节点即是尾部节点.

//删除尾部节点
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. 将下一个节点的上一节点指针指向上节点

//删除任意元素
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
}

查看完整源码

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