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

筑梦攻城狮 · · 307 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

双向链表

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 main

import "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()
}



有疑问加站长微信联系(非本文作者)

本文来自:51CTO博客

感谢作者:筑梦攻城狮

查看原文:自己动手用golang实现双向链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

307 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传