[C语言数据结构]单链表

引：

       顺序表的缺陷：
（1）空间不够，需要扩容。扩容(尤其是异地扩容)需要一定的代价。其次由于每次扩容都是前一次的二倍，存在大量的空间浪费；

（2）插入数据的时候，需要时间来挪动数据，效率相对较低；

 那么我们有没有一种方式可以实现，空间的按需分配(要多少给多少)，并且不需要挪动数据？

所以我们接下来就来介绍，数据结构中的一种叫：链表

💊1.链表

💊1.1何为链表

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

💊1.2链表的分类

链表的种类非常多样主要由下面几种排列组合而成：

每个颜色代表一种，所以组合起来就有8中结构；

💊1.3单链表

对于其中的一种叫无头单向非循环链表，结构较为简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。

💊1.3.1单链表的逻辑结构和物理结构：

💊1.3.2无头单向非循环链表的实现：

①声明

首先我们和顺序表类似还是需要用结构体的方式来构建：唯一的区别是：结构体中的变量类型和数量都发生了变化，在单向链表这里我们只需要两个变量：一个是存储数据用的变量，我们叫数据域，另一个是用来连接前一个结点和后一个结点的，叫做指针域；因此我们直接上代码：

 

typedef int SLDateType;
typedef struct SListNode
{
  SLDateType data;
  struct SListNode* next;
}SLNode;

接下来我们要逐一实现单向链表中所需要的接口；

②申请节点：

SLNode* BuySLNode(SLDateType x)；

这个接口主要实现节点的申请，并且将数据存入新的节点，然后返回新申请的节点：

所以我们展示代码：

 

//申请节点内存空间
SLNode* BuySLNode(SLDateType x)
{
  SLNode* New = (SLNode*)malloc(sizeof(SLNode));
  New->data = x;
  New->next = NULL;
  return New;
}

注意：这块我们我们为什么要采用malloc函数来申请动态内存空间；这里需要解释一下，因为我们都知道如果在函数内部创建变量的话，这个变量是存储在栈上的，会随着函数结束而被销毁；而申请动态内存空间，这部分空间是存储在堆上的；在我们不需要的时候可以随时进行释放，提高了空间的利用率。

③打印链表数据：

void SLprint(SLNode* plist)；

这个接口实现的是依次打印出单向链表中的所有数据，实现非常简单，只需要遍历链表即可；

代码：

void SLprint(SLNode* plist)
{
  SLNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NLLL\n");
}

注意：这个接口需要注意的就是临时变量cur的创建，我们使用cur来遍历链表会使得代码的逻辑性更加的清晰。也不必为了节省空间而省去cur变量，毕竟它只占四个字节，对于硬盘空间来说微乎其微。

④单链表的尾部插入：

void SLPushBack(SLNode** pplist, SLDateType x)；

这个接口实现的是实现单链表的数据从尾部插入，逻辑来说也是相对简单；

代码：

//尾插
void SLPushBack(SLNode** pplist, SLDateType x)
{
  if (*pplist == NULL)
  {
    *pplist = BuySLNode(x);
  }
  else
  {
    SLNode* tail = *pplist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = BuySLNode(x);
  }
}

注意：这个函数内部while循环的条件我们选用的是tail->next而不是tail；因为当我们选用tail的时候就会存在新申请的节点链接不上的情况出现；并且我们会发现这个接口内部我们采用了一个分支结构其实是对空链表的情况进行考虑；

至于为什么参数是SLNode**，这是因为当链表为空的时候我们要改变的是外部指针变量，所以我们要对指针修改就需要找到指针的指针所以是二级指针；

⑤删除单链表的尾部的数据：

void SLPopBack(SLNode** pplist)；

这个接口和上面的尾插是类似的都是需要二级指针的形参，但是这个接口我们要考虑的比上面的尾插更加的多，我们要同时考虑链表为空，链表只存在一个节点，链表存在多个节点总共这三种情况；所以我们先展示代码：

//尾删
void SLPopBack(SLNode** pplist)
{
  //1.无节点
  //2.一个节点
  //3.三个节点
  if (*pplist == NULL)
  {
    return;
  }
  else if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
    return;
  }
  else
  {
    SLNode* pre = NULL;
    SLNode* tail = *pplist;
    while (tail->next != NULL)
    {
      pre = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
    pre->next = NULL;
  }
}

注意：如上我们采用了三个分支结构，分别从三种情况进行考虑，第一种就是链表为空的情况，直接返回；第二种就是存在一个节点的情况，直接将头指针置空即可；第三种情况，也就是存在多个节点的情况，我们先要找到尾节点，然后再将其进行释放即可；

 

⑥向单链表的头部插入数据：

void SLPushFront(SLNode** pplist, SLDateType x)；

上代码：

//头插
void SLPushFront(SLNode** pplist, SLDateType x)
{
  SLNode* New = BuySLNode(x);
  New->next = *pplist;
  *pplist = New;
}

注意：我们可以看出头插是不需要考虑节点的数量的，从另一方面来理解的话就是，向数据中增加节点应为节点的数量不会变少所以，不会出现新的问题；

 

⑦从单链表的头部删除数据

void SLPopFront(SLNode** pplist)；

对于删除我们还是和上面的尾删类似，需要考虑节点数量的问题

代码：

//头删
void SLPopFront(SLNode** pplist)
{
  if ((*pplist) == NULL)
  {
    return;
  }
  else
  {
    SLNode* Temp = *pplist;
    *pplist = (*pplist)->next;
    free(Temp);
    Temp = NULL;
  }
}

注意：对于头删的话我们只需要考虑有节点和无节点的情况，对于无节点的情况，我们只需要直接返回即可，对于有节点的我们先要创建一个临时的指针变量来存储头指针的下一个指针，然后将头指针释放掉之后，再将临时指针赋值给头指针即可；

⑧单链表的查找
SLNode* SLFind(SLNode* plist, SLDateType x); 用于寻找链表中的节点逻辑非常简单就是遍历数组；
代码：

//单链表查找
SLNode* SLFind(SLNode* plist, SLDateType x)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

注意：分别来应对链表为空， 链表只有一个节点，链表有多个节点的情况；这种办法可以解决空指针访问的问题；

⑨向链表的指定位置后插入数据：
代码：

//在对应后位置插入
void SListInsertAfter(SLNode* pos, SLDateType x)
{
    assert(pos);
    SLNode* New = BuySLNode(x);
  New->next = pos->next;
  pos->next = New;
}

注意：这里有一个细节就是要先让新节点先指向pos->next;然后再把新节点给pos->next;这样就可以保证不会丢失节点

⑨向链表的指定位置前插入数据：
void SListInsertAfter(SLNode** pphead, SLNode* pos, SLDateType x)；
因为我们在这个函数内部可能会需要修改头指针，所以我们需要采用二级指针来访问；
代码：

//在对应位置前插入
void SListInsertAfter(SLNode** pphead, SLNode* pos, SLDateType x)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLNode* new = BuySLNode(x);
    prev->next = new;
    new->next = pos;
  }
}

注意：这个函数值得注意的一点就是要判断pos的位置是不是head的位置，所以我们用if来判断了一下，因为是这种情况的话我们可以直接调用头插的方法直接做到。

⑩删除pos后的第一个节点
void SListEraseAfter(SLNode* pos)；
这个函数就是要先判断一下，pos的位置之后是否有节点，如果没有节点的话那就直接返回即可；
代码：

//在对应后位置删除
void SListEraseAfter(SLNode* pos)
{
  SLNode* cur = pos;
  cur = pos->next;
  if (pos->next == NULL)
  {
    return;
  }
  else if (cur->next == NULL)
  {
    //删除即可
    cur = cur->next;
    free(cur);
    cur = NULL;
  }
  else
  {
    SLNode* temp = pos->next;
    pos->next = temp->next;
    free(temp);
    temp = NULL;
  }
}

注意：这个函数值得注意的一点就是需要谨慎防止野指针问题！

⑪删除pos位置
这个接口实现的是对于传入的pos位置对应节点的删除；逻辑也是很简单：
代码：

//删除对应的位置
void SListErase(SLNode** pphead, SLNode* pos)
{
  assert(pos);
  if (pos == *pphead)
  {
    //直接头删
    SLPopFront(pphead);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

以上就是单链表常用接口的实现了！
数据结构的学习笔记还在持续更新，需要的老铁可以关注一手！