Golang之单链表实现 - Golang教程网

一.单链表基本概念

单链表是一种顺序存储的结构。
有一个头结点，没有值域，只有连域，专门存放第一个结点的地址。
有一个尾结点，有值域，也有链域，链域值始终为NULL。
所以，在单链表中为找第i个结点或数据元素，必须先找到第i - 1 结点或数据元素，而且必须知道头结点，否者整个链表无法访问。

关于链表的概念，此处不细讲了，具体的内容，大家可以自行查找相关数据结构资料.

本文主要通过Golang实现链表的几种常见操作:

判断是否为空的单链表
单链表的长度
从头部添加元素
从尾部添加元素
在指定位置添加元素
删除指定元素
删除指定位置的元素
查看是否包含某个元素
遍历所有元素

二.实现代码以及代码注释

1. 定义结构体

package linkedList

import "fmt"

type Object interface{}

type Node struct {
   Data Object //定义数据域
   Next *Node  //定义地址域(指向下一个表的地址)
}

type List struct {
   headNode *Node //头节点
}

2.判断链表是否为空

3. 获取列表长度

func (this *List) Length() int {
   //获取链表头结点
   cur := this.headNode
   //定义一个计数器，初始值为0
   count := 0

   for cur != nil {
      //如果头节点不为空，则count++
      count ++
      //对地址进行逐个位移
      cur = cur.Next
   }
   return count
}

4.从链表头部添加元素

func (this *List) Add(data Object) *Node {
   node := &Node{Data: data}
   node.Next = this.headNode
   this.headNode = node
   return node
}

5. 从链表尾部添加元素

6. 在链表指定位置添加元素

7. 删除链表指定值的元素

8.删除指定位置的元素

9.查看链表是否包含某个元素

10. 遍历链表所有节点

三.测试代码与效果

创建并向链表中添加元素

测试代码：

测试结果：

2. 判断链表是否为空

测试代码：

list2 := linkedList.List{}
fmt.Printf("list 是否为空链表:%t\n", list.IsEmpty())
fmt.Printf("list2 是否为空链表:%t\n", list2.IsEmpty())

测试结果:

3. 在指定位置index=5,value=b处插入元素five_insert_value

list.Insert(5,"five_insert_value")
fmt.Print("链表List当前的数值为:")
list.ShowList()

4. 是否包含元素five_insert_value

测试代码：

isContain := list.Contain("five_insert_value")
fmt.Printf("isContain[five_insert_value]:%t",isContain)

测试结果：

isContain[five_insert_value]:true

5. 删除元素five_insert_value

测试代码：

list.Remove("five_insert_value")
fmt.Print("链表List当前的数值为:")
list.ShowList()
fmt.Println()

测试结果

链表List当前的数值为:   beforeHead 1  2  3  4  a  b  c  d

6.从位置3删除元素index=3,value=3

//注意此时的headNode是值为beforeHead的元素

list.RemoveAtIndex(3)
fmt.Print("链表List当前的数值为:")
list.ShowList()
fmt.Println()

测试结果

链表List当前的数值为:   beforeHead 1  2  4  a  b  c  d