自己動手用golang實現雙向鏈表

雙向鏈表

主要有鏈表跟節點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?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()
}