1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

我们之前讲解了顺序表，那么顺序表的缺点体现在哪呢？

1.顺序表空间不够时需要扩容，扩容（尤其是异地扩容）是有一定代价的，其次还可能存在一定的空间浪费

2.在头部或者中部插入或删除，需要挪动数据，效率低下

据此我们就提出了链表，可以按需申请空间，且不需要挪动数据，来对此缺点进行优化

下面我们就来进行正文单链表的讲解吧！

2.单链表的结构

单链表的结构包含了一个数据域和一个指针域，它的特点就是通过指针域的指针指向下一个结点的地址来达到链式存储

typedef int SLTDataType;//数据类型
typedef struct SListNode
{
  SLTDataType data;//数据
  struct SListNode* next;//指向下一个节点的指针
}SLTNode;

图示：

3.接口实现

3.1创建一个结点

单链表是由一个个独立的结点链接起来的，新增节点时就需要向内存申请一个结点空间

//创建一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)  //防止申请失败
  {
    perror("malloc fail");
    exit(-1);
  }
  //赋值
  newnode->data = x;
  newnode->next = NULL;
  //返回新节点
  return newnode;
}

这里用malloc申请空间，而不是用结构类型变量，是因为前者申请的空间是在堆区中开辟存放的，出了函数栈帧数据仍然存在，但是用结构类型变量，出了函数栈帧就销毁了，并不能存储数据

3.2创建一个单链表

创建一个单链表

//创建一个单链表
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  int x = 0;
  for (int i = 0; i < n; ++i)
  {
    //scanf("%d", &x); //手动输入
    //SLTNode* newnode = BuySLTNode(x);
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode; //创建头结点
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode; //变动ptail指针指向新节点
    }
  }
  ptail->next = NULL; //尾结点指空
  return phead;
}

3.3打印链表

遍历单链表将其数据域打印出来

//打印链表
void SLTPrint(SLTNode* phend)
{
  SLTNode* cur = phend;
  while (cur) //cur指针遍历到NULL就结束
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

3.4尾插

首先创建一个新结点，然后通过头结点向后遍历找到尾结点，最后将尾结点与新节点链接起来，这里还要考虑一种情况，如果链表为空就直接把新结点赋给头结点

//尾插
void SLTPushBack(SLTNode** pphend, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphend == NULL)
  {
    *pphend = newnode;
  }
  else
  {
    //找尾
    SLTNode* tail = *pphend;
    while (tail->next)
    {
      tail = tail->next;
    }
    //插入
    tail->next = newnode;
  }
}

这里有个问题就是为什么函数传参要用二级指针？

这是因为进行插入删除操作时，如果需要对头结点进行操作来改变头结点，就要改变头结点指针的指向，改变一级指针需要用二级指针来操作

3.5尾删

首先需要通过头结点向后遍历找到尾结点的前一个结点，然后释放掉尾结点，最后再将尾结点的上一个结点指空，这里需要断言处理链表为空的情况（为空不能删），还有只剩一个结点的情况，就直接释放掉头结点并将头指针置空（防止野指针）

//尾删
void SLTPopBack(SLTNode** pphend)
{
  assert(*pphend);
  //只剩一个头结点的情况
  if ((*pphend)->next == NULL)
  {
    free(*pphend);
    *pphend = NULL;
  }
  else
  {
    SLTNode* tail = *pphend;
    //找尾
    while (tail->next->next)
    {
      tail = tail->next;
    }
    //写法二：遍历找到尾结点并记录前一个结点的位置
    //SLLNode* pre = *pphead;
    //SLLNode* tail = *pphead;
    //找尾
    //while (tail->next != NULL)
    //{
      //pre = tail;
      //tail = tail->next;
    //}
    //释放
    free(tail->next);
    tail->next = NULL;
  }
}

3.6头插

首先创建一个新的结点，再将新结点与头结点链接，最后将头结点更新为新的结点即可

//头插
void SLTPushFront(SLTNode** pphend, SLTDataType x)
{
  //创建新节点
  SLTNode* newnode = BuySLTNode(x);
  //链接
  newnode->next = *pphend;
  //更新头结点
  *pphend = newnode;
}

3.7头删

先保存头结点的下一个结点的地址，再释放掉头结点，最后将头结点更新为新的结点即可，当然这里还要断言链表为空的情况（为空不能删），凡是进行删除的操作都要考虑一下是否有不能删的情况

//头删
void SLTPopFront(SLTNode** pphend)
{
    //断言链表为空
  assert(*pphend);
  //保存头结点的下一个结点的地址
  SLTNode* next = (*pphend)->next;
  //释放头结点
  free(*pphend);
  //更新头结点
  *pphend = next;
}

3.8查找结点位置

输入结点数值遍历并比较来查找该结点，找到了就返回结点位置，没找到或者链表为空就返回NULL。查找函数主要是配合后面的任意位置的插入删除操作的

//查找结点位置
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
      //遍历比较
    if (cur->data == x)
    {
        //找到就返回地址
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

3.9 任意位置之后插入

首先查找到目标位置（通过查找函数），并创建一个新的结点，再将新结点指向目标位置的下一个结点，最后将目标结点指向新结点，这里还需要断言一下没找到目标结点返回NULL的情况

//任意位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  //断言没找到的情况
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

3.10 任意位置之前插入

首先从头结点遍历找到目标结点的上一个结点，并创建一个新节点，然后将目标结点的上一个结点指向新结点，最后再将新节点指向目标结点，如果链表为空就复用头插，因为同时还需要改变头结点的位置，所以这里传二级指针，这里还需要断言链表不为空，但是pos为空的情况

//任意位置之前插入
void SLTInsert(SLTNode** pphend, SLTNode* pos, SLTDataType x)
{
    //断言链表不为空，但是pos为空的情况
  assert(pos);
  //头插
  if (*pphend == pos)
  {
    SLTPushFront(pphend, x);
  }
  else
  {
    SLTNode* prev = *pphend;
    //遍历找到目标结点的上一个结点
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    //链接
    prev->next = newnode;
    newnode->next = pos;
  }
}

3.11任意位置之后删除

首先记录目标位置的后一个位置的结点的地址（防止释放掉目标位置的后一个位置后地址丢失），然后释放掉目标位置的后一个位置，最后再将目标位置指向其后两个位置的结点，这里需要断言pos为空的情况，还要考虑只剩一个头结点其后面没有结点可删除的情况

//任意位置之后删除
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //只剩一个头结点
  if (pos->next == NULL)
  {
      perror("err");
    return;
  }
  else
  {
        //记录目标位置的后一个位置的结点的地址
    SLTNode* nextNode = pos->next;
    //链接
    pos->next = nextNode->next;
    free(nextNode);
    //nextNode为局部变量，可以不考虑置空
  }
}

3.12任意位置删除

首先遍历找到目标结点的上一个结点，然后将目标结点的上一个结点指向目标结点的下一个结点，最后释放掉目标结点即可，这里需要断言pos为空的情况和链表为空的情况（为空不能删），还需要注意如果来链表只剩一个头结点就可以直接复用头删，因为同时还需要改变头结点的位置所以这里传二级指针

//任意位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    //断言链表为空的情况
  assert(*pphead);
  assert(pos);
  //头删
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    //为什么无需置空？
    //pos是栈帧中局部变量
    //为什么必须free?
    //malloc出来的,堆区中存放数据，必须手动free还给操作系统
    //如果不free在用的时候就是野指针
  }
}

3.13销毁链表

因为链表中的元素不是连续存放的，所以销毁时只能逐个结点销毁，我们的方法是挨个儿结点遍历链表，并记录该节点下一个结点的位置（防止位置丢失），然后释放掉该节点并使用后一个节点的位置继续向后遍历销毁直到链表为空。最后一定要释放头指针，虽然链表已经释放完了，但是*pphead依然指向头结点的位置，就是野指针，所以必须置空

//销毁链表
void SLTDestroy(SLTNode** pphead)
{
    //断言指针为空
    assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
      //记录下一个结点的位置
    SLTNode* next = cur->next;
    //释放
    free(cur);
    //继续向后遍历
    cur = next;
  }
  *pphead = NULL;
}

单链表的介绍到这里就介绍结束了，期待大佬们的三连！

文章有写的不足或是错误的地方，欢迎私信或评论指出，我会在第一时间改正

单链表（C语言实现）