开发者学堂课程【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)链表的增删改查
来完成对链表的增删改查，通过此练习，就能知道链表它是怎么用的，可以这样理解，可以利用链表来做一个属于自己的内存数据库，就是有些时候我们往往把数据直接放在数据库里面，但是那是人家的东西，有些时候想自己去存放一个数据量比较大的数据，数量比较大而且还要让它具有很好的扩展性，比如还在内存里面存放数据，有增删改查的功能，这个时候链表加上哈希，即链表配合哈希的算法，就是非常不错的一种机构，
所以这就是为什么后边再讲的有一个闪列，闪列加上散列它本身就是一个哈希，然后配合链表，就相当于自己可以做一个小的内存的数据管理的一个机制，那是不是意味着将来自己想去搞一点数据，自己在里面把它维护起来，有增删改查功能就可以了，就是这个意思，必须学会链表，看起来它虽然不是很难，但是它很有用。
三、小结
链表是一个有序的列表，它在内存中的存储可能不是连续的，但是在形式上体现出来肯定必须是一个有序的，在上文中画了一个图；
单链表一般来讲会带一个表头，因为一般来说为了比较容易控制链表一般来讲，为了比较容易控制列表，一般都有表头，比较好的链表有增删改查的操作，都会给它设置一个头结点，头结点主要是用来表示它是链表的头，它本身并不存放数据，头结点的价值或者作用主要是用来标识链表的头，这个是不能动的，一旦头结点没有了，那就完全找不到了，节点本身不存放数据。
