转载请注明出处：数据结构——Golang实现单链表

Golang

1. 单链表

1.1. 定义

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，由于链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

1.2. 优点

1. 单个结点创立非常方便，普通的线性内存通常在创立的时候就需要设定数据的大小
2. 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
3. 结点的访问方便，可以通过循环或者者递归的方法访问到任意数据，但是平均的访问效率低于线性表。

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. 查询节点

根据指定的位置索引，查询出节点内容。

// 获取指定位置的节点，不存在则返回nilfunc (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实现单链表