您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
双向链表
主要有链表跟节点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() }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。