您好,欢迎来到网暖!

当前位置:网暖 » 站长资讯 » 建站基础 » 网络技术 » 文章详细 订阅RssFeed

自己动手用golang实现双向链表

来源:网络整理 浏览:152次 时间:2020-06-05

双向链表

image.png


主要有链表跟节点2个结构体

type Dnode struct {   data interface{}   prev *Dnode   next *Dnode}type  DList struct {   head *Dnode   tail *Dnode   size int}




特点:

1、除头部、尾部2个节点外,其他任意节点都通过prev / next 分别指向前置后置节点

image.png

2、头部节点前置节点为空,同理尾部节点后置节点为空



主要实现的API如下:

1、查询

查询链表长度

查询任意节点



2、添加

从开头插入节点

从尾部插入节点

从任意位置插入节点


3、删除

删除任意节点


4、其他

打印链表

初始化链表


具体实现如下:

package mainimport "fmt"type Dnode struct {   data interface{}   prev *Dnode   next *Dnode}type  DList struct {   head *Dnode   tail *Dnode   size int}// 获取链表长度func (dl *DList)getSize()int{   return dl.size}// 获取链表头部func (dl *DList)getHead() *Dnode{   return dl.head}// 获取链表尾部func (dl *DList)getTail() *Dnode{   return dl.tail}// 初始化链表func initDList()(dl *DList){   return &DList{      head:nil,      tail:nil,      size:0,   }}// 打印链表func (dl *DList) display(){   fmt.Println("DoubleLinkedList size is ",dl.size)   if dl.getSize() == 0{      return   }   ptr := dl.head   for ptr != nil{      fmt.Println("data is ",ptr.data)      ptr = ptr.next   }}// 在头部追加节点func (dl *DList) addHeadNode(node *Dnode){   if dl.getSize() == 0{      dl.head = node      dl.tail = node      node.prev = nil      node.next = nil   }else{      dl.head.prev = node      node.prev = nil      node.next = dl.head      dl.head = node   }   dl.size += 1}// 在尾部追加节点func (dl *DList) append(node *Dnode){   if dl.getSize() == 0 {      dl.head = node      dl.tail = node      node.prev = nil      node.next = nil   }else{      dl.tail.next = node      node.prev = dl.tail      node.next = nil      dl.tail = node   }   dl.size += 1}// 增加任意节点func (dl *DList) insert(node *Dnode,index int){   if dl.getSize() == 0 {      dl.addHeadNode(node)   }   // 获取当前索引为index 值的节点   oldNode := dl.getNode(index)   node.next = oldNode   node.prev = oldNode.prev   oldNode.prev.next = node   oldNode.prev = node      dl.size ++}// 查询节点func (dl *DList) getNode(index int)(dnode *Dnode){   if dl.getSize() == 0 || index > dl.getSize() {      return nil   }   if index == 0{      return dl.head   }   node := dl.head   for i:=0;i<=index;i++{      dnode = node.next   }   return}// 任意节点删除func (dl *DList) remove(node *Dnode) {   // 默认删除尾部节点   if node == nil || node == dl.tail{      node = dl.tail      dl.tail = node.prev      dl.tail.next = nil   }else if node == dl.head{      dl.head = node.next      dl.head.prev = nil   }else{      node.prev.next = node.next      node.next.prev = node.prev   }   dl.size --}func main() {   dl := initDList()   fmt.Println("从开头添加节点")   for i:=0;i<5;i++{      dnode := Dnode{         data:i,      }      dl.addHeadNode(&dnode)   }   dl.display()   fmt.Println("从末尾添加节点")   for i:=5;i<10;i++{      dnode := Dnode{         data:i,      }      dl.append(&dnode)   }   dl.display()   fmt.Println("删除最后一个节点")   dl.remove(nil)   dl.display()   fmt.Println("删除第3个节点")   node := dl.getNode(3)   dl.remove(node)   dl.display()   fmt.Println("添加第2个节点")   node = &Dnode{      data:3,   }   dl.insert(node,1)   dl.display()}


推荐站点

  • 腾讯腾讯

    腾讯网(www.QQ.com)是中国浏览量最大的中文门户网站,是腾讯公司推出的集新闻信息、互动社区、娱乐产品和基础服务为一体的大型综合门户网站。腾讯网服务于全球华人用户,致力成为最具传播力和互动性,权威、主流、时尚的互联网媒体平台。通过强大的实时新闻和全面深入的信息资讯服务,为中国数以亿计的互联网用户提供富有创意的网上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐网是全球最大的中文门户网站,为用户提供24小时不间断的最新资讯,及搜索、邮件等网络服务。内容包括全球热点事件、突发新闻、时事评论、热播影视剧、体育赛事、行业动态、生活服务信息,以及论坛、博客、微博、我的搜狐等互动空间。

    www.sohu.com
  • 网易网易

    网易是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

    www.163.com
  • 新浪新浪

    新浪网为全球用户24小时提供全面及时的中文资讯,内容覆盖国内外突发新闻事件、体坛赛事、娱乐时尚、产业资讯、实用信息等,设有新闻、体育、娱乐、财经、科技、房产、汽车等30多个内容频道,同时开设博客、视频、论坛等自由互动交流空间。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com