链表的定义和结构
链表是一种在计算机科学中常用的数据结构，用于存储元素的集合。它与数组相比，链表的元素不是在内存中连续存储的。链表由一系列节点组成，每个节点至少包含两个部分：一个是存储的数据，另一个是指向列表中下一个节点的指针（或引用）。通过这种方式，链表中的节点被串联起来
在顺序表中，我们的数据存储在数组中，每个数据在内存中连续存储，意味着可以通过索引直接访问任何元素
我们对顺序表进行数据的插入，物理空间不变，数据依次挪动。
链表中，我们每个节点的地址没有关联，是随机的，但是每个节点都有一个**指针，**让这个指针指向下一个节点的地址
我们设phead指针指向第一个地址，第一个节点的指针指向第二个节点的地址，最后一个节点的指针指向空
如果我们想在2 3节点中间插入新的数据a，并不需要挪动任何数据，只需要将2的指针指向a的地址，a的指针指向3的地址
若要删除3的数据，我们只需将2的指针指向4，并将3的空间释放掉即可
单链表的创建
1. typedef int SLNDataType; 2. 3. typedef struct SListNode 4. { 5. SLNDataType val; 6. struct SListNode* next; 7. }SLNode;
其中typedef int SLNDataType;在顺序表中我们进行了讲述，为类型抽象
typedef struct SListNode { SLNDataType val; struct SListNode* next; }SLNode; val
用于存储节点中的数据。数据类型由 SLNDataType 定义，当前是 int 类型，表示每个节点可以存储一个整数。
next 是一个指向下一个 SListNode 结构体的指针。它用于链接链表中的节点，使得可以从一个节点遍历到下一个节点。如果 next 为 NULL，则表示当前节点是链表的末尾。
链表的打印
我们定义了一个函数，它的作用是打印出一个单链表的所有节点值
void SLTPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL"); printf("\n"); }
我们来解析这个函数：
首先，函数内部定义了一个指针 cur 并将它初始化为指向链表的头节点 phead。这个指针用于遍历链表。
接着，函数进入一个 while 循环，条件是 cur != NULL，即只要 cur 指向的节点不是 NULL，循环就继续执行。这确保了函数能够遍历链表直到最后一个节点。
在循环体内，使用 printf 函数打印当前节点 cur 存储的整数值 cur->val，后面跟着一个箭头 ->，指示链表中的节点是如何连接的。
然后，cur 被更新为指向下一个节点 cur->next，准备打印下一个节点的值。这个步骤使得遍历可以继续进行。
一旦遍历完成（即 cur 为 NULL），循环结束。此时打印 “NULL” 来表示链表的结束
在后续我们会展示出来
创造节点
我们定义一个函数 CreatNode，用于创建一个新的链表节点 SLNode；
SLNode* CreatNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; return newnode; }
CreatNode 函数的目的是为了构造一个新的链表节点，并将其初始化。它接收一个参数 x，类型为 SLNDataType，这是链表节点存储数据的类型。函数的返回类型是 SLNode*，即新创建的链表节点的指针。我们来解析这个函数
通过调用 malloc(sizeof(SLNode)) 分配足够的内存来存储一个 SLNode 结构体实- 例。malloc 函数尝试分配指定大小的内存空间，并返回指向这块内存的指针。如果分配成功，这个指针指向的是新分配的内存；如果失败，则返回 NULL。
**初始化节点：**为新节点的 val 成员赋值参数 x，这表示节点存储的数据。将 next 成员设置为 NULL，表示新节点当前没有指向下一个节点
返回新节点：函数返回新创建的节点的指针，允许调用者将该节点添加到链表中的适当位置。
这个 CreatNode 函数用于创建并初始化链表的新节点。通过接收一个数据作为参数，并返回指向新分配和初始化的节点的指针，它为链表构造、数据插入等提供了基础。
单链表的尾插和头插
尾插
首先进行思考，我们能否这样定义函数？
void SLTPushBack(SLNode* pphead, SLNDataType x);
如果链表不为空，我们可以如下找到尾部
SLNode* newnode = CreatNode(x); SLNode* tail = pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode;
这里并没有对头指针进行任何的修改
如果链表为空，意味着我们需要将头指针指向空改为指向newnode，
我们想对一个数值通过函数修改，需要指针，那么对一个指针进行修改，则需要二级指针
所以函数定义如下：
void SLTPushBack(SLNode** pphead, SLNDataType x) { SLNode* newnode = CreatNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
这里，如果链表为空，插入新节点，则头指针发生了改变
我们再test文件中进行测试，创建并初始化头指针plist
尾插三次，插入1 2 3并打印，结果如下
头插
头插我们会改变头指针，也需要二级指针
1. void SLTPushFront(SLNode** pphead, SLNDataType x) 2. { 3. 4. SLNode* newnode = CreatNode(x); 5. newnode->next = *pphead; 6. *pphead = newnode; 7. } 8.
我们用pphead接收plist
newnode的指针next指向d1，即plist（*pphead）newnode->next = *pphead;，再让plist（*pphead）指向newnode。*pphead = newnode;
在这里，链表为空也无所谓，newnode指向NULL，plist指向newnode
测试如下
单链表的尾删和头删
尾删
void SLTPopBack(SLNode** pphead) { if (*pphead == NULL) { return; } if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } SLNode* prev = *pphead; while (prev->next->next != NULL) { prev = prev->next; } free(prev->next); prev->next = NULL; }
如果头指针指向 NULL，即链表没有节点，函数将直接返回，因为没有节点可以删除。
if ((*pphead)->next == NULL) {：这一行检查链表是否只有一个节点。它通过检查头节点的 next 指针是否为 NULL 来实现。如果是这种情况，说明链表中只有一个节点。free(*pphead);：如果链表只有一个节点，这行代码释放这个节点占用的内存。
pphead = NULL;：由于最后一个节点已被删除，链表现在为空。因此，需要将头指针设置为 NULL。
如果有多个节点，这个 while 循环遍历链表，直到 prev 指向倒数第二个节点。条件 prev->next->next != NULL 确保了 prev 停在倒数第二个节点，因为倒数第二个节点的下一个节点（即最后一个节点）的 next 指针是 NULL。 free(prev->next);：释放最后一个节点占用的内存。此时，prev->next 指向最后一个节点。
prev->next = NULL;：将倒数第二个节点的 next 指针设置为 NULL，从而移除对最后一个节点的引用，更新链表的末尾
1. void SLTPopFront(SLNode** pphead) { 2. if (*pphead == NULL) { 3. return; 4. } 5. SLNode* temp = *pphead; 6. *pphead = (*pphead)->next; 7. free(temp); 8. }
如果链表为空，直接返回，如果不为空，temp和*pphead现在指向同一块空间，我们让头指针指向第二个节点，现在只有temp指向第一个节点，释放第一个节点的空间
测试代码
寻找某个节点
SLNode* SLTFind(SLNode* phead, SLNDataType x) { SLNode* current = phead; while (current != NULL) { if (current->val == x) { return current; } current = current->next; } return NULL; }
初始化一个名为 current 的指针，用于遍历链表
在循环体内，if (current->val == x) 检查当前节点的值是否为目标值 x,若当前节点的值不是目标值，则通过 current = current->next; 将 current 更新为下一个节点的指针，继续遍历链表。
在指定位置后面插入节点
void SLTInsertAfter(SLNode* pos, SLNDataType x) { if (pos == NULL) { return; } SLNode* newnode =CreatNode(x); newnode->next = pos->next; pos->next = newnode; }
首先检查pos是否为NULL，如果是，则不进行插入
若不为空，则让newnode指向pos原来指向的节点，pos指向newnode完成插入
测试如下，我们已经有了三个数据1 2 3，在2后面插入4
首先找到2节点的地址，再传入insert函数中即可
在指定位置前面插入节点
要在指定位置之前插入一个新节点，情况就稍微复杂一点，因为单向链表的节点只包含指向下一个节点的指针，没有指向前一个节点的指针。这意味着，要实现这一功能，你需要找到目标位置的前一个节点，然后在这个节点之后插入新节点。以下是实现这一功能的方法
void SLTInsertBefore(SLNode** phead, SLNode* pos, SLNDataType x) { if (*phead == NULL || pos == NULL || *phead == pos) { SLNode* newnode = CreatNode(x); if (*phead == pos) { newnode->next = *phead; *phead = newnode; } else { free(newnode); } return; } SLNode* current = *phead; while (current->next != NULL && current->next != pos) { current = current->next; } if (current->next != pos) { return; } SLNode* newnode = CreatNode(x); newnode->next = pos; current->next = newnode; }
首先检查链表是否为空，或者目标位置是否是链表的第一个节点
如果是第一个节点，则意味着头插
如果pos为NULL，表示在空链表中插入，或者pos不在链表中
将创建的newnode释放掉
if (*phead == NULL || pos == NULL || *phead == pos) { SLNode* newnode = CreatNode(x); if (*phead == pos) { newnode->next = *phead; *phead = newnode; } else { free(newnode); } return; }
寻找pos前的节点
SLNode* current = *phead; while (current->next != NULL && current->next != pos) { current = current->next; }
如果没有找到pos，则不执行插入
if (current->next != pos) { return; }
在pos前插入新节点
SLNode* newnode = CreatNode(x); newnode->next = pos; current->next = newnode; }
测试代码如下：在1 2 3的2前面插入4
首先找到2节点的地址再传入插入函数
在指定位置后面删除节点
void SLTEraseAfter(SLNode* pos) { if (pos == NULL || pos->next == NULL) { return; } SLNode* temp = pos->next; pos->next = temp->next; free(temp); }
首先检查pos是否为空或pos之后没有节点，因为如果 pos 是 NULL，则没有任何节点可操作；如果 pos->next 是 NULL，则 pos 是链表中的最后一个节点，没有节点需要被删除。
将**待删除的节点（pos->next）**的地址存储在一个临时变量中。
更新 pos->next 指针，使其指向待删除节点的下一个节点。
释放待删除节点的内存，以防止内存泄漏。
测试代码如下，删除1 2 3中2后面的数据
在指定位置前面删除节点
在单向链表中删除某个指定位置pos之前的节点比删除其之后的节点稍微复杂，因为链表的单向性质意味着不能直接访问前驱节点。为了删除给定pos之前的一个节点，我们首先需要找到这个节点的前两个节点（即要删除的节点的前驱节点和要删除的节点）。然后，通过调整前驱节点的next指针，绕过要删除的节点，最后释放要删除的节点的内存。
1. void SLTEraseBefore(SLNode** phead, SLNode* pos) { 2. 3. if (*phead == NULL || pos == NULL || *phead == pos) return; 4. 5. if ((*phead)->next == pos) { 6. SLNode* temp = *phead; 7. *phead = (*phead)->next; 8. free(temp); 9. return; 10. } 11. SLNode* prev = NULL; 12. SLNode* current = *phead; 13. while (current != NULL && current->next != pos) { 14. prev = current; 15. current = current->next; 16. } 17. if (current == NULL || current->next != pos) return; 18. if (prev != NULL) { 19. prev->next = current->next; 20. free(current); 21. } 22. }
如果链表为空，pos为空，或pos是链表的第一个节点，无法删除前一个节点
if (*phead == NULL || pos == NULL || *phead == pos) return; 1 if ((*phead)->next == pos) { SLNode* temp = *phead; *phead = (*phead)->next; // 移动头指针 free(temp); return; }
这段代码的目的是处理一个特殊的情况：当我们想要删除位于给定pos节点之前的节点，且该pos恰好是链表的第二个节点时。下面分步解释这个代码块的含义和作用：
条件检查 (if ((*phead)->next == pos)): 这个条件检查链表的头节点（*phead）的下一个节点是否就是我们的目标位置pos。如果是，这意味着我们需要删除链表的第一个节点（即头节点），因为我们想要删除的是位于pos之前的节点，且pos是链表的第二个节点。
删除头节点:
SLNode* temp = *phead;：首先，我们将头节点（要删除的节点）的地址保存在临时变量temp中，以便之后能够安全地释放该节点占用的内存。
*phead = (*phead)->next;：接着，我们将头指针（*phead）向前移动到下一个节点，这实际上是在更新链表的头节点为原头节点的下一个节点。简单来说，我们就是把头指针指向了链表的第二个节点，从而在逻辑上“删除”了原来的第一个节点（头节点）。
释放内存 (free(temp);: 最后，使用free(temp);来释放原头节点占用的内存。
SLNode* prev = NULL; SLNode* current = *phead; while (current != NULL && current->next != pos) { prev = current; current = current->next; }
找到pos之前的节点
if (current == NULL || current->next != pos) return; 1 无法找到有效的pos位置，pos不在列表中，则返回 if (prev != NULL) { prev->next = current->next; free(current); }
删除current的节点，即pos之前的节点；
测试代码如下，删除1 2 3中2前面的节点
本节内容到此结束，感谢大家观看！
