前言

本章我们将主要讲解：

单链表及其实现

注：如果还不会顺序表，这里附上链接：数据结构-顺序表实现超详解（小白也能看懂的保姆级教程~）

链表

概念及结构

概念：

链表是一种物理存储结构上非连续、非顺序的存储结构

数据元素的逻辑顺序是通过链表中的指针链接次序实现的

图示：

注意：

链表结构在逻辑上为连续的，但是物理上（内存中）不一定连续

链表节点都是在堆上申请出来的，申请空间按一定策略分配

结构种类

链表具有多种结构：单向\双向，带头\不带头，循环\非循环

实际上最常用的是：无头单向非循环链表，带头双向循环链表

链表的实现

注：这里具体实现无头单向非循环链表

增删查改接口

//无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 为什么不在pos位置之前插入：效率不高
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 为什么不删除pos位置：同样效率不高
void SListEraseAfter(SListNode* pos);

节点结构体创建

节点具有两个域：

参考代码：

//默认链表数据类型
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SLTNode;

链表节点开辟

对于链表来说，每需要空间就需要进行开辟，这里我们将之封装成一个函数，便于后续调用直接使用（开辟的同时进行赋值）

注意：

malloc动态开辟，进行分配节点

节点开辟成功则进行赋值

可能会开辟失败，则打印错误信息（堆空间比较大，一般来说不会失败）

参考代码：

//链表节点开辟
SLTNode* BuySListNode(SLTDateType x)
{
  //动态分配一个节点
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    //分配失败则打印错误信息并结束进程
    perror("newnode fail:");
    exit(-1);
  }
  //成功则进行赋值
  newnode->data = x;
  newnode->next = NULL;
  //返回节点地址，以便后续操作
  return newnode;
}

链表数据打印

注意：

对于不带头的链表来说，打印数据不需要修改链表首节点地址（故只要传链表指针）

用循环遍历链表，每打印数据，需要指向下一个节点

依靠尾节点的址域为NULL来结束循环

参考代码：

//链表数据打印
void SListPrint(SLTNode* phead)//一级指针接收一级指针（打印不需改变指针本身内容）
{
  //创建一个寻址指针
  SLTNode* cur = phead;
  while (cur!=NULL)//后续还有节点
  {
    //打印数据并指向下一个节点
    printf("%d->", cur->data);
    cur = cur->next;
  }
  //最后打印空指针
  printf("NULL\n");
  return;
}

链表尾插数据

注意：

对于不带头链表，尾插数据也可能是插在链表首元素的地址（当链表为空），需要修改链表指针的内容（故需要传入链表指针的地址）

插入数据要开辟节点

要尾插数据则需要遍历找到链表的尾节点

尾插则是将前一个节点的址域该成该节点地址（为空链表则是将链表指针内容该成该节点地址）

参考代码：

//链表尾插数据
void SListPushBack(SLTNode** pphead, SLTDateType x)//二级指针接收一级指针（尾插存在需改变链表指针本身内容）
{
  //避免传入错误(直接报错便于找到错误位置)
  assert(pphead);
  //接收新节点的地址
  SLTNode* newnode=BuySListNode(x);
  //头节点为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    //找尾节点
    SLTNode* tail = *pphead;//创建寻址节点
    //两个及以上节点的情况
    while (tail->next != NULL)
    {
      //指向下一个节点
      tail = tail->next;  
    }
    //找到了
    tail->next = newnode;
  }
  return;
}

注意代码中的assert的作用：

正确传入链表指针的地址是不会为空的

但是对于非正常传入链表指针（不是链表指针的地址）且此时链表指针为空则会发生报错（assert报错会告诉错误位置），告诉程序员应该传入链表指针的地址

注：这是一个非常好的代码习惯

链表前删数据

注意：

前删数据即删除当前链表首节点，即需修改链表指针的内容（故需传入链表指针的地址）

删除前需要保存当前节点的址域（即保存下个节点的空间地址，以防丢失）

删除后修改链表指针内容，指向新的首节点

如果链表为空时无法删除（保存下个节点地址会造成非法访问）

参考代码：

//链表前删数据
void SListPopFront(SLTNode** pphead)
{
  //避免传入错误(直接报错便于找到错误位置)
  assert(pphead);
  //链表为空的情况
  if (*pphead == NULL)
  {
    return;
  }
  //创建指针保存第二个节点地址
  SLTNode* next = (*pphead)->next;
  //释放当前头结点空间
  free(*pphead);
  //更新头结点数据
  *pphead = next;
  return;
}

链表数据查找

注意：

对于查找数据不用修改链表指针的内容，故只需传入链表指针就行了

查找时用循环遍历链表

查找到时则返回节点地址，否则返回NULL

参考代码：

//链表数据查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  //创建寻址指针
  SLTNode* cur = phead;
  while (cur!=NULL)
  {
    if (cur->data == x)//找到数据符合节点
    {
      return cur;//返回节点地址（好处：以便后续再寻找或修改）
    }
    else
    {
      //找下一个节点
      cur = cur->next;
    }
  }
  //未找到数据符合节点
  return NULL;
}

链表pos位置前插数据（较难）

注意：

传入的pos为NULL则报错

想要pos位置前插数据，不仅需要找到pos位置，还需要记录pos的前一个节点位置

进行修改前节点的址域成新节点，并让新节点的址域修改成pos，这才是一个成功的pos位置前插数据

循环遍历链表查找pos位置，没有找到pos位置则什么也不干

参考代码：

//链表pos位置往前插入(较难)（还有在pos位置之后插入，简单点）
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  //避免传入错误(直接报错便于找到错误位置)
  assert(pphead);
  assert(pos);
  SLTNode* newnode = BuySListNode(x);
  //首结点符合的情况
  if (*pphead == pos)
  {
    newnode->next = *pphead;
    *pphead = newnode;
  }
  else
  {
    //创建寻址指针
    SLTNode* cur = *pphead;
    while (cur !=NULL)
    {
      if (cur->next!= pos)
      {
        cur = cur->next;//找到下一节点
      }
      else // 找到对应空间
      {
        cur->next = newnode;
        newnode->next = pos;
        return;//结束寻找（否则会一直插入，造成死循环）
      }
    }
  }
  //未找到则什么也不干
  return;
}

链表pos位置后插数据（简单）

注意：

后插则不用关注是否为首节点

也不用找到遍历找到前节点的位置

后插则先将新节点址域改成pos后节点地址再将pos的址域改成新节点地址

注：一定要注意修改链接节点址域的先后，避免地址的丢失

参考代码：

//链表pos位置往后插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  SLTNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  return;
}

链表pos位置数据删除

注意：

考虑删除首节点的情况，可能修改链表指针的内容，故需要传入链表指针的地址

对于删除节点，需要先保存pos位置下一个节点地址，将pos位置释放，再将pos位置前节点的址域改成pos位置后节点的地址，这才是成功的删除pos位置节点

循环找pos位置，没找到则什么也不干

参考代码:

//链表pos位置删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  //避免传入错误(直接报错便于找到错误位置)
  assert(pphead);
  assert(pos);
  //头结点符合的情况
  if (*pphead == pos)
  {
    *pphead = (*pphead)->next;
    free(pos);
  }
  else
  {
    //创建寻址指针
    SLTNode* cur = *pphead;
    while (cur != NULL)
    {
      if (cur->next != pos)
      {
        cur = cur->next;//找到下一节点
      }
      else // 找到对应空间
      {
        SLTNode* next = cur->next->next;
        free(cur->next);
        cur->next = next;
        return;//结束寻找
      }
    }
  }
  //未找到则什么也不干
  return;
}

链表节点释放

注意:

对于动态开辟的内存空间，在使用后一定要记得的进行释放（避免造成内存泄漏）

因为链表节点是一个个开辟的，同样的释放也需要一个个进行释放

循环遍历释放当前节点前需保存后一个节点的地址，避免地址丢失无法释放

释放完后，还需将链表指针给置空（避免使用野指针）

参考代码:

//链表节点释放
void SListDestory(SLTNode** pphead)
{
  //避免传入错误(直接报错便于找到错误位置)
  assert(pphead);
  //遍历释放
  SLTNode* cur = *pphead;
  while (cur)
  {
    //保存下一个地址
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  //置空
  *pphead = NULL;
  return;
}

不带头单链表到这里就讲解完了，学完顺序表和链表我们可以将之做一个对比~

开卷数据结构？！单链表实现超详解~

前言

链表

概念及结构

链表的实现

增删查改接口

节点结构体创建

链表节点开辟

链表数据打印

链表尾插数据

链表前删数据

链表数据查找

链表pos位置前插数据（较难）

链表pos位置后插数据（简单）

链表pos位置数据删除

链表节点释放

链表与顺序表区别

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

开卷数据结构？！单链表实现超详解~

前言

链表

概念及结构

链表的实现

增删查改接口

节点结构体创建

链表节点开辟

链表数据打印

链表尾插数据

链表前删数据

链表数据查找

链表pos位置前插数据（较难）

链表pos位置后插数据（简单）

链表pos位置数据删除

链表节点释放

链表与顺序表区别

热门文章

最新文章

相关课程

相关电子书