自己动手用golang实现双向链表
双向链表
创新互联是一家专业的成都网站建设公司,我们专注网站制作、做网站、网络营销、企业网站建设,买友情链接,一元广告为企业客户提供一站式建站解决方案,能带给客户新的互联网理念。从网站结构的规划UI设计到用户体验提高,创新互联力求做到尽善尽美。
主要有链表跟节点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() }
文章题目:自己动手用golang实现双向链表
URL链接:http://pcwzsj.com/article/jjiecs.html