@toc
知识回顾
在前一章中我们已经介绍了==顺序表==，对顺序表的实现已经有所了解！
但是，这种数据结构，难免会有以下的==缺陷==
我们在中间位置插入或删除数据的话，可能需要挪动后面的所有数据，时间复杂度较高==(o(n))==
我们的空间是按照2倍的常数开辟的，可能会造成空间的浪费，比如我们的顺序表从100扩容到200，
但我们只需要插入5个数据，剩下的195单位空间就被浪费了
增容过程也会造成资源的消耗
为了克服以上的缺陷，我们设计出了另外一种线性数据结构——<code>链表</code>
之所以叫它线性表，是因为它的逻辑结构是连续的，仍然满足线性表的特征
但它在物理结构上未必是关联的，连续的
在物理结构上非连续的话，我们可以利用地址，形成元素之间的相互联系
它的定义仍然是一个结构体,每个结构体，就是链表中的一个结点
<code>链表是一种物理存储单元上非连续、非顺序的存储结构</code>，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，<code>结点</code>可以在运行时<code>动态生成</code>。每个结点包括两个部分：<code>一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域</code>。
实际中，链表的结构多种多样：
1.带头、不带头链表
2、单向，双向。
3、循环，非循环。
通过以上的这些情况组合起来，就有<code>八种链表结构。即带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。</code>
本篇讲解的是无头单向非循环链表。
<code>链表</code>是由一个个结点链接而成，创建一个链表之前，我们首先要创建一个结点类型，该类型由两部分组成：<code>数据域和指针域。</code>
内存布局：
打印链表时，我们需要从头指针指向的位置开始，依次向后打印，直到指针指向null时，结束打印。
仔细想想，每当我们需要增加一个结点之前，我们必定要先申请一个新结点，然后再插入到相应位置，于是我们可以将该功能封装成一个函数。
头插时，我们只需要先让新结点的指针域指向头指针指向的位置（即原来的第一个结点），然后让头指针指向新结点即可。
注：这两步操作的顺序不能颠倒，若先让头指针指向新结点，那么就无法找到原来第一个结点的位置了。
尾插的时候我们需要先判断链表是否为空，若为空，则直接让头指针指向新结点即可；若不为空，我们首先需要利用循环找到链表的最后一个结点，然后让最后一个结点的指针域指向新结点。
注：新结点创建的时候指针域就已经置空，所以尾插时不需要再将新结点的指针域置空。
在给定位置后插入结点也只需要两步：先让新结点的指针域指向该位置的下一个结点，然后再让该位置的结点指向新结点即可。
注：这两步操作也不能颠倒顺序，理由与头插时相同。
要想在给定位置的前面插入一个新结点，我们首先还是要找到该位置之前的一个结点，然后让新结点的指针域指向地址为pos的结点，让前一个结点指向新结点即可。需要注意的是，当给定位置为头指针指向的位置时，相当于头插。
头删较为简单，若为空表，则不必做处理；若不为空表，则直接让头指针指向第二个结点，然后释放第一个结点的内存空间即可。
尾删相对麻烦一些，我们需要考虑三种不同的情况：
1、当链表为空时，不做处理。
2、当链表中只有一个结点时，直接释放该结点，然后将头指针置空。
3、当链表中有多个结点时，我们需要先找到最后一个结点的前一个结点，然后将最后一个结点释放，将前一个结点的指针域置空，使其成为新的尾结点。
4、==注意：删除尾部的数据还要把尾部的前一个结点的指针域置为null空指针，否则我们下次删除就找不到尾了。==
要删除给定位置之后的值，我们首先判断传入地址是否为最后一个结点的地址，若是，则不做处理，因为最后一个结点后面没有结点可删除。若不是最后一个结点，我们首先让地址为pos的结点指向待删除结点的后一个结点，然后将待删除结点释放即可。
要删除给定位置的结点，我们首先要判断该结点是否为第一个结点，若是，则操作与头删相同；若不是，我们就需要先找到待删除结点的前一个结点，然后让其指向待删除结点的后一个结点，最后才能释放待删除的结点。
**这个有2种情况：
1、删除的是不是第一个结点
2、删除的是第一个结点
因为删除当前位置数据有可能是第一个结点，所以我们统一传二级指针来实现。**
查找数据相对于前面的来说就非常简单了，我们只需要遍历一遍链表，在遍历的过程中，若找到了目标结点，则返回结点的地址；若遍历结束也没有找到目标结点，则直接返回空指针。
修改数据，嗯…其实我觉得根本不用写出来，但是链表的一般功能就是增、删、查、改嘛，为了完整性，还是加上吧。