数据结构-单链表-详解-2

本文主要是介绍数据结构-单链表-详解-2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构-单链表-详解-2

1.前言
2.创建新结点
3.头插与尾插
- 3.1头插
- 3.2尾插
- - 空链表
  - 找尾
4.头删与尾删
- 4.1头删
- 4.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);
}