深入理解顺序表（SeqList）

一、 链表介绍

1.1、 为什么引入链表

• 学习链表之前，先让我们来思考一个问题：

为什么有了顺序表，还需要有链表这样的数据结构呢？

• 顺序表存在的一些问题：

1. 顺序表在中间/头部的插入删除，要挪动很多数据，时间复杂度为O(N)，效率太低了。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是一次增长2倍，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
   再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间SeqList。

• 为了更好的解决上述问题，引入了链表。

1.2、 链表的概念及结构

• 概念

前面学习的顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，而链表是一种物理存储结构上不连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，可以实现更加灵活的动态内存管理。

• 链表的组成

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

1、数据域：存储数据元素

2、指针域：存储下一个结点地址

• 链表的物理结构

可以看到，4个节点的地址并不是连续的，链表在物理结构上不一定是线性的，而在逻辑结构上是线性的

• 链表的逻辑结构（想象出来的）

• 注意

1、链式结构在逻辑上是连续的，但在物理上不一定连续

2、链表的节点是在堆上申请出来的

1.3、 链表的分类

链表的结构非常多样化

• 单向、双向

• 带头结点、不带头节点（哨兵位的头节点，不存储有效数据）

• 非循环、循环

• 常用的两种结构

二、 无头单向非循环链表的实现

2.1、 单链表的定义

typedef int SLTDataType;//定义单链表节点
typedef struct SListNode
{SLTDataType data;        //数据域struct SListNode* next;  //指针域
}SLTNode;

2.2、 动态申请一个节点

//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL)  //检查是否开辟成功{perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

2.3、 销毁（释放）所有节点

//销毁单链表中所有节点
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur != NULL)  //遍历链表{SLTNode* next = cur->next;  //保存cur的下一个节点free(cur);  //释放节点cur = next;}*pphead = NULL;  //z
}

• 作用：

销毁单链表中所有节点，指向头节点的指针置空，防止内存泄露等问题

2.4、 打印单链表

//打印单链表
void SLTPrint(SLTNode* phead)
{SLTNode* ptr = phead;while (ptr != NULL){printf("%d->", ptr->data);ptr = ptr->next;}printf("NULL\n");
}

2.5、 单链表尾插

• 先来看一种错误写法：这个也是弄懂单链表的关键

传一级指针的值，用一级指针接收

• 这种写法会导致一个问题：

因为当链表为空时，我们需要改变 plist 的指向，使其指向第一个节点。

而初始 plist 和 phead 都指向 NULL，调用函数后，phead 指向了新的节点，而 plist 还是指向 NULL 的。

• 如何解决呢：

plist 是指向第一个节点的指针，想要在函数中改变 plist 的值（指向），必须要把 plist指针的地址 作为实参传过去，形参用 二级指针 接收，这样在函数中对二级指针解引用得到 plist 的值，就可以改变 plist 的值（指向）了

记住：在函数里面要改变 int，则要传 int* ，要改变 int* ，则要传 int**

• 注意区分开这几个代表的意思哦

平时一般不用解引用两层，没啥意义，一般是解引用一层，来改变外面 plist 的指向。

• **正确写法：**通过二级指针改变外面 plist 的指向

单链表为空时，plist 直接指向新节点；

单链表不为空时，先找到单链表的尾节点，然后将尾节点的next指向新节点

//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);  //检查参数是否传错SLTNode* newnode = BuySListNode(x);  //动态申请一个节点if (*pphead == NULL)  //单链表中没有节点时{*pphead = newnode;  //plist指向新节点}else if (*pphead != NULL)  //单链表中已经有节点时{SLTNode* tail = *pphead;while (tail->next != NULL)  //找到单链表中的最后一个节点{tail = tail->next;}tail->next = newnode;  //最后一个节点的next指向新节点}
}

• 运行结果如下：

2.6、 单链表头插

• 图解头插操作

• 代码如下

因为要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址

//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);  //检查参数是否传错SLTNode* newnode = BuySListNode(x);  //动态申请一个节点newnode->next = *pphead;  //新节点的next指针指向plist指向的位置*pphead = newnode;  //plist指向头插的新节点
}

• 运行结果如下：

2.7、 单链表尾删

• 图解尾删操作

• 代码如下

单链表只有一个节点时，删除节点，plist 指向 NULL；

单链表有多个节点时，先找到单链表尾节点的上一个节点，删除尾节点，然后将该节点的next指向 NULL；

因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

//单链表尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);   //检查参数是否传错assert(*pphead);  //断言，链表不能为空SLTNode* tail = *pphead;if ((*pphead)->next == NULL)  //链表只有一个节点{free(*pphead);   //删除节点*pphead = NULL;  //plist置空}else  //链表中有多个节点{while (tail->next->next != NULL)  //找到链表的尾节点的上一个节点{tail = tail->next;}free(tail->next);   //删除尾节点tail->next = NULL;  //置空/*思路2：SLTNode* prev = *pphead;while (tail->next)  //找到链表的尾节点和它的上一个节点{prev = tail;tail = tail->next;}free(tail);         //删除尾节点prev->next = NULL;  //置空*/}
}

• 运行结果如下：

2.8、 单链表头删

• 图解头删操作

• 代码如下

因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

//单链表头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);   //检查参数是否传错assert(*pphead);  //链表不能为空SLTNode* cur = *pphead;  //保存头节点的地址*pphead = cur->next;  //plist指向头节点的下一个节点free(cur);  //删除头节点
}

• 运行结果如下：

2.9、 在单链表中查找指定值的节点

如果查找到，返回该节点的地址；没有查找到，返回 NULL。

//在单链表中查找指定值节点
SListNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;//遍历链表while (cur != NULL){if (cur->data == x){return cur;  //找到了，返回该节点的地址}cur = cur->next;}return NULL;  //未找到，返回NULL
}

2.10、 单链表在pos位置之后插入

• 图解插入操作

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

单链表不适合在pos位置之前插入，因为需要遍历链表找到pos位置的前一个节点，

单链表更适合在pos位置之后插入，如果在后面插入，只需要知道pos位置就行，会简单很多

C++官方库里面单链表给的也是在之后插入

• 代码如下

//单链表在指定pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);  //给的pos位置不能为空SLTNode* newnode = BuySListNode(x);  //动态申请一个节点newnode->next = pos->next; //新节点的next指针指向pos位置后一个节点pos->next = newnode;       //pos位置的next指向新节点
}

• 作用：

先调用 SLTFind 函数在单链表中查找指定值的节点，查找到了，返回该节点的地址，也即是我们指定的 pos 位置，然后将其传给 SLTInsertAfter 函数。

2.11、 单链表删除指定pos位置的节点

• 图解删除操作

• 代码如下

要考虑到两种情况：pos位置为单链表的第一个节点，pos位置为中间节点；

因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

//单链表删除指定pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead); //链表不能为空assert(pos);     //给的pos位置不能为空//pos位置为第一个节点，相当于头删if (pos == *pphead){SLTPopFront(pphead);}//pos位置为中间节点else{SLTNode* prev = *pphead;while (prev->next != pos)  //找到pos位置的前一个节点{prev = prev->next;}prev->next = pos->next;  //pos位置的前一个节点指向pos位置的后一个节点free(pos);  //释放pos节点pos = NULL; //置空}
}

• 补充一下，assert 断言

assert 放在函数里面检查参数，一方面是为了安全，另一方面也是为了防止有人调用该函数时，不正确的使用，错误传入参数，好及时提醒到他，写代码时一定要考虑到有人不正确的使用该函数时的场景，来进行避免

• 测试其功能

先调用 SLTFind 函数在单链表中查找指定值的节点，查找到了，返回该节点的地址，也即是我们指定的 pos 位置，然后将其传给 SLTErase 函数。

2.12、 单链表删除指定pos位置之后的节点

• 图解删除操作

• 代码如下

//单链表删除指定pos位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);       //给的pos位置不能为空assert(pos->next); //给的pos位置不能是尾节点SLTNode*del = pos->next;  //保存pos位置的后一个节点pos->next = pos->next->next;free(del);  //释放pos位置的后一个节点del=NULL;
}

-运行结果如下：

2.13、 求单链表长度

//求单链表长度
int SLTSize(SLTNode* phead)
{int size = 0;SLTNode* cur = phead;while (cur != NULL)  //遍历链表{size++;cur = cur->next;}return size;
}

2.14、 判断单链表是否为空

plist为空，返回 1 (true)，非空，返回 0 (false)

//单链表判空
bool SLTEmpty(SLTNode* phead)
{//plist为空，返回1(true)，非空，返回0(false)return phead == NULL;/*写法2：return phead == NULL ? true : false;*/
}

三、 总结

单链表是一种简单且高效的数据结构，适用于需要频繁插入和删除操作的场景。通过掌握单链表的创建、插入、删除、查找、修改和遍历等操作，我们可以更好地理解和应用这一数据结构，从而提高程序的效率和可靠性。