转载请注明出处：数据结构——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
}
}
3. 源码
完
转载请注明出处: 数据结构——Golang实现单链表
