寄语：

生活或许总有不如意，但请相信，所有的艰难都是暂时的。只要心中有光，脚下就有力量，勇敢向前走，未来自有答案。

引语

由于在顺序中，我们进行插入和删除中需要移动大量的元素，这尤为麻烦，所以我们重新定义了一种新的数据结构类型：链表，来解决这样的问题。在链表中各个元素随意的存放在内存单元中，我们只需知道每个数据下一个元素的地址即可，从而解决顺序表进行插入删除操作的痛点。

链表的特点

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

为了表示每个数据元素ai与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素ai 来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素 a 的存储映像，称为节点（node）。
结点包括两个域：其中存储数据元素信息的称为数据域；存储直接后继存储位置有域称为指针域。指针域中存储的信息称作指针或链。
n个结点[a（1 ≤i≤ n）的存储映像]链接成一个链表，即为线性表（ar，a2，…，an）。

单链表结构

结点的创建由数据域和指针域组成，假设p是指向第i个元素的指针，ai数据域可以用p->data,ai的指针域可以用p->next表示，p->next依然是一个指针，它指向的元素是第ai+1。

单链表的初始化

 

 

单链表元素的插入

单链表的头插法

这个时候单链表的优势就体现出来了，假如存储元素的结点为p，那么就需要插入的结点的后继指向原来L的后继，原来L的后继指向p结点。代码层面：

 需要注意的是一定要让新的结点指向头结点的下一个结点，再让头结点指向新的结点。

单链表的尾插法

在刚才的头插法中，可以看到对于新插入的元素我们把他放在表头，但其实先来后到应该算是我们比较容易接受的方法，所谓先来后到，我们每次把新插入的结点放在终端节点后面。在将尾插法之前，我们先讲如何获取尾结点。毕竟在做尾插前我们至少得找到尾结点才能对它进行操作。

获取尾结点

这个算法还是比较简单的，因为尾结点指向的next为空，所以很容易就可以理解这个算法，这里不过多赘述。

获取完尾结点我们就要进行尾插操作了，其算法语言描述与头插法大同小异，所以我们直接看代码。

尾插法

在指定位置插入元素

与头插尾插数据交替顺序类似， 只是在前面多了一步查找结点位置的操作，查找到需要插入的前驱结点，这时我们发现在指定位置插入元素的时间复杂度与顺序表相同都是O(n)。

单链表的删除

操作与在指定位置插入类似，先找到需要删除的结点位置，但需要注意的是删除操作我们需要用一个指针q记录要删除的结点，用于释放空间。代码如下：

单链表获取长度

对于单链表长度的获取，无非就是一个循环，从头结点到尾，循环中假如计数变量。进行一次循环自增一次，用于计数，该过程难度较低，这里不作讲述。

单链表释放链表：

释放链表的过程的算法描述可以这样叙述：指针p指向结点后的第一个结点，判断该结点是否指向空结点，如果p不为空，用q指针记录p的后继结点，释放p指向的结点，指针p和q指向同一个结点，循环上面操作。需要注意的是在释放过程中不删除头结点，释放过程中只释放头结点后面的结点。下面我们来看代码：

 单链表和顺表的对比

存储方式

顺序结构用一段连续的存储单元依次存储元素；链表用任意的内存但愿存储线性表的元素。

时间性能

查找

顺序表O(1)

单链表O(n)

插入和删除

顺序存储结构中插入和删除伴随大量元素的移动，时间复杂度尾O(n)。

单链表找到位置的指针后，只需改变其后继结点，时间复杂度仅为O(1)。

空间性能

顺序结构在存储时需提前分配内存空间，可能分大了浪费，分小了可能元素溢出。

单链表不需要事前分配空间，在需要插入元素时就可以分配，元素数也不受限制。

总之不论顺序表还是链表都有这样那样的优缺点，在实际需求中综合平衡决定要使用哪种数据结构，以便于解决问题。

好了这次内容就到这里，下次再聊。希望该文章对你有所帮助，如果觉得作者写的不错，点赞转发，这将成为我前进的动力！