链表是一种很重要的数据结构，它由两部分组成，第一个部分是我们要储存的数据，第二个部分是指向下一个储存单元的指针。链表在使用中有顺序表无法比拟的灵活性，免去了储存空间不够，又有可能浪费的尴尬。

单链表有一个头指针pHead，当我们没有数据要储存的时候它指向NULL，当我们有数据的时候它指向第一块储存单元。储存单元里面有两个部分，前面的部分是我们要储存的数据data，后面的部分是指向下一个储存单元的指针pNext，当后面没有储存单元的时候就指向NULL。那么我们储存的数据在内存中并不是连续储存的，而是在内存中跳跃式储存的。要使用的时候再直接申请一块空间。

下面是链表的定义：

可以看到单链表的两个成员。为了使用方便我们直接typedef重命名。

单链表有几种基本操作，比如插入数据，删除数据，那我下面实现了一下。

首先，我写了一个申请新单元的函数：

它可以为我们直接在内存中申请一块新的空间并且返回它的地址。

第一个实现就是我们从尾部插入数据：

这里我们传的参数是二级指针，因为我们是要改变它指针的指向。假如我们直接传递一级指针，那么我们并不能改变它的指向，相当于我们函数中操作了半天，其实都是在操作一个临时的指针变量，只不过他跟我们的头指针的指向是一样的，最后什么也没有返回，头指针什么变化都没有。

接下来就是我们从尾部删除数据的实现：

注释中的代码是我刚开始的时候写的，我发现他的逻辑不是很清晰，在第二个部分中我把链表中只有一个节点的情况单列了出来，逻辑比之前清晰了很多。

那我们也可以在链表的头部插入数据：

思路有了之前的两个函数做铺垫想起来并不难。申请一块新的空间之后，让它的pNext指向我们之前的第一块空间。然后改变我们的头指针的指向，让它指向我们的新空间。这里注意我们申请空间是有可能失败的，所以要判断一下。

当然还有从头部删除：

千万不要忘记free空间之后要给指针赋空，否则会形成野指针。

还有就是寻找我们链表中的元素：

注释掉的代码是我第一次写的，后来我发现它的逻辑有点问题，我可以更简单的实现它的功能。

最后返回我要找的数据的位置，假如没有找到那么就返回空。

打印我链表中的元素：

删除我的任意位置的节点：

在我的链表的任意位置插入一个节点：

作者：刘子蛋gogogo博客