前言

在学习数据结构时，单链表可谓是第一个需要跨越的台阶。

从C语言到数据结构，单链表能够真正的反映我们C语言到底学的扎不扎实，那是因为，单链表对于C语言中的指针，结构体，以及函数模块的实现有较高的要求。因此，通过本章的学习，要是能够自我实现单链表，那你的C语言功底会厚实，你的代码能力也会提升。

当然，从C语言到数据结构阶段，单链表只是第一个需要跨越的台阶，后面还有更难的数据结构在等着大家，后面我会相继出文章。

单链表与顺序表的比较

顺序表与单链表同属于线性表, 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

不同：

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
  
• 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
  

顺序表扩容一般是二倍扩，这势必会有空间浪费。而单链表非如此，你想增加一个节点，就向内存申请一个节点，想去掉一个节点，就释放返还这个节点给内存。这就体现了，在扩容方面，单链表比顺序表要优。

顺序表在头插头删或者在任意位置插入删除都需要挪动数组的数据，这必然会使效率下降，时间复杂度最多是O(N^2)。而单链表的这些操作，不需要挪动数据，最多也就O(N)。所以，在增删数据方面，单链表优于顺序表。

当然顺序表优于单链表的情况是访问数据操作，顺序表可以直接通过下标访问，为O(1)。而单链表需要从头开始依次寻找，为O(N)。

单链表初始操作

同样的，这里也需要三个文件，一个是SList.h（头文件），SList.c（实现函数接口的文件），test.c（测试文件）。

SList.h存放需要使用的库函数的头文件以及单链表节点结构体和接口函数声明。

分析单链表的结构，我们需要一个变量来存放数据，需要一个结构体指针来指向下一个节点进行连接，所以初始操作如下：

#include <stdio.h>
// malloc 所需头文件
#include <stdlib.h>
// assert断言所需头文件
#include <assert.h>
// 每个节点存放的数据的类型
typedef int SLTDataType;  // 这里只需改变int就可以存放不同的数据
// 节点
typedef struct SListNode
{
  SLTDataType data;
  // 存放下一个节点的地址，依此进行链接形成单链表
  struct SListNode* next;
}SListNode;  // typedef 重命名为 SListNode，后面写起来方便

对应的函数接口有：

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// 单链表修改节点的data
void SListModify(SListNode* pos, SLTDataType NewData);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表删除pos位置的值
void SListErasePos(SListNode** pplist, SListNode* pos);
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** pplist, SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);

我们只需要在SList.c与test.c文件开头包含SList.h,即可链接。

• 有了上述的初始操作，接下来只需将头文件里的函数接口一一实现即可。

得到一个节点

单链表的每一个元素我们称之为节点，每个节点存放着相应的数据和下一个节点的地址

单链表从得到一个节点开始，由于后面的插入形式有多种，而在每个插入函数中都写得到一个节点的代码，未免有些麻烦，因此，这里将得到一个节点的功能单独拿出来作为一个函数，要插入直接调用这个函数获取节点即可。

每当获取一个节点的时候，节点内的结构体指针都指向NULL。

这里的节点是我们通过malloc在内存中申请的一段空间来存放的，并且每个节点之间的地址不连续（随机申请，可能相邻）。

当我们向内存申请了一个节点时，需要返回指向这个节点的指针，如果不返回的话，函数结束后，指向这个节点的指针会被销毁，此时这个节点就找不到了，也就出现了内存泄漏的问题，所以，一定要返回指向这个节点的指针。

下面是相关接口函数的代码：

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  // 判断一下是否申请失败，malloc申请失败返回空指针
  assert(newnode);
  // 存放相应数据
  newnode->data = x;
  // 初始化NULL
  newnode->next = NULL;
  // 返回指向这个节点的指针
  return newnode;
}

单链表的打印

由于单链表是用指针相连的，因此也需要运用指针来遍历单链表。

我们只有单链表的头指针，运用这个头指针，依次向下找节点并打印相应的数据，直到这个指针为NULL结束。因此，遍历单链表的循环条件是这个指针不为NULL。

如果传递过来的头指针是空，也就说明这个单链表是空链表，此时循环不会进去，也就不会打印。

所以，该函数模块不需要assert来判断单链表是不是空链表。是空他就不打印嘛。

对于如何遍历，如果phead是指向头节点的指针，我们只需要phead = phead->next;即可使phead指向下一个节点。

下面是相关接口函数的代码：

// 单链表打印
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  // 如果cur为NULL停止循环
  while (cur)
  {
    printf("%d ", cur->data);
    // 跳到下一个节点
    cur = cur->next;
  }
  // 最后指向NULL，打印NULL
  printf("NULL\n");
}

单链表的销毁

由于单链表的每一个节点是用 malloc 在堆上申请的空间，因此，在程序运行的最后需要将这些空间返还给操作系统。

返还空间给操作系统使用的对应函数为free ，这里，我们不能天真的以为free指向头节点的指针就可以释放掉整个链表，因为每一个节点的空间分配是不连续的，所以这里也是要遍历一遍单链表，并依次释放每一个节点的空间。

由于又要释放节点，又要遍历单链表，因此这里需要两个指针来操控，一个指针用来释放指向对应的空间，一个指针用来存放下一个节点的地址。

我这里的销毁函数是传递一个二级指针的，也就是传递单链表的头指针的地址。当然，就将单链表的头指针传递过来也是可以的，我是为了能够释放完所有空间后将单链表的头指针置为NULL才这样做的（怕有人销毁完单链表后还用之前的单链表的头指针进行操作）。

当然，此函数需要assert断言判断传过来的二级指针是否是NULL指针。如果是空指针就不再进行后续的操作了。但是，单链表可以为空，因为他为空的话，解引用二级指针（单链表的头节点指针）就为空，此时循环就不会进去。

下面是相关接口函数的代码：

// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
  assert(pplist);
  SListNode* cur = *pplist;
  // cur为空的话while不执行
  while (cur)
  {
    SListNode* tmp = cur;
    cur = cur->next;
    free(tmp);
  }
  *pplist = NULL;
}

单链表的尾插

既然是插入，就需要获取一个节点，这时候就需要调用BuySListNode函数了。

单链表的尾插是比较简单的，通过循环利用指针依次寻找下一节点，直到找到最后一个节点为止，在将最后一个节点的节点指针next指向新的节点即可。

如果此时单链表为空，当然也是可以插入的，只不过这里就需要分两个情况了，就是单链表为空和不为空。

当单链表为空时插入，此时就是插入一个头节点，所以传过来的空指针要指向这个头节点，也就是节点指针需要改变。在调用函数时，一个指针的值需要改变，那就需要传递这个指针的地址，所以该函数需要使用二级指针来接受这个指针的地址。

• 由于是二级指针，因此这里需要assert断言一下这个二级指针，怕直接传递一个空指针过来或者传递一个一级指针。

下面是相关接口函数的代码：

// 单链表尾插
// 二级指针接收一级指针的地址
void SListPushBack(SListNode** pplist, SLTDataType x)
{
  // 断言二级指针，截断二级指针为NULL的情况
  assert(pplist);
  // 获取一个结点
  SListNode* newnode = BuySListNode(x);
  // 如果单链表为空，更新头节点即可
  if (*pplist == NULL) *pplist = newnode;
  else
  {
    SListNode* cur = *pplist;
    // 遍历找尾节点，如果该节点的next为NULL，说明此节点就是尾节点，停止循环
    while (cur->next) cur = cur->next;
    // 连接新的尾
    cur->next = newnode;
  }
}

单链表的头插

既然是插入，就需要获取一个节点，这时候就需要调用BuySListNode函数了。

单链表的头插不需要遍历单链表，只要将新节点的next指向此时单链表的头节点即可。当然单链表指向头节点的指针需要改变指向新的头节点。既然需要改变头指针，那么此时就需要用到二级指针来操作了。

如果此时单链表为空，也是一样，直接插入，更改头指针（二级指针操作）指向这个结点即可。

下面是相关接口函数的代码：

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  // 如果单链表为空，更新头节点即可
  if (*pplist == NULL) *pplist = newnode;
  else  // 不为空则将newnode的next指向当前的头节点即可
  {
    newnode->next = *pplist;
    // 更新头节点
    *pplist = newnode;
  }
}

单链表的尾删

尾删，既然是尾，那么就需要遍历单链表找尾，但要注意的是，我们还需要找到尾的前一个节点，因为删完尾后，新的尾的next需要置为NULL。

既然需要找到尾的前一个节点，那么循环内就需要两个指针来进行操作，如果说此时单链表只有一个节点，那么尾节点的前一个节点就不存在，因此此时对指向尾的前一个结点的指针进行操作就会出现问题，所以当单链表只有一个节点的时候，需要单独操作。

当只有一个节点的时候，我们直接free头节点即可。这里需要将指向头节点的指针置为NULL（避免后面对该指针进行不当的操作），因此，这里也是需要使用二级指针的。

当单链表为空的时候，是不可以删的，因此这里需要assert断言判断单链表是否为空，如果为空，直接暴力结束程序不给他删。

下面是相关接口函数的代码：

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
  // 断言判断pplist是否为NULL，判断链表是否为空（为空就不能删）
  assert(pplist && *pplist);
  // 如果此时单链表只有一个节点，直接free头节点，将指向头节点的指针置为空，此时需要二级指针来操作
  if (!(*pplist)->next) free(*pplist), * pplist = NULL;
  else
  {
    // 找尾，和找尾的前一个节点，需要两个指针来操作
    SListNode* cur = *pplist, * tmp = NULL;
    while (cur->next)  // 判断条件找到尾就停止
    {
      tmp = cur;  // 最终tmp会指向尾节点的前一个节点
      cur = cur->next;
    }
    // 释放尾节点
    free(cur);
    // 将尾节点的前一个节点置为NULL
    tmp->next = NULL;
  }
}