Go 链表的实现

庆云2年前技术文章789

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表允许插入和移除表上任意位置上的结点,但是不允许随机存取。链表有三种类型:

  • 单向链表

  • 双向链表

  • 循环链表


1、单项链表

单向链表中每个结点包含两部分,分别是数据域和指针域,上一个结点的指针指向下一结点,依次相连,形成链表。

这里介绍三个概念:首元结点、头结点和头指针。

  • 首元结点:就是链表中存储第一个元素的结点,如下图中 a1 的位置。

  • 头结点:它是在首元结点之前附设的一个结点,其指针域指向首元结点。头结点的数据域可以存储链表的长度或者其它的信息,也可以为空不存储任何信息。

  • 头指针:它是指向链表中第一个结点的指针。若链表中有头结点,则头指针指向头结点;若链表中没有头结点,则头指针指向首元结点。

7.png

头结点在链表中不是必须的,但增加头结点有以下几点好处:

  • 增加了头结点后,首元结点的地址保存在头结点的指针域中,对链表的第一个数据元素的操作与其他数据元素相同,无需进行特殊处理。

  • 增加头结点后,无论链表是否为空,头指针都是指向头结点的非空指针,若链表为空的话,那么头结点的指针域为空。

1.1 定义

利用 Struct 可以包容多种数据类型的特性,使用它作为链表的结点是最合适不过了。一个结构体内可以包含若干成员,这些成员可以是基本类型、自定义类型、数组类型,也可以是指针类型。可以使用指针类型成员来存放下一个结点的地址。


实例:

type Node struct {
	Data int
	Next *Node
}

其中成员 Data 用来存放结点中的有用数据,Next 是指针类型的成员,它指向 Node struct 类型数据,也就是下一个结点的数据类型。

实例:为链表赋值,并遍历链表中的每个结点。

package main

import "fmt"

type Node struct {
	data int
	next *Node
}

func Shownode(p *Node) { //遍历
	for p != nil {
		fmt.Println(*p)
		p = p.next //移动指针
	}
}
func main() {
	var head = new(Node)
	head.data = 1
	var node1 = new(Node)
	node1.data = 2
	head.next = node1
	var node2 = new(Node)
	node2.data = 3
	node1.next = node2
	Shownode(head)
}

运行结果:

➜   go run main.go
{1 0x14000010240}
{2 0x14000010250}
{3 <nil>}

1.2 插入结点

单链表的结点插入方法一般使用头插法或者尾插法。

1.2.1 头插法

每次插入在链表的头部插入结点:

  • 使用 tail 记录头结点(指针类型)

  • 每插入一个结点,使该结点的指针指向头结点的地址(tail)

  • 每插入一个结点,则更新 tail 使其指向新结点

实例:

package main

import "fmt"

type Node struct {
	data int
	next *Node
}

func Shownode(p *Node) { // 遍历
	for p != nil {
		fmt.Println(*p)
		p = p.next // 移动指针
	}
}

func main() {
	var head = new(Node)
	head.data = 0
	var tail *Node
	tail = head // tail用于记录头结点的地址,刚开始tail的的指针指向头结点
	for i := 1; i < 10; i++ {
		var node = Node{data: i}
		node.next = tail // 将新插入的node的next指向头结点
		tail = &node     // 重新赋值头结点
	}
	Shownode(tail) // 遍历结果
}

运行结果:

➜   go run main.go 
{9 0x1400008e290}
{8 0x1400008e280}
{7 0x1400008e270}
{6 0x1400008e260}
{5 0x1400008e250}
{4 0x1400008e240}
{3 0x1400008e230}
{2 0x1400008e220}
{1 0x1400008e210}
{0 <nil>}

1.2.2 尾插法

每次插入在链表的尾部插入结点(常用):

  • 使用 tail 记录尾结点(指针类型)

  • 每插入一个结点,使 tail 的指针指向该结点的地址

  • 每插入一个结点,则更新 tail 使其指向新结点

实例:

package main

import "fmt"

type Node struct {
	data int
	next *Node
}

func Shownode(p *Node) { // 遍历
	for p != nil {
		fmt.Println(*p)
		p = p.next // 移动指针
	}
}

func main() {
	var head = new(Node)
	head.data = 0
	var tail *Node
	tail = head // tail用于记录最末尾的结点的地址,刚开始tail的的指针指向头结点
	for i := 1; i < 10; i++ {
		var node = Node{data: i}
		(*tail).next = &node
		tail = &node
	}
	Shownode(head) // 遍历结果
}

运行结果:

➜   go run main.go 
{0 0x14000188050}
{1 0x14000188060}
{2 0x14000188070}
{3 0x14000188080}
{4 0x14000188090}
{5 0x140001880a0}
{6 0x140001880b0}
{7 0x140001880c0}
{8 0x140001880d0}
{9 <nil>}

1.3 总结

在进行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据搬移,所以速度较慢。而在链表中插入或者删除一个数据,我们并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的。所以,在链表中插入和删除一个数据是非常快速的。

但是,有利就有弊。链表要想随机访问第 k 个元素,就没有数组那么高效了。因为链表中的数据并非连续存储的,所以无法像数组那样,根据首地址和下标,通过寻址公式就能直接计算出对应的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点。


2、循环链表

循环链表是一种特殊的单链表。

循环链表跟单链表唯一的区别就在尾结点。单向链表的尾结点指针指向空地址,表示这就是最后的结点了,而循环链表的尾结点指针是指向链表的头结点,它像一个环一样首尾相连,所以叫作“循环”链表,如下图所示。

8.png

和单链表相比,循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表。比如著名的约瑟夫问题,尽管用单链表也可以实现,但是用循环链表实现的话,代码就会简洁很多。

3、双向链表

单向链表只有一个方向,结点只有一个后继指针 next 指向后面的结点。而双向链表,顾名思义它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。

9.png

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。


相关文章

Prometheus监控Minio集群

Prometheus监控Minio集群

一、概述Minio支持集成prometheus,用以监控CPU、硬盘、网络等数据。二、修改docker-compose.yaml官方的给docker-compose.yaml,默认是不能访问metri...

chronyc时间同步器配置

chronyc时间同步器配置

chronyc & chronydchrony 有两个核心组件:chronyd守护进程,主要用于调整内核中运行的系统时间和时间服务器同步chronyc命令行界面程序,让用户能够对 chrony...

Doris审计插件的安装

Doris审计插件的安装

插件下载地址:https://doris.apache.org/download1.安装Doris审计插件(1)解压 Audit Loader 插件步骤1. 复制插件文件cp  /opt/dtstac...

MongoDB的In-Memory存储引擎

   在企业版 3.2.6版本开始,MongoDB开始有In-Memory存储引擎,除了一些元数据和诊断数据外,In-Memory存储引擎不会存储任何数据到磁盘,包括配置数据、索引、用户凭证等。   ...

kafka部署

安装前准备修改环境变量vi /etc/profile export KAFKA_HOME=/opt/kafkaexport PATH=$PATH:$KAFKA_HOME/bin创建用户及用户组grou...

presto参数优化

presto参数优化

总体参数1)session级别的参数配置 query.max-run-time=600s 在终止查询之前,允许在群集上处理查询的最大时间。时间包括分析和计划的时间,也包括在队列中等待的时间,因此本...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。