详解go语言单链表及其常用方法的实现

2024-08-20 12:08:58

目的

在刷算法题中经常遇到关于链表的操作，在使用go语言去操作链表时不熟悉其实现原理，目的是为了重温链表这一基础且关键的数据结构。

1、链表的特点和初始化

1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)

1.2、结点

结点(node)

数据域 => 存储元素信息
指针域 => 存储结点的直接后继，也称作指针或链

首元结点是指链表中存储的第一个数据元素的结点
头结点是在首元结点之前附设的一个结点，其指针域指向首元结点(非必须)
头指针是指向链表中第一个结点的指针

1.3、单链表
特点

每个结点中只包含一个指针域
单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发，顺链进行寻找，也称为顺序存取的存取结构

1.4、单链表的常用操作

本文主要实现了单链表的以下操作

判断是否为空
获取链表长度
在头部插入元素
在尾部插入元素
删除指定位置元素
删除指定值的元素
查找是否包含指定值
查找指定位置元素的值
遍历链表所有结点

1.5、单链表的初始化

//定义单链表结构体
type Node struct {
  data interface{} //数据域
  next *Node    //指针域
}
type List struct {
  length  int //储存链表的长度
  headNode *Node
}

/*单链表的初始化
1、生成新结点作为头结点，用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
  //即构造一个空的单链表L(包含头指针)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

2、单链表的插入

先讲单链表的插入有利于后续相关操作的实现

2.1、在指定位置插入元素

/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index <= 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := &Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

2.2、在头部插入元素

func (list *List) AddElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

2.3、在尾部插入元素

func (list *List) AppendElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

3、单链表的删除

3.1、删除指定值的元素

/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中，以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
  if index <= 0 || index > list.length {
    fmt.Println("删除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

3.2、删除指定位置的元素

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
    fmt.Println("ok")
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        fmt.Println("ok")
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

4、单链表的查询

4.1、查找是否包含指定值

/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找，只要指向当前结点的指针p不为空，
并且p所指结点的数据域不等于给定值e，则执行以下操作：p指向下一个结点
3、返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if IsNull() {
    fmt.Println("err")
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

4.2、查找指定位置的值

/*单链表的取值
1、用指针P指向首元结点，用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问，
只要指向当前结点的指针P不为空，并且没有达到序号为i的结点，则循环执行以下操作：
  2.1、P指向下一个结点
  2.2、计数器j相应加1
3、退出循环时，如果指针P为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，
取值失败返回ERROR；否则取值成功，
此时j==i时，P所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index <= 0 || index > list.length {
    fmt.Println("err")
    return
  } else {
    pre := list.headNode
    for j := 0; j < index; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data
  }
}

4.3、遍历单链表

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
  }
}

5、完整代码及结果展示

package main

import "fmt"

//定义单链表结构体

type Node struct {
  data interface{} //数据域
  next *Node    //指针域
}
type List struct {
  length  int //储存链表的长度
  headNode *Node
}

/*
type Method interface {
  IsNull() bool          //1、判断是否为空
  GetLength() int         //2、获取链表长度
  InsertElem(i int, v interface{}) //3、在指定位置添加元素
  AddElem(v interface{})      //4、在头部插入元素
  AppendElem(v interface{})    //5、在尾部插入元素
  DeleteElem(i int)        //6、删除指定位置元素
  RemoveElem(v interface{})    //7、删除指定值的元素
  ContaineElem(v interface{}) bool //8、是否包含指定值的元素
  LocateElem(i int) interface{}  //9、查找指定位置元素的值
  ShowList()            //10、遍历链表所有结点
}
*/
/*单链表的初始化
1、生成新结点作为头结点，用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
  //即构造一个空的单链表L(包含头指针)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

/*单链表的取值
1、用指针P指向首元结点，用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问，只要指向当前结点的指针P不为空，
并且没有达到序号为i的结点，则循环执行以下操作：
  2.1、P指向下一个结点
  2.2、计数器j相应加1
3、退出循环时，如果指针P为空，或者计数器j大于i，说明指定的序号i值
不合法(i大于表长n或i小于等于0)，取值失败返回ERROR；否则取值成功，
此时j==i时，P所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index <= 0 || index > list.length {
    return 0
  } else {
    pre := list.headNode
    for j := 0; j < index-1; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data.(int)
  }
}

/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找，只要指向当前结点的
指针p不为空，并且p所指结点的数据域不等于给定值e，则执行以下操作：
  2.1、p指向下一个结点
3、返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if list.IsNull() {
    fmt.Println("err")
    return false
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index <= 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := &Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中，以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
  if index <= 0 || index > list.length {
    fmt.Println("删除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count < index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

func (list *List) IsNull() bool {
  if list.length == 0 {
    return true
  } else {
    return false
  }
}

func (list *List) AddElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() { //处理空表的插入，否则会导致一个空的头结点后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

func (list *List) AppendElem(v interface{}) {
  node := &Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
    fmt.Printf("\n")
  }
}

func main() {
  L := InitList()
  msg := []int{12, 5, 3, 8, 55, 13}
  for i := range msg {
    L.AddElem(msg[i])
  }
  fmt.Println("---- 添加元素 ----")
  L.AppendElem(66)
  L.ShowList()
  fmt.Println("---- 按位删除元素 ----")
  L.DeleteElem(3)
  L.ShowList()
  fmt.Println("---- 按值删除元素 ----")
  L.RemoveElem(13)
  L.ShowList()
  fmt.Println("---- 插入元素 ----")
  L.InsertElem(1, 88)
  L.ShowList()
  fmt.Println("---- 按值寻找元素 ----")
  fmt.Println(L.LocateElem(88))
  fmt.Println("---- 按位寻找元素 ----")
  fmt.Println(L.GetElem(4))
}

结果
---- 添加元素 ----
        13      55      8       3       5       12      66
---- 按位删除元素 ----
        13      55      3       5       12      66
---- 按值删除元素 ----
        55      3       5       12      66
---- 插入元素 ----
        88      55      3       5       12      66
---- 按值寻找元素 ----
true
---- 按位寻找元素 ----
5

6、总结

本文中除了初始化时为链表添加了一个空的头结点，其他情况下均无头结点，正如书中所说，为单链表添加头结点会方便很多，对链表进行相关操作时，不需要对首元结点做额外的处理，也便于对空表和非空表做统一处理
关于删除时释放结点空间及指针回收，我们交由go强大的垃圾回收来完成

参考博客
Golang之单链表实现
 go语言实现单链表

到此这篇关于详解go语言单链表及其常用方法的实现的文章就介绍到这了,更多相关go语言单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Go语言单链表实现方法

本文实例讲述了Go语言单链表实现方法.分享给大家供大家参考.具体如下: 1. singlechain.go代码如下: 复制代码代码如下: ////////// //单链表 -- 线性表 package singlechain //定义节点 type Node struct { Data int Next *Node } /* * 返回第一个节点 * h 头结点 */ func GetFirst(h *Node) *Node { if h.Next == nil {
详解go语言单链表及其常用方法的实现

目的在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构. 1.链表的特点和初始化 1.1.链表的特点用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 1.2.结点结点(node) 数据域 => 存储元素信息指针域 => 存储结点的直接后继,也称作指针或链首元结点是指链表中存储的第一个数据元素的结点头结点是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须) 头指
详解Go语言中单链表的使用

目录链表单链表结构创建节点遍历链表头插法尾插法遍历方法链表长度链表转数组数组转链表链表一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域.使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理.但是链表失去
C++详解如何实现单链表

目录单链表单链表的基本操作 1.初始化 2.取值 3.查找 4.插入 5.删除示例代码开发环境运行结果单链表链表内存空间不一定连续,其扩展性较好.多余的不多说了.该文主要记录单链表的实现,该单链表含有一个非空的头节点.链表的操作实际上是对其指针域与数据域的操作. 线性表的链式存储又称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素.为了建立数据元素之间的线性关系,对每个链表结点,除存放元素自身的信息外,还需要存放一个指向其后继的指针. 单链表中结点类型的描述如下: t
C语言单链表实现方法详解

本文实例讲述了C语言单链表实现方法.分享给大家供大家参考,具体如下: slist.h #ifndef __SLIST_H__ #define __SLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { //定义单链表中的结点信息 ElemType data; //结点的数据域 struct Node *next
详解C语言中二级指针与链表的应用

目录前言二级指针讲解链表的应用定义双链表的结构体创建双链表前言这篇文章即将解决你看不懂或者不会写链表的基本操作的问题,对于初学者而言,有很多地方肯定是费解的.比如函数的参数列表的多样化,动态分配内存空间函数malloc等,其实这些知识和指针联系紧密,尤其是二级指针.那么开始好好的学习这篇文章吧! 二级指针讲解简述:其实就是一个指针指向另一个指针的地址. 我们都知道指针指向地址,但是指针自身也是一个变量,当然也可以被二级指针所指向. 语法:形如 int x = 10; int *q
详解C语言快速排序三种方法的单趟实现

目录交换排序的思想冒泡排序的思想快速排序的整体框架快速排序单趟实现逻辑 1. hoare版本单趟实现(左右指针法) 2.挖坑法单趟排序实现 3.前后指针法交换排序的思想基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动. 冒泡排序的思想冒泡排序比较简单,我们之前使用也很多,简单讲解,就是比较两个数,如果比他大就交换,没有他大就接着向后比,一直到数组结束,这是单趟
详解C语言内核中的链表与结构体

Windows内核中是无法使用vector容器等数据结构的,当我们需要保存一个结构体数组时,就需要使用内核中提供的专用链表结构LIST_ENTRY通过一些列链表操作函数对结构体进行装入弹出等操作,如下代码是本人总结的内核中使用链表存储多个结构体的通用案例. 首先实现一个枚举用户进程功能,将枚举到的进程存储到链表结构体内. #include <ntifs.h> #include <windef.h> extern PVOID PsGetProcessPeb(_In_ PEPROCES
详解C语言进程同步机制

本文是对进程同步机制的一个大总结(9000+字吐血总结),涵盖面非常的全,包括了进程同步的一些概念.软件同步机制.硬件同步机制.信号量机制和管程机制,对每种机制结合代码做了详细的介绍,并且对琐碎的知识点和概念解释的非常清晰. 在前面的博客中讲述了进程的状态及其状态的转换,每种状态的含义和转换的原因.同样我们也知道,在OS引入了进程后,可以使系统中的多道程序可以并发的执行,进程的并发执行一方面极大的提高了系统的资源利用率和吞吐量,但是另一方面却使系统变得更加复杂,如果不能采取有效的措施,对多个
c语言单链表尾添加的深入讲解

前言犹豫了几天,看了很多大牛写的关于c语言链表,感触很多,终于下定决心,把自己对于链表的理解随之附上,可用与否,自行裁夺.由于作者水平有限也是第一次写,不足之处,竭诚希望得到各位大神的批评指正.制作不易,不喜勿喷,谢谢!!! 在正文开始之前,我先对数组和链表进行简单的对比分析. 链表也是一种很常见的数据结构,不同于数组的是它是动态进行存储分配的一种结构.数组存放数据时,必须要事先知道元素的个数.举个例子,比如一个班有40个人,另一个班有100个人,如果要用同一个数组先后来存放这两个班的学生数据
详解C语言如何实现双向带头循环链表

目录一.双向循环链表与顺序表的区别二.List.h 三.List.c 1.带头双向循环链表的初始化 2.带头双向循环链表的销毁 3.带头双向循环链表的打印 4.动态开辟一个节点 5.带头双向循环链表的判空 6.带头双向循环链表的尾插.尾删 7.带头双向循环链表的头插.头删 8.带头双向循环链表的长度 9.带头双向循环链表的查找.任意位置插入.删除一.双向循环链表与顺序表的区别不同点顺序表双向带头循环链表在内存中的存储方式连续存储不一定连续随机访问支持随机访问不支持随访问

详解go语言单链表及其常用方法的实现

相关推荐

随机推荐