开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-单链表的基本介绍】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/627/detail/9835
数据结构和算法-单链表的基本介绍
内容简介:
一、链表的介绍
二、单链表的介绍
三、小结
一、链表的介绍
(1)前言
上一节讲了用数组来模拟一个环形的队列,它的核心思想就是指针、或者是标识在元素的下标,它在到达队尾的时候,它可以通过取模的方式,又重新回到这个数组的前面,这是它核心思想。下面来看另外一种数据结构,这个数据结构是非常有用的,为什么说这个数据结构更有用?或者更有意思?
因为这个链表,它可以实现前面的队列,在前面讲 redit 的时候,曾经有一个数据结构叫 list ,那个 list 的底层可以用数组实现,也可用链表实现,它这个就很灵活了。此数据结构可以做很多好玩的东西出来。
(2)链表的基本介绍及示意图
首先看链表是什么,链表是有序的一个列表。它在内存中的存储是如下图所示的:
这里有头指针,它指向了后面的各个结点,结点之间是可以这样互相指,对于我们来说,感觉它并不是完全连续的,这个很正常,因为它下面地址的分布其实还是由系统来决定的,这个并不影响,因为它认为都是有序的就行,这是它一个基本的说明。
二、单链表的介绍
(1)单链表(带头结点)逻辑示意图
单链表(带头结点)逻辑示意图如下所示:
最左边是一个 head 的结点,它先指向一个头结点,头结点里面有一个字段,这个字段又指向另外一个节点,另外一个节点里面又有一个字段,它又向指向另外节点。
(2)经典案例示意图介绍
画了一个示意图是最经典的案例,如下:
这里有一个头结点 head 的节点,它指向了一个头结点,比如说这是第一个结点,那这个结点里面是什么内容?比如是一个人,即 Person ,假设它有个字段的名字叫 tom ,另外它有一个叫 next ,它是一个什么类型?
姑且认为它是一个 next[ *Person] 的类型,假定左上角节点它的结构体是 type people struct ,它里面首先有它自己的信息,比如 name string ,另外一个最重要的信息就是 next 的指针,即 next[ *Person] ,假设还有一结点叫 jack ,假设还有一个结点叫 Scott ,再来一个头结点,头结点没有具体的数据,只专门用来做头结点,那其里面的内容可以不给任何东西,然后形成一个结构,可以看到它的头结点指向的地方,然后下边的地方继续指向它的下一个结点,以此类推,于是这样它就形成了一个链表的结构,那么链表它形成的意义有什么用?
可以想象在现实生活中就会存在这样类似的结构,比如小朋友们围成一圈丢手帕,就可以形成一个环状的,怎么样一个环状呢?
既可以让它再重新回来,不要再重新指向这个头结点,这样就是一个环状,那如果不想做环状的列表,它本身其实看起来也像是一个队列,也就可以当一个队列来使用它,更有意思的是,它可以在内存里面形成一些非常有用的结构,
比如下图:
比如上图是有一组人,那么可以让很多人形成一个哈希,到时候在帮抓某一组人的时候,通过一个里面有另外一个的结构,可以很轻松的通过这个结点来找到主人,所以说这个是非常有用的,上图是它的一个示意图。
(3)改进的链表示意图
那么我这个图,画的有一点点不准确,这个图如果在 Java 或者 C++ 里面,它是一个很精准的图,但是放在 Go 语言里面,有点不准确,哪一点不准确?
就是因为都非常清楚的知道,在 Go 语言里面这个结构体它本身是一个指针类型,所以 next 这个指针准确的讲,它并没有直接指向下一个结构体,它其实直接指向的是一个地址,以前讲过,它是指针的话是先指向一个地址再指向真正的结构体,也就是说标准的画法应该是如下图所示:
有时候这样画的很麻烦,看起来不舒服,所以说在讲课的时候,可能把中间这个地址就不画了,这个就是一个链表的一个最基本的结构。
(4)链表的增删改查
来完成对链表的增删改查,通过此练习,就能知道链表它是怎么用的,可以这样理解,可以利用链表来做一个属于自己的内存数据库,就是有些时候我们往往把数据直接放在数据库里面,但是那是人家的东西,有些时候想自己去存放一个数据量比较大的数据,数量比较大而且还要让它具有很好的扩展性,比如还在内存里面存放数据,有增删改查的功能,这个时候链表加上哈希,即链表配合哈希的算法,就是非常不错的一种机构,
所以这就是为什么后边再讲的有一个闪列,闪列加上散列它本身就是一个哈希,然后配合链表,就相当于自己可以做一个小的内存的数据管理的一个机制,那是不是意味着将来自己想去搞一点数据,自己在里面把它维护起来,有增删改查功能就可以了,就是这个意思,必须学会链表,看起来它虽然不是很难,但是它很有用。
三、小结
链表是一个有序的列表,它在内存中的存储可能不是连续的,但是在形式上体现出来肯定必须是一个有序的,在上文中画了一个图;
单链表一般来讲会带一个表头,因为一般来说为了比较容易控制链表一般来讲,为了比较容易控制列表,一般都有表头,比较好的链表有增删改查的操作,都会给它设置一个头结点,头结点主要是用来表示它是链表的头,它本身并不存放数据,头结点的价值或者作用主要是用来标识链表的头,这个是不能动的,一旦头结点没有了,那就完全找不到了,节点本身不存放数据。