Golang学习日志 ━━ 单向链表

因为转载必须指明原文网址，而本文内容整合了网上多篇技术文章，无法明确其中一条，所以选择了原创。
已在最后的参考目录里列出本文所有涉及的文章。

定义

单向链表（单链表）是链表的一种，是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

• 链表是使用指针进行构造的列表；
• 又称为结点列表，因为链表是由一个个结点组装起来的；
• 其中每个结点都有指针成员变量指向列表中的下一个结点；

链表中的数据是以结点来表示的，每个结点的构成：

元素(数据元素的映象) + 指针(指示后继元素存储位置)，

• 元素就是存储数据的存储单元，
• 指针就是连接每个结点的地址数据。

优点

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

实现

简单说来，目的就是实现至少一个头指针记录开始的内存地址，此后每个元素都包含一个值和下一个元素的内存地址

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. 链表初始化
   定义完结构，接下来就需要对单链表进行初始化了。代码如下：

// 初始化
func (list *SingleList) Init()  {
    list.Size = 0
    list.Head = nil
    list.Tail = nil
    list.mutex = new(sync.RWMutex)
}

3. 新增节点
   链表节点的新增分为两种，
   a. append：在链表后面追加节点；
   b. 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
}

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
}

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

// 获取指定位置的节点，不存在则返回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
}

6. 打印链表
   最后，我们增加一个打印链表的功能，方便我们看整个链表的内容：

// 输出链表
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
    }
}

完整实例

package main

import "fmt"

type Object interface{}

type Node struct {
    Data Object
    next *Node
}

type List struct {
    size uint64
    head *Node
    tail *Node
}

func (list *List) Init() {
    (*list).size = 0
    (*list).head = nil
    (*list).tail = nil
}

// 向链表追加节点
func (list *List) Append(node *Node) bool {
    if node == nil {
        return false
    }

    (*node).next = nil // 新加节点在末尾，没有next
    if (*list).size == 0 {
        (*list).head = node
    } else {
        oldTail := (*list).tail // 取尾结点
        (*oldTail).next = node  // 尾结点的next指向新加节点
    }

    (*list).tail = node // 新节点是尾结点
    (*list).size++
    return true
}

// 向第i个节点处插入节点
func (list *List) Insert(i uint64, node *Node) bool {
    if node == nil || i > (*list).size || (*list).size == 0 {
        return false
    }

    if i == 0 {
        (*node).next = (*list).head
        (*list).head = node
    } else {
        preNode := (*list).head
        for j := uint64(1); j < i; j++ {
            preNode = (*preNode).next
        }

        (*node).next = (*preNode).next // 新节点指向旧节点原来所指的next
        (*preNode).next = node         // 原节点的next指向新节点
    }
    (*list).size++

    return true
}

// 移除指定位置的节点
func (list *List) Remove(i uint64) bool {
    if i >= (*list).size {
        return false
    }

    if i == 0 {
        preHead := (*list).head     // 取出旧的链表头
        (*list).head = preHead.next // 旧链表头的next变为新的头

        // 如果仅有一个节点，则头尾节点清空
        if (*list).size == 1 {
            (*list).head = nil
            (*list).tail = nil
        }
    } else {
        preNode := (*list).head
        for j := uint64(1); j < i; j++ {
            preNode = (*preNode).next
        }

        node := (*preNode).next     // 找到当前要删除的节点
        (*preNode).next = node.next // 把当前要删除节点的next赋给其父节点的next,完成后代转移

        // 若删除的尾部，尾部指针需要调整
        if i == ((*list).size - 1) {
            (*list).tail = preNode
        }
    }

    (*list).size--

    return true
}

// 移除所有节点
func (list *List) RemoveAll() bool {
    (*list).Init()
    return true
}

// 获取指定位置的节点
func (list *List) Get(i uint64) *Node {
    if i >= (*list).size {
        return nil
    }

    node := (*list).head
    for j := uint64(0); j < i; j++ {
        node = (*node).next
    }

    return node
}

// 搜索某个数据的节点位置
func (list *List) IndexOf(data Object) int64 {
    pos := int64(-1)
    node := (*list).head
    if node.Data == data {
        return 0
    }

    for j := uint64(1); j < (*list).size; j++ {
        if node != nil {
            node = (*node).next
            if node != nil && node.Data == data {
                pos = int64(j)
                break
            }
        }
    }
    return pos
}

// 取得链表长度
func (list *List) GetSize() uint64 {
    return (*list).size
}

// 取得链表头
func (list *List) GetHead() *Node {
    return (*list).head
}

// 取得链表尾
func (list *List) GetTail() *Node {
    return (*list).tail
}

func main() {
    var l List
    l.Init()

    node1 := &Node{Data: 11111}
    l.Append(node1)

    node2 := &Node{Data: 22222}
    l.Append(node2)

    node3 := &Node{Data: 33333}
    l.Append(node3)

    node4 := &Node{Data: "insert"}
    l.Insert(1, node4)

    node5 := &Node{Data: "head"}
    l.Insert(0, node5)

    node6 := &Node{Data: "tail"}
    l.Append(node6)

    l.Remove(0)
    l.Remove(1)
    l.Remove(3)

    pos1 := l.IndexOf(22222)
    pos2 := l.IndexOf(44444)
    fmt.Println(pos1, pos2)

    fmt.Println(l.GetHead(), l.GetTail(), l.GetSize())
    fmt.Println()

    //l.RemoveAll()

    for i := uint64(0); i < l.size; i++ {
        fmt.Println(l.Get(i))
    }
}

参考

《Golang学习手册之：带你21周搞定Go语言 - P128 128今日分享面试题》
《数据结构——Golang实现单链表 》
《golang 实现单链表》
《用golang实现的单向链表》
《golang 实现单链表 》
《Golang之单链表实现 》