双向链表

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

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

特点：

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

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