数据结构初阶——单链表

链表的介绍

  链表是线性表的一种，但它在物理空间上并不是线性的，它是由多个物理空间连接而成，链表里的每节空间称之为节点。

  单链表节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。

  链表中的每个节点都是独立申请的，我们需要通过指针变量来保存下一节点的位置才能从当前节点找到下一节点。这为我们提供了实现链表的思路。

链表的理想结构如图，可见，第二个节点的地址是0x1122ff40，我们就将第一个节点的next指针赋值为第二个节点的地址，以此类推，这样就能将各节点链接起来，从图中我们还能看出，各个节点的地址不一定连续，但通过链接后能通过连续的方式找到每个节点里的数据，当然，最后一个节点的next指针需指向空。

链表的实现

链表的实现与顺序表类似，先创建三个文件，在SList.h头文件中，先建立多个接口，如图

在这个文件中，我们先建立的每个节点的结构，然后在声明了所有节点，这是我们的准备工作，接下来就是对接口函数的封装。

接口的封装

首先就是在链表中增添节点，也有头插和尾插的方法，当然，在插入一个新节点之前，我们需要创建一个新节点，这样，就得用到CreartNode这个接口，那我们先对这个接口实现封装

在这段代码中，我们使用malloc函数向系统申请了一个节点的空间，我们将这个节点的val赋值为x，next赋为空指针，这样就开辟好了一个新节点。

那么，接下来就是头插和尾插

我们先实现尾插，代码如下

在这个函数中，我们先判断链表是否为空，若链表为空，则头节点就为新节点，若不为空，需先找到尾节点，然后在后面插入。

接下来是头插

头插的代码较为简单，三行代码就能解决链表为空和不为空的情况。

接下来要封装的是删除的接口，有头删和尾删的方法，尾删的代码如下

尾插要分为三种情况来讨论，一是链表为空的情况，二是链表只有一个节点的情况，三是链表节点数大于一的情况。

对于情况一，我们直接用一个assert语句来判断链表是否为空，为空程序停止运行。

然后再用if..else语句来处理情况二和三，若pphead的next为空，代表链表只有一个节点，则直接释放空间，若不为空，需要一个prev指针来记录尾删后链表新的尾节点，将需删除的节点释放空间后，prev的next指针赋为NULL。

尾删结束了，接下来是头删

头删的代码也较为简单，只需几行代码就能将三种情况包含进去。与尾删相同，只需使用一个assert语句就能排除链表为空的情况，另外两种情况，定义一个tmp指针就能解决。

除了在头尾进行删除插入的操作，我们还可以在指定位置进行操作，在此之前，就需要使用到查找的接口，所以我们得先封装查找的接口，如下

使用一个循环就能找到目标节点，然后返回

接着就是在指定位置插入节点

在这串代码中，先规定了pos指针是个有效的指针，如果pos是头节点，那么可以直接使用头插接口，否则得先找到pos节点，在pos前插入新节点。

然后就是在指定位置删除了，

与指定位置插入一样，pos必须是一个有效节点，然后就是如果pos是头节点，可直接引用头删接口，然后找到pos节点的前一个节点，释放pos节点的空间。

对链表的操作接口就差不多这些了，在操作完链表，不需要用到链表之后，我们需要对链表进行销毁，代码实现如下

这样，单链表就顺利完成了

The End