本文共 7219 字，大约阅读时间需要 24 分钟。

因为转载必须指明原文网址，而本文内容整合了网上多篇技术文章，无法明确其中一条，所以选择了原创。

定义

单向链表（单链表）是链表的一种，是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是由结点构成，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. 查询节点
   根据指定的位置索引，查询出节点内容。

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

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 mainimport "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))    }}

参考

《》