内容简介:转载请注明出处:列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。
转载请注明出处: 数据结构——Golang实现单链表
Golang
1. 单链表
1.1. 定义
单向链表
(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。
1.2. 优点
- 单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小
- 结点的删除非常方便,不需要像线性结构那样移动剩下的数据
- 结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表。
2. Golang 实现
2.1. 相关结构体
首先需要先定义一下链表相关的结果, SingleObject
用于每个节点的数据,为interface{}结构, SingleNode
为链表中的节点, SingleList
单链表,为了多协程读写安全,所以在链表中加了读写锁。
具体定义如下:
// 节点数据 type SingleObject interface{} // 单链表节点 type SingleNode struct { Data SingleObject Next *SingleNode } // 单链表 type SingleList struct{ mutex *sync.RWMutex Head *SingleNode Tail *SingleNode Size uint }
2.2. 链表初始化
定义完结构,接下来就需要对单链表进行初始化了。代码如下:
// 初始化 func (list *SingleList) Init() { list.Size = 0 list.Head = nil list.Tail = nil list.mutex = new(sync.RWMutex) }
2.3. 新增节点
链表节点的新增分为两种,一种是在链表后面追加节点,该方式,我们称为append;另外一种方式是在指定位置插入节点,我们叫做insert。
另外新增时,若为第一个节点需特殊处理一下。下面请看代码:
// 添加节点到链表尾部 func (list *SingleList)Append(node *SingleNode) bool { if node == nil{ return false } list.mutex.Lock() defer list.mutex.Unlock() if list.Size == 0{ list.Head = node list.Tail = node list.Size = 1 return true } tail := list.Tail tail.Next = node list.Tail = node list.Size += 1 return true } // 插入节点到指定位置 func (list *SingleList)Insert(index uint, node *SingleNode) bool { if node == nil { return false } if index > list.Size{ return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0{ node.Next = list.Head list.Head = node list.Size += 1 return true } var i uint ptr := list.Head for i = 1; i < index; i ++ { ptr = ptr.Next } next := ptr.Next ptr.Next = node node.Next = next list.Size += 1 return true }
2.4. 删除节点
有了新增功能自然就少不了删除,此外,删除节点时,如果指定的位置是链表的头部或尾部,都需要特殊处理下。看代码:
// 删除指定位置的节点 func (list *SingleList)Delete(index uint) bool { if list == nil || list.Size == 0 || index > list.Size - 1 { return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0 { head := list.Head.Next list.Head = head if list.Size == 1{ list.Tail = nil } list.Size -= 1 return true } ptr := list.Head var i uint for i = 1; i < index; i++{ ptr = ptr.Next } next := ptr.Next ptr.Next = next.Next if index == list.Size - 1 { list.Tail = ptr } list.Size -= 1 return true }
2.6. 查询节点
根据指定的位置索引,查询出节点内容。
// 获取指定位置的节点,不存在则返回nil func (list *SingleList)Get(index uint) *SingleNode{ if list == nil || list.Size == 0 || index > list.Size - 1 { return nil } list.mutex.RLock() defer list.mutex.RUnlock() if index == 0{ return list.Head } node := list.Head var i uint for i = 0; i < index; i ++ { node = node.Next } return node }
2.7. 打印链表
最后,我们增加一个打印链表的功能,方便我们看整个链表的内容:
// 输出链表 func (list *SingleList)Display(){ if list == nil { fmt.Println("this single list is nil") return } list.mutex.RLock() defer list.mutex.RUnlock() fmt.Printf("this single list size is %d \n", list.Size) ptr := list.Head var i uint for i = 0; i < list.Size; i++{ fmt.Printf("No%3d data is %v\n", i + 1, ptr.Data) ptr = ptr.Next } }
完
转载请注明出处: 数据结构——Golang实现单链表
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 数据结构和算法面试题系列-C指针、数组和结构体
- 请问二叉树等数据结构的物理存储结构是怎样的?
- 数据结构——单链表
- 常用数据结构
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。