前言
引入链表：顺序表的问题及思考与讨论
优势：
- 可通过 下标i （数据连续（物理空间连续）） 便捷查询查找顺序表中的信息，也会在后面的 排序算法 和 堆算法 中尽显身手
问题：
- 在头部/中间的插入与删除需要挪动数据，时间复杂度为O(N)，效率低；
- 增容需要申请新空间，可能会拷贝数据，释放旧空间，会有不小的消耗；
- 增容一般是呈 1.5倍 或 2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，如果我们再继续插入了5个数据，后面没有数据插入了，那么会浪费95个数据空间；
正因顺序表的这些不足，我们设计出了链表。
一、链表
1、链表的概念及结构
1.1 概念
- 链表 是一种 物理存储结构 上 非连续、非顺序 的存储结构，
- 数据元素的逻辑顺序是通过 链表中的 指针链接 次序 实现的 。
[注： 所谓的逻辑结构指的是数据在逻辑上是如何存储的，这是由人们主观想象出来的；而物理结构则是数据在物理内存中实际存储的方式，不随人们的主观意志而改变。]
带大家感受一下链表；
链表就如同图中的火车：
plist = 火车头，指向第一个节点
每个节点 = 每一节的火车车厢
每一节点中存储的下一节点的指针 =火车车厢之间的链接
实际上链表的每一个节点都是在堆区上随机申请的，前一个节点的地址可能比后一个节点大，也可能比后一个节点小，二者之前其实并没有物理结构上的关系。
链表的结构也可以这样
★☆★ 总结
注意：
- 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
- 现实中的结点一般都是从堆上申请出来的 （malloc）
- 从堆上申请的空间，是按照一定的策路来分配的，两次申清的空同可能连续，也可能不连续
链表和顺序表的 不同之处 在于：
顺序表不仅要求逻辑结构上连续，还要求物理结构上也连续；而链表只要求逻辑结构上连续，物理结构上可以不连续；正因为链表是用 指针 相连的特性。
2、链表的分类
- 单向/双向
双向链表对比单向链表来说，其结构体中会多一个结构体指针变量，用来指向前一个节点的地址。
- 带头/不带头
带头（哨兵位）最开始的时候会有一个节点，这个节点不用来存储数据，仅仅作为链表的头部使用，还是一个节点都没有。
- 循环/不循环
非循环链表的最后一个节点的next指向NULL，而循环链表的最后一个节点的next指向链表的第一个节点。
3. 最常用的两种链表
虽然链表有这么多中结构，但是我们实际中最常用还是以下两种结构：无头单向非循环链表 和 双向带头循环链表。
（1）无头单向非循环链表
结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等；另外这种结构在笔试面试中出现很多；其实如果不做特殊声明，一般情况下无头单向非循环链表指的就是我们的单链表；
（2）带头双向循环链表
结构最复杂，一般用于单独存储数据；实际中我们使用的链表数据结构，都是带头双向循环链表；另外它虽然结构复杂，但是使用代码实现后会有发现结构会带来多优势，所以反而是链表中使用起来最简单的。
二、单链表的实现
由于单链表是其他结构链表学习的基础，且经常被用做其他数据结构的子结构，在笔试题中也最常被考到，所以下面我们用C语言来手动实现一个单链表，以此来加深我们对单链表的理解。
（一）创建文件
- slist.h （单链表的类型定义、接口函数声明、引用的头文件)
- slist.c （单链表接口函数的实现）
- test.c （主函数、测试顺序表各个接口功能）
（二）slist.h
1、结构体类型声明
//类型声明 typedef int SLTDateType; //数据类型重命名 typedef struct SListNode { //结构体类型声明 SLTDateType data; struct SListNode* next; //结构体指针-存放下一节点（结构体）的地址 }SListNode;
（三）slist.c
注解都标注在代码旁边，方便大家边看代码边理解
2、动态创建新节点
//动态创建新节点 SListNode* BuySListNode(SLTDateType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); assert(malloc); //避免malloc失败返回的空指针NULL，并及时报错 newNode->data = x; newNode->next = NULL; return newNode; }
3、在头部插入数据
//单链表的头插 void SListPushFront(SListNode** pphead, SLTDateType x) { assert(pphead); //确保传过来的不是空指针 SListNode* newNode = BuySListNode(x); //指针变量中存放的是指针（地址） //链表为空 直接存放newNode的地址 在 解引用头指针处得到的内容处 //图解 if (*pphead == NULL) { *pphead = newNode; return; } //链表不为空 //图解 SListNode* temp = *pphead; //先将头指针中 所指向的节点地址，先暂时保存 *pphead = newNode; //把新节点地址存入头指针中，形成新连接 newNode->next = temp; //在把暂存的原后链接的地址，放入到新节点newNode中的 结构体指针中， //再形成新的后链接 }
4、在尾部插入数据
//单链表的尾插 void SListPushBack(SListNode** pphead, SLTDateType x) { assert(pphead); //确保传过来的不是空指针 SListNode* newNode = BuySListNode(x); //指针变量中存放的是指针（地址） //链表为空 直接存放newNode的地址 在 解引用头指针处得到的内容处 //图解 if (*pphead == NULL) { *pphead = newNode; return; } //链表不为空 我们需要找到链尾 SListNode* tail = *pphead; //创建个结构体指针遍历链表， while (tail->next != NULL) { tail = tail->next; } //找到最后为空的结构体，将其newNode地址插入该末尾结构体 tail->next = newNode; }
5、查找数据
// 查找数据——单链表查找 SListNode* SListFind(SListNode* pphead, SListDateType x) { assert(pphead); SListNode* cur = pphead; while (cur != NULL) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
6、在pos位置前插入数据
//在pos位置前插入数据 void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x) { assert(pphead); assert(pos); if (pos == *pphead) //如果pos等于*pphead，相当于头插 { SListPushFront(pphead, x); return; } SListNode* newNode = BuySLTNode(x); //找到pos位置的前一个节点 SListNode* prev = *pphead; while (prev->next != pos) { assert(prev); //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错 prev = prev->next; } prev->next = newNode; newNode->next = pos; }
7、在pos位置后插入数据
思考：为什么不在pos位置之前插入？
由于单链表在某一节点的前面插入数据时需要从头遍历寻找该节点的前一个节点， 导致时间复杂度为O(N)，
所以人们为了提高单链表的效率，为单链表单独设计了在pos位置后插入数据的函数；除了单链表，其他数据结构插入数据都是在前面插入。
// 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* next = pos->next; SListNode* newNode = BuySListNode(x); newNode->next = next; pos->next = newNode; }
8、在头部删除数据
// 单链表头删 void SListPopFront(SListNode** pphead) { SListNode* temp = *pphead; if (temp == NULL) { //先判断链表中是否还有数据可被删除 printf("链表中无数据可删除\n"); return; } *pphead = temp->next; //图解 free(temp); //用个临时变量 记住要free掉的节点的地址 temp = NULL; //记住后就可以放心大胆的将其后一个节点的地址传给头指针中， //这样就不怕要free掉的节点的地址被覆盖而找不到该地址 }
9、在尾部删除数据
// 单链表的尾删 void SListPopBack(SListNode** pphead) { SListNode* temp = *pphead; //由于后面还会用到头指针中所存储的下一节点的地址， //所以干脆直接解引用拿出得到头指针中所存储的下一节点的地址，并用SListNode*保存 //（而不是SListNode** temp存储pphead的地址， //后面还要解引用*temp才能得到pphead中存储的（头指针中所存储的下一节点的地址， //*temp虽说也是指针，但 `*temp->` 这样的格式编译器是不允许的不成立的）） // =>所以还是直接解引用的好 if (temp == NULL) { //先判断链表中是否还有数据可被删除 printf("链表中无数据可删除\n"); return; } while (temp->next->next != NULL) { //要删除最后一个节点，当然要找到的是它前一个节点的地址 // [ 因为前一个节点的结构体中存有最后一个节点结构体的地址 ]（没有前一个节点的地址根本无法找到） temp = temp->next; //当然没有前一个节点，最后那个节点遍历到temp->next=NULL， //temp也能遍历到最后那个节点的地址，并将其free掉，但前一个地址的next也要重新设为空指针NULL， //（就算再遍历一遍链表，结尾不为NULL，也再也找不到现在的最后一个节点了 //（因为无法让遍历碰到现在的新最后一个节点停下）， //那么也将无法删除最后一个节点后 的新的最后一个节点中的next置为NULL） } SListNode* temp1 = temp->next; //free掉最后一个节点 free(temp1); temp1 = NULL; //记得要置回NULL空指针，避免变成野指针，很危险 temp->next = NULL; //将前一个节点的指针置为NULL }
10、删除pos位置前的数据
//删除pos位置前的数据 void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead && pos); assert(*pphead); //当链表为空时，删除元素报错 if (pos == *pphead) //pos等于*pphead时相当于头删 { SListPopFront(pphead); return; } //找到pos的前一个节点 SListNode* prev = *pphead; while (prev->next != pos) { assert(prev); //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错 prev = prev->next; } SListNode* tmp = pos->next; prev->next = tmp; free(pos); pos = NULL; }
11、删除pos位置后的数据
思考：为什么不删除pos位置？
和在pos位置后插入数据一样，为了提高效率，人们也设计了一个在pos位置后删除数据的函数。
// 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos) { assert(pos); //确保指针不为空 if (pos->next != NULL) { SListNode* next = pos->next->next; SListNode* temp = pos->next; free(temp); temp = NULL; pos->next = next; } }
12、修改pos位置处的数据
//修改pos位置处的数据 void SListModify(SLTNode* phead, SLTNode* pos, SLTDataType x) { assert(phead && pos); SListNode* cur = phead; while (cur != pos) { assert(cur); //如果cur为空循环还没停止，说明在链表中找不到pos，直接报错 cur = cur->next; } cur->data = x; }
13、打印链表中的数据
//打印链表 递归实现 void SListPrint(SListNode* pList) { printf("%d ", pList->data); SListPrint(pList->next); }
14、销毁链表
// 单链表的销毁 void SListDestroy(SListNode* pphead) { //pphead的内存空间也要销毁 assert(pphead); SListNode* cur = pphead; while (cur != NULL) { SListNode* temp = cur->next; //用个临时变量先存着后一个节点的地址, //以免free掉现在的地址后，找不到后面的地址了 free(cur); cur = temp; //再重新找回来 } }
三、完整代码
1、SList.h
#pragma once //防止头文件重复包含 //头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> //类型声明 typedef int SLTDateType; //数据类型重命名 typedef struct SListNode { //结构体类型声明 SLTDateType data; struct SListNode* next; //结构体指针-存放下一节点（结构体）的地址 }SListNode; //函数声明 //创建新建节点 SListNode* BuySLTNode(SLTDateType x); //在头部插入数据 void SListPushFront(SListNode** pphead, SLTDateType x); //销毁链表 void SListDestory(SListNode** pphead); //在尾部插入数据 void SListPushBack(SListNode** pphead, SLTDateType x); //查找数据 SListNode* SListFind(SListNode* phead, SLTDateType x); //在pos之前插入数据 void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x); //在pos之后插入数据 void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDateType x); //打印链表 void SListPrint(SListNode* phead); //在头部删除数据 void SListPopFront(SListNode** pphead); //在尾部删除数据 void SListPopBack(SListNode** pphead); //删除pos位置处的数据 void SListErase(SListNode** pphead, SListNode* pos); //删除pos位置后的数据 void SListEraseAfter(SListNode** pphead, SListNode* pos); //修改pos位置处的函数 void SListModify(SListNode* phead, SListNode* pos, SLTDateType x);
2、SList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"slist.h" //动态创建新节点 SListNode* BuySListNode(SLTDateType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); assert(malloc); //避免malloc失败返回的空指针NULL，并及时报错 newNode->data = x; newNode->next = NULL; return newNode; } // 单链表的头插 void SListPushFront(SListNode** pphead, SLTDateType x) { assert(pphead); //确保传过来的不是空指针 SListNode* newNode = BuySListNode(x); //指针变量中存放的是指针（地址） //链表为空 直接存放newNode的地址 在 解引用头指针处得到的内容处 //图解 if (*pphead == NULL) { *pphead = newNode; return; } //链表不为空 //图解 SListNode* temp = *pphead; //先将头指针中 所指向的节点地址，先暂时保存 *pphead = newNode; //把新节点地址存入头指针中，形成新连接 newNode->next = temp; //在把暂存的原后链接的地址，放入到新节点newNode中的 结构体指针中， //再形成新的后链接 } //单链表的尾插 void SListPushBack(SListNode** pphead, SLTDateType x) { assert(pphead); //确保传过来的不是空指针 SListNode* newNode = BuySListNode(x); //指针变量中存放的是指针（地址） //链表为空 直接存放newNode的地址 在 解引用头指针处得到的内容处 //图解 if (*pphead == NULL) { *pphead = newNode; return; } //链表不为空 我们需要找到链尾 SListNode* tail = *pphead; //创建个结构体指针遍历链表， while (tail->next != NULL) { tail = tail->next; //找到最后为空的结构体，将其newNode地址插入该末尾结构体 } tail->next = newNode; } // 查找数据——单链表查找 SListNode* SListFind(SListNode* pphead, SLTDateType x) { assert(pphead); SListNode* cur = pphead; while (cur != NULL) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } // 单链表在pos位置之后插入x // 分析思考为什么不在pos位置之前插入？ // // 由于单链表在某一节点的前面插入数据时需要从头遍历寻找该节点的前一个节点， // 导致时间复杂度为O(N)，所以人们为了提高单链表的效率， // 为单链表单独设计了在pos位置后插入数据的函数； // 除了单链表，其他数据结构插入数据都是在前面插入。 void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* next = pos->next; SListNode* newNode = BuySListNode(x); newNode->next = next; pos->next = newNode; } //在pos位置前插入数据 void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x) { assert(pphead); assert(pos); if (pos == *pphead) //如果pos等于*pphead，相当于头插 { SListPushFront(pphead, x); return; } SListNode* newNode = BuySLTNode(x); //找到pos位置的前一个节点 SListNode* prev = *pphead; while (prev->next != pos) { assert(prev); //如果prev为空循环还没停止，说明在链表中找不到pos，直接报错 prev = prev->next; } prev->next = newNode; newNode->next = pos; } // 单链表删除pos位置之后的值 // 分析思考为什么不删除pos位置？ //和在pos位置后插入数据一样，为了提高效率，人们也设计了一个在pos位置后删除数据的函数。 void SListEraseAfter(SListNode* pos) { assert(pos); //确保指针不为空 if (pos->next != NULL) { SListNode* next = pos->next->next; SListNode* temp = pos->next; free(temp); temp = NULL; pos->next = next; } } //修改pos位置处的数据 void SListModify(SListNode* phead, SListNode* pos, SLTDateType x) { assert(phead && pos); SListNode* cur = phead; while (cur != pos) { assert(cur); //如果cur为空循环还没停止，说明在链表中找不到pos，直接报错 cur = cur->next; } cur->data = x; } // 单链表头删 void SListPopFront(SListNode** pphead) { SListNode* temp = *pphead; if (temp == NULL) { //先判断链表中是否还有数据可被删除 printf("链表中无数据可删除\n"); return; } *pphead = temp->next; //图解 free(temp); //用个临时变量 记住要free掉的节点的地址 temp = NULL; //记住后就可以放心大胆的将其后一个节点的地址传给头指针中， //这样就不怕要free掉的节点的地址被覆盖而找不到该地址 } // 单链表的尾删 void SListPopBack(SListNode** pphead) { SListNode* temp = *pphead; //由于后面还会用到头指针中所存储的下一节点的地址， //所以干脆直接解引用拿出得到头指针中所存储的下一节点的地址，并用SListNode*保存 //（而不是SListNode** temp存储pphead的地址， //后面还要解引用*temp才能得到pphead中存储的（头指针中所存储的下一节点的地址， //*temp虽说也是指针，但 `*temp->` 这样的格式编译器是不允许的不成立的）） // =>所以还是直接解引用的好 if (temp == NULL) { //先判断链表中是否还有数据可被删除 printf("链表中无数据可删除\n"); return; } while (temp->next->next != NULL) { //要删除最后一个节点，当然要找到的是它前一个节点的地址 // [ 因为前一个节点的结构体中存有最后一个节点结构体的地址 ]（没有前一个节点的地址根本无法找到） temp = temp->next; //当然没有前一个节点，最后那个节点遍历到temp->next=NULL， //temp也能遍历到最后那个节点的地址，并将其free掉，但前一个地址的next也要重新设为空指针NULL， //（就算再遍历一遍链表，结尾不为NULL，也再也找不到现在的最后一个节点了 //（因为无法让遍历碰到现在的新最后一个节点停下）， //那么也将无法删除最后一个节点后 的新的最后一个节点中的next置为NULL） } SListNode* temp1 = temp->next; //free掉最后一个节点 free(temp1); temp1 = NULL; //记得要置回NULL空指针，避免变成野指针，很危险 temp->next = NULL; //将前一个节点的指针置为NULL } //打印链表 递归实现 void SListPrint(SListNode* pList) { printf("%d ", pList->data); SListPrint(pList->next); } // 单链表的销毁 void SListDestroy(SListNode* pphead) { //pphead的内存空间也要销毁 assert(pphead); SListNode* cur = pphead; while (cur != NULL) { SListNode* temp = cur->next; //用个临时变量先存着后一个节点的地址, //以免free掉现在的地址后，找不到后面的地址了 free(cur); cur = temp; //再重新找回来 } } int main() { test1(); //test2（） //test3（） return 0; }
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" void test1() //测试插入 { SListNode* plist = NULL; //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL； //头插 SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPrint(plist); //尾插 SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist); //在pos位置前插入 SListNode* pos = SListFind(plist, 5); if (pos != NULL) { SListInsert(&plist, pos, 50); } pos = SListFind(plist, 3); if (pos != NULL) { SListInsert(&plist, pos, 30); } SListPrint(plist); pos = SListFind(plist, 6); if (pos != NULL) { SListInsert(&plist, pos, 60); } SListPrint(plist); //在pos位置后插入 pos = SListFind(plist, 1); if (pos != NULL) { SListInsertAfter(&plist, pos, 10); } pos = SListFind(plist, 3); if (pos != NULL) { SListInsertAfter(&plist, pos, 30); } SListPrint(plist); //销毁 SListDestory(&plist); } void test2() //测试删除 { SListNode* plist = NULL; //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL； //头插 SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPrint(plist); //在头部删除数据 //SListPopFront(&plist); //SListPopFront(&plist); //SListPopFront(&plist); //SListPrint(plist); //在尾部删除数据 //SListPopBack(&plist); //SListPopBack(&plist); //SListPopBack(&plist); //SListPrint(plist); //删除pos位置处的数据 //SLTNode* pos = SListFind(plist, 1); //if (pos != NULL) //{ // SListErase(&plist, pos); //} //pos = SListFind(plist, 3); //if (pos != NULL) //{ // SListErase(&plist, pos); //} //SListPrint(plist); //pos = SListFind(plist, 2); //if (pos != NULL) //{ // SListErase(&plist, pos); //} //SListPrint(plist); //删除pos位置后的数据 SListNode* pos = SListFind(plist, 2); if (pos != NULL) { SListEraseAfter(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 3); if (pos != NULL) { SListEraseAfter(&plist, pos); } SListPrint(plist); //销毁 SListDestory(&plist); } void test3() //测试查和改 { SListNode* plist = NULL; //指向链表第一个节点的指针，因为链表没有节点，所以初始化为NULL； //头插 SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPrint(plist); //查找并修改pos位置处的数据 SListNode* pos = SListFind(plist, 3); if (pos != NULL) { SListModify(plist, pos, 30); } SListPrint(plist); pos = SListFind(plist, 1); if (pos != NULL) { SListModify(plist, pos, 10); } SListPrint(plist); //销毁 SListDestory(&plist); }
