本篇主要总结单链表是如何实现的，数据结构是如何管理数据的，详细的介绍每一步是如何实现以及各种注意事项。

🚀1.单链表的实现🚀

单链表能实现什么功能呢？数据结构对数据的管理无外乎增删查改，让我们一一实现它吧！

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTData;//在单链表要使用的数据类型，可根据需要改动
typedef struct SLTNode  重定义单链表类型名
{
  SLTData data;//单链表中结点一般都含有两个元素，一个数据
  struct SLTNode* next;//一个指向该该结点类型的指针
}SLTNode;//结点
SLTNode* BuySLTNode(SLTData x);//生成新结点的函数
void SLTPrint(SLTNode* pphead);//单链表的打印
void SLTPushBack(SLTNode** pphead,SLTData x);//单链表的尾插
void SLTPushFront(SLTNode** pphead, SLTData x);//单链表的头插
void SLTPopBack(SLTNode** pphead);//单链表的尾删
void SLTPopFront(SLTNode** pphead);//单链表的头删
SLTNode* SLTFind(SLTNode** pphead, SLTData x);//单链表的查找
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置前面插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//在pos位置之前删除
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTData x);//在pos位置之后插入
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//在pos位置之后删除

🍭1.1单链表的尾插

单链表的尾插。我们要注意到我们传给尾插函数的是二级指针，也就是指向链表的指针的指针，为什么要传二级指针呢？

因为我们要在该函数内部修改指向链表的指针，让它指向别的的地方去，这就将它修改了，要想将该变量真正的修改成功，从内到外都要修改我们就得传它的指针，不然在函数内部修改成功，但在函数外部没有修改那又有什么用呢？

其实这就是典型的形参的改变不影响实参，只不过如果这里的实参是指向结点的指针，然后尾插函数接收参数也是指向结点的指针，那修改形参就无法改变实参，必须将指向结点的指针的地址传过去，然后用二级指针来接收，这样对形参的修改才可以改变实参。

并且一开始我们还要进行对该二级指针断言，防止有人传错指针，又传入一级指针类型。

好，让我们回到这个尾插函数。

尾插一个结点，我们首先要需要生成一个新的结点newnode.

我们首先想前面有一系列结点，而尾插只要在最后一个结点的后面接上即可，这时我们需要是最后一个结点的地址。

所以我们需要找尾。注意找尾while里进行的条件是tail->next!=NULL,这样才能找到最后一个结点

而不能写成while(tail!=NULL),这样找到的不是最后一个结点而是最后一个结点的后面。

接着我们再分析如果前面没有结点，那么直接将新生成的结点与指向链表的指针链接起来即可。

void SLTPushBack(SLTNode** pphead, SLTData x)//尾插
{
  assert(pphead);
  SLTNode* newNode = BuySLTNode(x);//生成一个新结点
  //如果前面没有结点
  if (*pphead == NULL)
  {
    *pphead = newNode;//直接将新结点赋给指向链表的指针
  }
  else
  {
    //假设前面有结点
  //找尾
    SLTNode* tail = *pphead;
    while(tail->next!= NULL)
    {
      tail = tail->next;//往后走
    }
    tail->next = newNode;//最后将新结点与最后一个结点链接
  }
}

🍭1.2单链表的头插

单链表的头插。

首先对二级指针断言，看是否合法

先假设前面有结点，然后生成新结点进行头插。

头插就是将指向链表的指针一开始指向新结点，再让原先第一个结点与新结点链接起来。

然后再假设前面没有结点，分析没有结点和有结点都可以。

void SLTPushFront(SLTNode** pphead, SLTData x)//头插
{
  assert(pphead);//断言判断
  SLTNode* newNode = BuySLTNode(x);//生成新结点
  //假设前面有结点.发现有结点和没有结点一样
  newNode->next = *pphead;//将原先第一个结点与新结点链接起来
  *pphead = newNode;//再让新结点与指向链表的指针连接起来
}

🍭1.3单链表的打印

单链表的打印。

其实本质也是循环打印，只不过不同与顺序表的下标循环，链表是没有顺序的，根据结点的next来进行循环

我们一般不让形参改动，而是重新将形参赋给给一个新元素，这样使用起来更好，因为如果在使用的过程中，又需要头地址的地方，就可以直接使用。

利用cur进行遍历。注意这里循环的条件是cur！=NULL

而不能写成cur->next!=NULL,如果写成这样那么最后一个元素就无法打印出来了，因为最后一个结点的next就为NULL

到最后一个结点就结束了

void SLTPrint(SLTNode* phead)//打印单链表
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);//打印每个结点的数据
    cur = cur->next;
  }
  printf("NULL\n");
}

🍭1.4单链表的尾删

单链表的尾删。

我们要想删除数据就要进行判断是否删除过头，每次删除之前都要进行断言判断，一旦删除过头就立刻停止。

所以这里我们除了对二级指针断言之外，还需要对指向链表的指针进行断言也就是一级指针，对二级指针解引用即可。

首先我们假设前面有结点，然后尾删也就是删除最后一个结点，同时还需要将前一个结点的next置NULL

不然就变成野指针了。

这里有两种方法来找到前面一个结点的next。

一种是再定义一个指针prev来记录tail遍历链表的前面结点的位置。

最后tail找到尾结点释放tail，再将prev的next置为NULL，即可。

另一种是通过不去找真正的尾结点而实现。

也就是while(tail->next->next)

这里找的不是真正尾结点，而是尾结点前面的。

最后释放tail->next即可

再将tail->next置为NULL.

接着就是假设前面只要一个结点时，该怎么删呢？直接释放即可。

void SLTPopBack(SLTNode** pphead)//尾删
{
  assert(pphead);
  //暴力检查是否删过头
  assert(*pphead);
  //假设前面只有一个结点时。
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}

🍭1.5单链表的头删

头删与尾删一样都需要对二级指针和一级指针进行断言判断。

假设前面有结点，进行头删，就是让指向链表的指针指向第二个结点，将第一个结点删除掉。

假设前面没有结点，分析发现都适用。

void SLTPopFront(SLTNode** pphead)//头删
{
  assert(pphead);
  assert(*pphead);//暴力检查
  //假设前面只有一个结点
  //和
    //假设前面有结点
    SLTNode* first = *pphead;
    *pphead = first->next;//将第二个结点与指向链表的指针链接
    free(first);//删除第一个结点
    first = NULL;
}

🍭1.6单链表的查找

单链表的查找，就是根据所给的数据进行遍历，没有什么好的方法

如果与给的数据相同则返回该地址。如果找不到就返回NULL。

通常查找与修改连在一起，先查找到该结点的数据，然后对该数据进行修改。

SLTNode* SLTFind(SLTNode** pphead, SLTData x)//查找
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    if (cur->next == x)
    {
            return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

🍭1.7单链表的插入

与上面的讲的单链表的头插和尾插不一样，这里讲的是给定位置pos，然后将数据插入想要插入的位置，不过对于单链表的插入，通常都是在位置pos的前面插入数据，而不是在pos的后面插入数据，我们分别来看看这两种插入的不同

在pos前面插入就想要pos前面结点的地址了，并且遍历循环的条件也发生变化。

插在pos的前面

1.如果链表有结点，那我们将新结点与pos位置前面的结点链接起来，再让pos与新结点链接起来。

如果没有结点就相当于头插了。

2.插在pos的后面

插在后面都不要遍历找了，直接将新结点放在pos的后面，将pos的next与新结点链接，再将新结点与pos链接

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTData x)//在pos位置前面插入
{
  assert(pphead);
  assert(pos);
  //如果没有结点
  if (pos == *pphead)
  {
    SLTpushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
void SLTInsertAfter( SLTNode* pos, SLTData x)//在pos位置之后插入
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

🍭1.8单链表的删除

单链表的删除分为在pos位置的前面删除还是在后面删除

不过首先都需要对二级指针和一级指针断言。

1.在pos位置之前删除

假设前面有结点，删除pos前面的结点，需要前面结点位置的地址

找到后将该结点点释放。

假设前面只有一个结点，相当于头删。

2.在pos位置之后删除

首先要将pos后面的结点的位置记录下来

然后将后面的结点与pos链接起来将pos后面的结点释放

void SLTErase(SLTNode** pphead, SLTNode* pos)//在pos位置之前删除
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SLTpopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev->next = pos->next;
    }
    free(pos);
    pos = NULL;
  }
}
void SLTEraseAfter( SLTNode* pos)//在pos位置之后删除
{
  assert(pos);
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}

【数据结构】单链表的实现