数据结构-单链表-详解-2
1.前言
在数据结构-单链表-详解-1中，我们不仅了解了单链表的基本概念，还掌握了如何创建和打印单链表。
今天，我将详细讲解如何对单链表进行头尾部的插入、删除。
2.创建新结点
在后续插入的过程中，都需要创建新的结点，因此直接将该过程封装为一个函数，便于操作。
SList.c：
SListNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("BuySListNode::malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
这段代码定义了一个名为BuySListNode的函数，它接受一个数据值作为参数，并返回一个新的链表结点。函数首先使用malloc来分配内存，然后初始化结点的数据成员和指向下一个结点的指针。
3.头插与尾插
链表的一个重要特性是可以在任意位置插入新元素，这使得链表非常适合动态数据集合的处理。
下面我将分别介绍如何实现头插和尾插操作。
3.1头插
- 链表不为空：
- 链表为空：
可以发现，头插时，链表为不为空操作相同。
SList.h：
void SListPushFront(SListNode** pphead, SLTDataType x);
SList.c：
void SListPushFront(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
这段代码定义了一个名为SListPushFront的函数，它接受指向链表头结点的二级指针和一个数据值作为参数。
首先，调用CreateSLTNode来创建一个新结点，并将其next指针设置为原来的头结点。
最后，更新头指针使其指向新结点。
现在可以测试一下：
test.c:
void TestSList1()
{
SListNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
}
int main()
{
TestSList1();
return 0;
}
运行结果：
3.2尾插
空链表
在尾插中，如果链表为空，则需改变头指针，因此，我们传入二级指针。
SList.h：
void SListPushBack(SListNode** pphead, SLTDataType x);
SList.c：
void SListPushBack(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySlistNode(x);
*pphead = newnode;
}
找尾
SListNode* tail = *pphead;
尾插的实现比头插更复杂，想要在尾部插入数据，首先得找到尾部。
错误写法：
while (tail != NULL)
{
tail = tail->next;
}
tail = newnode;
分析一下，循环的结束条件是tail等于NULL，而下一步则把新结点赋值给了NULL，因此错误。
链表的链接是让上一个结点有下一个结点的地址，因此，尾插的本质是：原尾结点中要存储新尾结点的地址。
完整写法：
SList.c：
void SListPushBack(SListNode** pplist, SLTDataType x)
{
SListNode* newnode = BuySlistNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
这段代码首先创建一个新结点。
如果链表为空，则直接插入新结点并更新头指针。
否则，初始化一个指针tail从头结点开始，并遍历链表直到找到最后一个结点。
最后，将新结点插入到链表的尾部。
4.头删与尾删
删除的条件是链表不为空，因此该处的函数开头应该assert断言。
4.1头删
两个以上的结点：
一个结点：
SList.h：
void SListPopFront(SListNode** pphead);
SList.c：
void SListPopFront(SListNode** pphead)
{
assert(*pphead);
SListNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
这段代码定义了一个名为SListPopFront的函数，它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空，然后保存当前的头结点，并更新头指针使其指向下一个结点。
最后，释放原来头结点占用的内存，并将指针设为NULL以避免野指针。
4.2尾删
- 单个结点：
同头删 - 多个结点：
由于需要删除的是最后一个结点，因此，找尾时应该找倒数第二个结点。
SList.h：
void SListPopBack(SListNode** pphead);
SList.c：
void SListPopBack(SListNode** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
这段代码定义了一个名为SListPopBack的函数，它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空。
如果链表只有一个结点，则直接释放该结点并更新头指针。
否则，初始化一个指针tail从头结点开始，并遍历链表直到找到倒数第二个结点。
最后，释放尾结点占用的内存，并更新倒数第二个结点的next指针使其指向NULL。
现在可以测试一下：
test.c:
void TestSList3()
{
SListNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopBack(&plist);
SListPrint(plist);
}
运行结果：
通过以上的介绍和代码实现，我们掌握了如何对单链表进行头尾部的插入、删除。希望这些内容能帮助你更好地理解单链表，并激发你进一步探索数据结构的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！