自己動手用golang實現(xiàn)雙向鏈表
雙向鏈表
創(chuàng)新互聯(lián)是一家專業(yè)的成都網(wǎng)站建設(shè)公司，我們專注網(wǎng)站制作、做網(wǎng)站、網(wǎng)絡(luò)營銷、企業(yè)網(wǎng)站建設(shè)，買友情鏈接，一元廣告為企業(yè)客戶提供一站式建站解決方案，能帶給客戶新的互聯(lián)網(wǎng)理念。從網(wǎng)站結(jié)構(gòu)的規(guī)劃UI設(shè)計到用戶體驗提高，創(chuàng)新互聯(lián)力求做到盡善盡美。
主要有鏈表跟節(jié)點2個結(jié)構(gòu)體
type?Dnode?struct?{
???data?interface{}
???prev?*Dnode
???next?*Dnode
}
type??DList?struct?{
???head?*Dnode
???tail?*Dnode
???size?int
}特點：
1、除頭部、尾部2個節(jié)點外，其他任意節(jié)點都通過prev / next 分別指向前置后置節(jié)點
2、頭部節(jié)點前置節(jié)點為空，同理尾部節(jié)點后置節(jié)點為空
主要實現(xiàn)的API如下：
1、查詢
查詢鏈表長度
查詢?nèi)我夤?jié)點
2、添加
從開頭插入節(jié)點
從尾部插入節(jié)點
從任意位置插入節(jié)點
3、刪除
刪除任意節(jié)點
4、其他
打印鏈表
初始化鏈表
具體實現(xiàn)如下：
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
???}
}
//?在頭部追加節(jié)點
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
}
//?在尾部追加節(jié)點
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
}
//?增加任意節(jié)點
func?(dl?*DList)?insert(node?*Dnode,index?int){
???if?dl.getSize()?==?0?{
??????dl.addHeadNode(node)
???}
???//?獲取當前索引為index?值的節(jié)點
???oldNode?:=?dl.getNode(index)
???node.next?=?oldNode
???node.prev?=?oldNode.prev
???oldNode.prev.next?=?node
???oldNode.prev?=?node
???
???dl.size?++
}
//?查詢節(jié)點
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
}
//?任意節(jié)點刪除
func?(dl?*DList)?remove(node?*Dnode)?{
???//?默認刪除尾部節(jié)點
???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("從開頭添加節(jié)點")
???for?i:=0;i<5;i++{
??????dnode?:=?Dnode{
?????????data:i,
??????}
??????dl.addHeadNode(&dnode)
???}
???dl.display()
???fmt.Println("從末尾添加節(jié)點")
???for?i:=5;i<10;i++{
??????dnode?:=?Dnode{
?????????data:i,
??????}
??????dl.append(&dnode)
???}
???dl.display()
???fmt.Println("刪除最后一個節(jié)點")
???dl.remove(nil)
???dl.display()
???fmt.Println("刪除第3個節(jié)點")
???node?:=?dl.getNode(3)
???dl.remove(node)
???dl.display()
???fmt.Println("添加第2個節(jié)點")
???node?=?&Dnode{
??????data:3,
???}
???dl.insert(node,1)
???dl.display()
}
分享名稱：自己動手用golang實現(xiàn)雙向鏈表
標題路徑：http://m.jiaotiyi.com/article/jjiecs.html