💕十载寒窗无人问，一举成名天下知💕
作者：Mylvzi
文章主要内容：详解单链表
引言：
我们之前已经学习过顺序表，顺序表是一种线性的存储结构，它在内存中是连续存放的；我们不难发现，顺序表在管理数据时存在一些问题，如进行插入数据时需要挪动大量数据，异地扩容导致内存使用率低，存在大量内存碎片等等，那有没有一种存储方式可以实现“随用随开“的内存使用方式呢？存在，就是我们今天要学的-->链表
链表的基本知识：
链表是一种管理内存的数据结构，和顺序表一样，都是一种线性表；
单链表(Single List Table)的表示：
（指针域中只有一个地址，所以叫做单链表）
链表与顺序表的区别：
1.链表和顺序表最大的差距在于空间开辟的方式：
链表是有多少就开辟多少（精打细算）
顺序表是直接给你一大片空间，让你使用，不够用了，再给你一大片空间（任性父母）
2.顺序表的空间在内存中是连续的，而链表的空间是一个一个独立的小空间，不连续
单链表的创建：
前提准备：
//创建结构体存储单链表的基本信息（数据域 + 指针域）： typedef int SLDataType; //定义结点 typedef struct SListNode { SLDataType data;//数据域 struct SListNode* next;//指针域-->存放下一节点的地址 }SLTNode;//SLT-->single list table单链表
单链表的管理：
打印单链表：
逻辑：从头指针（phead）访问下一个结点，打印每个结点的数据域，再把下一个结点的地址给cur,一直到NULL;
//打印链表 void SLTPrint(SLTNode* phead); //打印链表逻辑 void SLTPrint(SLTNode* phead) { //assert(phead);err //断言不合理，因为phead可以是NULL,代表链表中无数据 //断不断言，要看的传的数据是否合理 SLTNode* cur = phead;//重新赋头指针 //while(cur != NULL) while (cur) { printf("%d->", cur->data); cur = cur->next; //++cur err 结点的存储在内存中不是连续的 } printf("NULL"); }
创建新结点：
逻辑：为新结点动态开辟内存空间，然后再对数据域指针域进行赋值
//创建一个新结点 SLTNode* BuySListNode(SLDataType x); //创建一个新结点 SLTNode* BuySListNode(SLDataType x)//要存储的数据为x { //为整个结点动态开辟空间 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL)//判断是否开辟成功 { perror("malloc"); exit(-1); } //初始化 newnode->data = x; newnode->next = NULL; }
尾插：
//尾插-->结点的本质是一种结构体指针，改变结构体指针需要传递结构体指针的地址（二级指针） void SLTPushBack(SLTNode** pphead, SLDataType x); //尾插-->结点的本质是一种结构体指针，改变结构体指针需要传递结构体指针的地址（二级指针） void SLTPushBack(SLTNode** pphead, SLDataType x) { assert(pphead);//pphead是plist的地址，永远不可能为空，所以要检查; //assert(*pphead);err 空链表可以尾插 //创建一个新结点作尾插用 SLTNode* newnode = BuySListNode(x); //进行尾插-->找到尾结点，使其next指向newnode if (*pphead == NULL) { //如果*phead本事就是NULL，则不存在NULL->next,直接将newnode赋给phead即可 *pphead = newnode; } else { //寻找到尾结点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
头插：
//头插 void SLTPushFront(SLTNode** pphead, SLDataType x); //头插 void SLTPushFront(SLTNode** pphead, SLDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); //头插-->注意顺序 newnode->next = *pphead; *pphead = newnode; // 这里改变了头结点，所以要用二级指针 //err //*pphead = newnode; //newnode->next = *pphead; }
注意到：头插和尾插的参数都是二级指针，原因在于你改变的是结点，结点本身就是一个结构体指针，改变结构体指针就要传递结构体指针的地址，即二级指针；在顺序表中，我们改变的是一个一个结构体 ，所以传递的是结构体指针
由于形参是实参的临时拷贝，出了函数作用域后会被自动销毁，要改变值，就要传递值的地址！
头插，尾插都要检查pphead,但不用检查*pphead，因为NULL也能插入数据
尾删：
//尾删 void SLTPopBack(SLTNode** pphead); //尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead);//pphead为空，不合理 //1.*pphead == NULL 如果是NULL,属于非法删除 assert(*pphead); //2.只有一个节点 if ((*pphead)->next == NULL)//注意：由于存在优先级问题，*pphead需要添加括号 { free(*pphead); *pphead = NULL; } else//不止一个结点 { //第一种写法 SLTNode* tail = *pphead; //while (tail->next->next != NULL) while (tail->next->next)//在倒数第二个结点停止（因为你需要删除最后一个结点） { tail = tail->next; } free(tail->next); tail->next = NULL; } 第二种写法：双指针法 // SLTNode* tailPrev = NULL;//tail结点的上一个结点 // SLTNode* tail = *pphead; // while (tail->next) // { // tailPrev = tail; // tail = tail->next; // } // free(tail); // tail = NULL; // //tailPrev->next = NULL; }
注意尾删有三种情况
头删：
//头删 void SLTPopFront(SLTNode** pphead); //头删 void SLTPopFront(SLTNode** pphead) { assert(pphead); //1.空 assert(*pphead); //2.非空 SLTNode* newhead = (*pphead)->next;//使第二个结点作为头结点 free(*pphead); *pphead = newhead;//这里不是置空，而是置换新结点为头结点 }
寻找结点：
根据输入的值，找到对应的结点
//寻找数据为x的结点 SLTNode* SLTFind(SLTNode* phead, SLDataType x); SLTNode* SLTFind(SLTNode* phead, SLDataType x) { assert(phead); SLTNode* cur = phead;//遍历尽量多定义一个变量 while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } //出循环，遍历到NULL return NULL; }
在pos之前插入x：
逻辑：找到pos之前的prev结点，改变指针域
// 在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x); // 在pos之前插入x-->单链表前插效率不高 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x) { assert(*pphead); //pos是*pphead-->头插 if (pos == *pphead) { SLTPushFront(pphead, x);//头插函数的第一个参数是plist的地址，是二级指针 } else { //找到pos之前的结点prev SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } }
在pos之后插入x：
逻辑：找到pos,改变指针域（去观察什么数据发生了改变）
// 在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLDataType x); // 在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLDataType x) { assert(pos);//防止传错 //插入逻辑 SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
删除pos位置的结点：
逻辑：找到prev,改变指针域，free（pos）
// 删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(*pphead); assert(pos); //头指针-->头删 if (pos == *pphead) { SLTPopFront(pphead); } else { //找到prev SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
删除pos的后一个位置的结点：
逻辑：找到posNext，改变指针域，free(posNext);
// 删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos); // 删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next);//检查pos是否是尾节点 SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; }
删除整个链表：
逻辑：依次free,最后置空
//删除链表 void SLTDestroy(SLTNode** pphead); //删除链表 void SLTDestroy(SLTNode** pphead) { assert(pphead); //逻辑：一个一个释放，同时要能找到下一个结点 SLTNode* cur = *pphead; //循环删除 while (cur) { SLTNode* next = cur->next; free(cur);//释放cur所指向的内容，但是cur本身还在，是一个指针 next = next->next; } *pphead = NULL;//最后对头指针置空 }
补充：链表和顺序表的区别
关于缓存利用率：
总结：
单链表是一种链式的线性表，是一种常见的数据结构，但其对数据的管理效率并不高（只有头插，头删的效率还可以），但常常出题考察，在leetcode上非常常见，此外，单链表还经常作为更复杂数据结构的子结构出现，所以还是要掌握好单链表的相关知识，以及他的创建管理！希望这篇文章对你有用，谢谢观看！
