数据结构_单链表

今天我们要开启链表的学习

🖋️🖋️🖋️
学了顺序表我们可以知道：
🎈链表其实就是争对顺序表的缺点来设计的，补足的就是顺序表的缺点
🎈链表在物理上是上一个节点存放的下一个节点的地址

链表

1.链表的概念及结构

1.1概念

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

1.2结构

根据上图我们可以知道：
链表是由一系列节点组成的线性数据结构，每个节点包含数据部分和指向下一个节点的指针（在双向链表中还有指向前一个节点的指针）。节点通过指针连接在一起，形成一个链式结构，数据在内存中存储并不连续。

2.链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向、双向
2.带头、不带头
3.循环、非循环
（这里图就不展示啦，大家感兴趣的可以自己去查找噢）

3.链表的实现

1.创建一个节点

typedef int SListDataType;
//节点
typedef struct SListNode
{//定义一个数据SListDataType data;//这个data就是下图中的1 2 3//定义一个指针struct SListNode* next;//next就是存放的指针
}SListNode;

这部分代码定义了一个单链表的节点结构:

• struct SListNode：定义了一个名为 SListNode 的结构体，用于表示单链表中的一个节点。
• SListDataType data;：在结构体中定义了一个成员变量 data，其数据类型为之前定义的 SListDataType（这里实际上就是 int 类型）。这个成员变量用于存储链表节点所包含的数据。
• struct SListNode* next;：定义了一个指向struct SListNode类型的指针 next。这个指针用于指向下一个链表节点，通过它可以将多个节点连接起来形成链表。

2.遍历打印链表

void SListPrint(SListNode* phead)
{//这里不需要assert断言，因为这里为空的话就是空链表SListNode* cur = phead;//指向第一个节点while (cur != NULL){printf("%d ", cur->data);cur = cur->next; }
}

画图解释：

3.尾插

//动态申请新节点并初始化
SListNode* BuySListNode(SListDataType x)
{SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));//在内存的堆区动态分配一块连续的内存空间，大小为 SListNode 结构体的字节数，再强转为SListNode*型if (newNode == NULL){printf("申请结点失败\n");exit(-1);}newNode->data = x;//将传入的数据 x 存储到新节点的 data 成员newNode->next = NULL;//初始化新节点的 next 指针为 NULL（新节点暂时无后续节点）return newNode;//返回创建好的节点地址
}//尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{SListNode* newNode = BuySListNode(x);//调用函数创建待插入的新节点if (*pphead == NULL){*pphead = newNode;//若链表为空，直接让头指针指向新节点}else{//找尾SListNode* tail = *pphead;//定义指针 tail 指向链表头部while (tail->next != NULL)//遍历链表，找到尾节点（尾节点的 next 为 NULL）{tail = tail->next;//实现遍历链表的关键代码，将指针 tail 移动到下一个节点}tail->next = newNode;//将尾节点的 next 指针指向新节点，完成尾插}}

问题：动态申请return newNode;为什么要返回创建好的节点地址

返回新节点的地址是为了让调用者能够：

1. 将节点插入链表中。
2. 后续操作节点的数据或指针。
3. 正确释放内存（避免泄漏）。

这是 C 语言中动态内存管理的标准做法，确保函数间的数据传递和内存控制权的转移。

4.尾删

//尾删
void SListPopBack(SListNode** pphead)
{//1.空//2.一个结点//3.一个以上结点// 处理空链表if (*pphead == NULL){return;//直接返回，没得删}// 处理单节点链表else if ((*pphead)->next ==NULL){free(*pphead);*pphead = NULL;//只有这一个就直接删}// 处理多节点链表else{SListNode* prev = NULL;//用于记录尾节点的前驱节点SListNode* tail = *pphead;//用于遍历链表while (tail->next  != NULL){prev = tail;//在循环中，prev 始终指向 tail 的前一个节点，tail 逐步后移tail = tail->next;//再往后走}free(tail);tail = NULL;prev->next = NULL;//将其存放的地址置空，避免内存泄漏和悬空指针}
}

5.头插

//头插
void SListPushFront(SListNode** pphead, SListDataType x)
{SListNode* newnode = BuySListNode(x);//创建新节点newnode->next = *pphead;//新节点的 next 指向原头节点*pphead = newnode;//更新头指针为新节点
}

步骤分析：

• 步骤 1：创建新节点
  调用 BuySListNode(x)：
  动态分配内存，初始化data为 x，next 为 NULL。
• 步骤 2：连接新节点与原头节点
  newnode->next = *pphead;：
  若原链表非空，新节点的next指向原头节点（形成链式关系）。
  若原链表为空（*pphead == NULL），新节点的next仍为 NULL。
• 步骤 3：更新头指针
  *pphead = newnode;：
  将头指针pphead指向新节点，使其成为链表的新头部。

画图解释：

注意：

1. 核心原因：头指针是链表的入口，必须指向第一个节点。头插法中，新节点成为第一个节点，因此必须更新头指针。
2. 技术实现：通过双重指针修改原始头指针，确保链表结构正确。若省略此步骤，新节点将无法被链表访问，导致内存泄漏或逻辑错误。

6.头删

//头删
void SListPopFront(SListNode** pphead)
{//1.空//2.一个节点 + 3.一个以上节点if (*pphead == NULL){return;}else{SListNode* next = (*pphead)->next;//保存头节点的下一个节点 free(*pphead);// 释放头节点内存*pphead = next;// 更新头指针为原头节点的下一个节点  }
}

详细分析：

• 保存后续节点：SListNode* next = (*pphead)->next; 记录原头节点的下一个节点，防止链表断裂。
• 释放内存：free(*pphead); 释放原头节点的内存，避免内存泄漏。
• 更新头指针：*pphead = next; 使头指针指向原头节点的下一个节点，完成头删。

举个例子：

注意：

1. 左边 next：是程序员自定义的指针变量，用于临时存储地址。
2. 右边 next：是链表节点结构体固有的成员，用于维系链表的链式结构。

二者仅名称相同，但一个是变量标识，一个是结构体成员，功能和性质完全不同。

7.单链表查找

// 单链表查找
SListNode* SListFind(SListNode* phead, SListDataType x)
{SListNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

详细分析：

• SListNode* cur = phead;定义一个指针cur并初始化为 phead，用于遍历单链表。cur 会从链表的头节点开始，依次向后移动;
• 在循环内部，使用if语句检查当前节点cur的数据域data是否等于要查找的值 x。如果相等，则表示找到了目标节点，直接返回 cur，即该节点的指针。
• cur = cur->next;如果当前节点的数据域不等于 x，则将cur指针更新为指向下一个节点，继续向后遍历链表。
• return NULL;如果while循环结束后仍未找到值为x的节点，说明链表中不存在该值，此时返回 NULL

在test函数中实现时：

最后的打印结果为：
（将3修改为了30）

8.单链表在pos位置之后插入x

void SListInsertAfter(SListNode* pos, SListDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

问题：分析思考为什么不在pos位置之前插入？

原因：单链表的单向性决定了插入操作必须依赖前驱节点的遍历，若pos无法通过遍历到达（如越界或无前驱），则无法实现插入。

实例：若链表为1→2→3，想在节点2前插入0，需先找到节点1（前驱），再修改其指针为1→0→2→3。若无法找到前驱（如pos为4），则插入失败。

关键指针操作分析

• newnode->next = pos->next;
pos->next 是pos节点原本指向的下一个节点的指针。
  这行代码的作用是让新节点newnode的next指针指向pos节点原来的下一个节点。其目的是在插入新节点时，保证新节点能够连接到原链表中pos节点之后的部分，避免丢失后续的节点。可以把它理解为 “记住”pos节点后面的节点，以便后续正确连接链表。
• pos->next = newnode;
  这行代码将pos节点的next指针指向新节点 newnode。
  结合上一步，这就完成了将新节点插入到 pos 节点之后的操作。此时，pos 节点后面跟着新节点 newnode，而新节点 newnode 后面接着原链表中 pos 节点原本的后续节点，链表结构更新成功。

画图分析：

9.单链表删除pos位置之后的值

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos);if (pos->next)//不为空{SListNode* next = pos->next;SListNode* nextnext =next->next;pos->next = nextnext;free(next);}
}

分析思考为什么不删除pos位置？

原因：在单链表中，直接删除pos位置节点需要遍历链表来寻找前驱节点，这会增加代码的复杂度和时间成本。因此，通常建议优先采用删除后继节点或者复制后继节点值的替代方案。如果确实需要删除pos节点，就必须传递头指针的地址（即二级指针），以便在头节点被删除时能够正确更新链表的头指针。

画图分析：

详细分析：
🖋️🖋️🖋️
pos->next也就是方框1的后半个位置，存放的是next的地址；通过next指向的next也就是第二个next的后半个方框，存放的是第三个nextnext的地址；所以删除后直接将nextnext所存放的地址赋值给pos->next!

如何去调用呢？

10.接口实现

🎉🎉🎉
到这里本章就结束啦~
我们下节见~