单链表总结提升

这篇博客讲解数据结构中的单链表，包括单链表的基础知识和我对链表实现的总结理解，希望可以帮助到正在学习的小伙伴，也希望得到小伙伴们的关注和支持哦~

1.单链表的概念

1.2顺序表和链表的对比

顺序表：

链表：

链表相对于顺序表：

2.单链表的结构

3.单链表的实现

总结单链表函数书写要点：

一、关于是否需要分支：

二、关于删除操作：

三、关于为什么用二级指针

1.单链表的概念

在之前顺序表的博客中讲解过线性表

线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表在逻辑结构和物理结构上都是连续的（类似数组），而今天要说的链表在物理结构上是非连续的！

所以，链表到底是什么呢？它和顺序表到底有哪些不同呢？

1.2顺序表和链表的对比

顺序表：

实质上就是对数组的操作，相对于静态顺序表来说，动态顺序表可以更加灵活地申请使用空间，不过，在顺序表使用的后期，开辟的内存成倍增加，如果再次加入的数据不多，还是会导致空间的浪费，而且在每次非尾部插入和删除时，总要对数组元素进行大量移动，效率还是没有那么高。

再次看一下顺序表的结构：

typedef int SLDateType;
typedef struct SeqList {SLDateType* a;int size;//有效数据个数int capacity;//当前顺序表容量
}SL;

顺序表缺点小总结：

后期内存开辟成倍增加
插入删除元素对顺序表移动元素较多

从中我们也可以猜测出链表的功能，开辟内存不会成倍增加且插入删除不必移动过多元素

链表：

实质上是指针链接，就好比如图所示的火车：

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？最简单的做法：每节车厢里都放一把下一节车厢的钥匙。这里的钥匙就是指针。

链表相对于顺序表：

将数组这一整体变为一个一个的链表节点，从对整体开辟内存变为对单个节点开辟内存
将顺序表用于计数的size和capacity去除，不再有越界的问题，取而代之的是链接下一个节点的指针
链表缺点在于无法通过下标访问，只能从头一个一个去访问，原因是一个一个申请的内存空间可能连续也可能不连续
顺序表和链表都是基于结构体实现的

2.单链表的结构

ps：节点和结点表示一个意思

画出单链表的结构大致如下：

所有的链表节点都使用链表结构体指针去访问，一个链表节点包含数据区和指针区，数据区用于存放数据；指针区用于存放下一个节点的地址
plist相当于火车头，出于方便，习惯叫它头结点，不过这种叫法其实不符合逻辑，也是结构体指针类型，单链表也可以没有plist
还有一种链表，叫带头链表，这种链表的头节点数据区没有值，这个头节点叫做哨兵位，区分一下这两种链表

单链表结构体用代码书写就是：

typedef int SLTDateType;
typedef struct SListNode {SLTDateType val;//存放有效值struct SListNode* next;//指向下一个节点
}SLTNode;

SList 代表 single list

3.单链表的实现

使用单链表实现数据的增删查改

SList.h存放链表结构体及相关函数声明：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDateType;
typedef struct SListNode {SLTDateType val;struct SListNode* next;
}SLTNode;
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);//头删
void SLTPopFront(SLTNode** pphead);//尾删
void SLTPopBack(SLTNode** pphead);//申请内存
SLTNode* SLTBuyNode(SLTDateType x);
//打印链表
void SLTPrint(SLTNode* phead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** pphead);

SList.c存放相关函数定义

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//申请内存
SLTNode* SLTBuyNode(SLTDateType x)
{SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode));if (p == NULL){perror("fail malloc");exit(1);}p->val = x;p->next = NULL;return p;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* pcur = SLTBuyNode(x);//不用找尾，不用对原先链表解引用，故不用考虑链表为空的情况pcur->next = *pphead;*pphead = pcur;}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* ptail=*pphead;//链表为空if (*pphead == NULL)//如果链表为空，则找尾时不能对空指针解引用，故需要分支{*pphead = SLTBuyNode(x);}else{//找尾while (ptail->next != NULL){ptail = ptail->next;}//接入ptail->next = SLTBuyNode(x);}}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead&&*pphead);//只有一个节点和有多个节点可以使用相同方法//需要头结点后的位置的地址，若只有一个节点，其后面有位置，故不用分支SLTNode* pcur = *pphead;*pphead = (*pphead)->next;free(pcur);pcur = NULL;	
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* ptail = *pphead;SLTNode* prev = *pphead;if (ptail->next == NULL)//只有一个节点（ptail prev未错开）//需要尾节点前一位的地址，若尾节点为头节点，头结点前无位置，故需要分支{free(*pphead);*pphead = NULL;}else//有多个节点（ptail prev错开）{//找尾while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}
//打印链表
void SLTPrint(SLTNode* phead)
{//assert(phead);while (phead != NULL){printf("%d->", phead->val);phead = phead->next;}printf("NULL\n");
}
//查找
SLTNode* SLTFind(SLTNode* phead,SLTDateType x)
{SLTNode* pcur = phead;while (phead){if (phead->val == x){return phead;}phead = phead->next;}return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead && *pphead);assert(pos);SLTNode* pcur = *pphead;//第一个位置为指定位置if (pcur == pos)//需要指定位置之前的位置和指定位置的地址，头节点之前无位置，故需要分支{SLTPushFront(pphead, x);}//其他位置else{while (pcur->next != pos){pcur = pcur->next;}//插入SLTNode* pin = SLTBuyNode(x);pin->next = pos;pcur->next = pin;}}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead && *pphead);assert(pos);SLTNode* pcur = *pphead;//找到指定位置while (pcur != pos)//需要指定位置和指定位置之后位置的地址，尾节点后有位置，故不需要分支{pcur = pcur->next;}//插入(最后节点后插入与其他位置相同)SLTNode* pin = SLTBuyNode(x);pin->next = pcur->next;pcur->next = pin;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* pcur = *pphead;//删除头结点if (pcur == pos)//需要pos前和pos后的位置，若pos为头结点，头结点前无位置，故需要分支{SLTPopFront(pphead);}else//非头结点{while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;//pos相当于尾删里面的prev，故不用再创建结构体指针来保存前一个位置的nextfree(pos);pos = NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos && pos->next);SLTNode* pcur = *pphead;while (pcur!=pos)//需要pos和pos之后的之后的地址，若pos为尾节点，尾节点后有位置，故不需要分支{pcur = pcur->next;}SLTNode* pout = pos->next;//pos和pcur指向相同，pcur发生改变导致pos发生改变，保存pos地址用于删除pcur->next = pos->next->next;free(pout);pout = NULL;
}//销毁链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur;while (*pphead){pcur = *pphead;*pphead = (*pphead)->next;free(pcur);pcur = NULL;}
}

总结单链表函数书写要点：

一、关于是否需要分支：

1.传入链表可能为空的函数：关键要清楚是否需要某个节点的next（也就是是否对需要某节点指针解引用）

对于头插尾插：头插不需要原链表头结点的next，尾插需要原链表尾节点的next用于链接，故尾插需要考虑链表为空的情况（不能对空指针解引用）。尾插需要分支，头插不用分支。

2.传入链表不能为空的函数（讨论只有一个节点的情况）：关键要确定需要找的节点是否存在（节点为NULL也是存在，不存在指找不到其地址）

对于头删尾删：头删需要头结点后面的节点，当链表只有一个节点时，头结点后面的节点存在，故头删不用分支；尾删需要尾节点前面的节点，当链表只有一个节点时，尾节点前面的节点不存在，故尾删需要分支。
对于任意位置插入：pos之前插入需要pos和pos前面的节点，当链表只有一个节点时，pos前面节点不存在，故前插需要分支；pos之后插入需要pos和pos后面的节点，当链表只有一个节点时，pos后面节点存在，故后插不用分支。
对于任意位置删除：pos位置删除需要pos前面和pos后面的节点，当链表只有一个节点时，pos前面节点不存在，故pos删除需要分支；pos之后删除需要pos和pos后面的后面的节点，当链表只有一个节点时，接收链表时就要断言报错，因为无法删除一个不存在的节点，故pos后删不用分支。

总体来说，相对于参考节点，向前看的需要分支讨论，向后看的不需要分支讨论

向前看的（要分支的）都是用pcur->next 与某节点比较作为循环判断条件
向后看的（不要分支的）都是用pcur与某节点比较作为循环判断条件

二、关于删除操作：

关键在于确定删除操作中链接前后节点所使用的指针是否使被删的节点指针指向发生改变

对于头删：需要头结点和头结点后的节点，头结点为被删节点，链接前后节点时，头指针指向发生了改变，故需要指针保存原来的头结点，进行后续删除。
对于尾删：需要尾节点和尾节点前的节点，尾节点为被删节点，链接前后节点时，尾指针指向没有发生改变，故直接删除。
对于删pos节点：需要pos前和pos后的节点，pos为被删节点，链接前后节点时，pos指针指向没有发生改变，故直接删除。
对于删pos后的节点：需要pos和pos后面的后面的节点，pos->next为被删节点，链接前后节点时，pos指针指向发生改变，会导致pos->next指针指向发生改变，故需要指针保存原来的pos->next，进行后续删除。