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

双向链表

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实现双向链表

• 编辑
• 预览