重温一遍数据结构之单链表(golang版)
发布时间:2020-12-16 09:43:00 所属栏目:大数据 来源:网络整理
导读:说明 上一篇说的是线性表中的顺序存储结构,他的读取复杂度虽然是o(1),但是它的缺点也很明显,插入和删除需要移动很多元素,而且需要分配一块连续的内存区域 线性表之单链表 单链表在一定程度上解决了一部分上面的问题,而且也不要一大块连续的内存区域,代
说明上一篇说的是线性表中的顺序存储结构,他的读取复杂度虽然是o(1),但是它的缺点也很明显,插入和删除需要移动很多元素,而且需要分配一块连续的内存区域 线性表之单链表单链表在一定程度上解决了一部分上面的问题,而且也不要一大块连续的内存区域,代码如下 package main //线性表中的链式存储结构 //第一个节点为头节点,并不真实保存数据,头节点基本代表了整个链表 import ( "fmt" ) type Elem int type LinkNode struct { Data Elem Next *LinkNode } //生成头节点 func New() *LinkNode { //下面的data可以用来表示链表的长度 return &LinkNode{0,nil} } //在链表的第i个位置前插入一个元素e,复杂度为o(n) func (head *LinkNode) Insert(i int,e Elem) bool { p := head j := 1 for nil != p && j < i { p = p.Next j++ } if nil == p || j > i { fmt.Println("pls check i:",i) return false } s := &LinkNode{Data: e} s.Next = p.Next p.Next = s return true } //遍历链表 func (head *LinkNode) Traverse() { point := head.Next for nil != point { fmt.Println(point.Data) point = point.Next } fmt.Println("--------done----------") } //删除链表中第i个节点,复杂度为o(n) func (head *LinkNode) Delete(i int) bool { p := head j := 1 for (nil != p && j < i) { p = p.Next j++ } if nil == p || j > i { fmt.Println("pls check i:",i) return false } p.Next = p.Next.Next return true } // 获取链表中的第i个元素,复杂度为o(n) func (head *LinkNode) Get(i int) Elem { p := head.Next for j:= 1; j< i ;j++ { if nil == p { //表示返回错误 return -100001 } p=p.Next } return p.Data } func main() { linkedList := New() linkedList.Insert(1,9) linkedList.Insert(1,99) linkedList.Insert(1,999) linkedList.Insert(1,9999) linkedList.Insert(1,99999) linkedList.Insert(1,999999) linkedList.Traverse() linkedList.Delete(4) linkedList.Traverse() e := linkedList.Get(4) fmt.Println(e) } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |