C++算法
数据结构：链表详解（单链表、双链表、循环链表）
系统讲解了数据结构中链表的各类实现与操作。涵盖单链表的初始化、判空、查找、插入、删除及建表方法；双链表的节点插入、删除与销毁；循环链表与静态链表的特性；并对比了顺序表与链表在存取方式、逻辑物理结构、操作复杂度及空间分配上的差异。内容适合计算机专业学生及开发者复习链表核心知识点。
系统讲解了数据结构中链表的各类实现与操作。涵盖单链表的初始化、判空、查找、插入、删除及建表方法；双链表的节点插入、删除与销毁；循环链表与静态链表的特性；并对比了顺序表与链表在存取方式、逻辑物理结构、操作复杂度及空间分配上的差异。内容适合计算机专业学生及开发者复习链表核心知识点。
它的实现逻辑是，通过一组任意的存储单元来存储线性表中的数据元素。
为建立数据元素之间的关系，对于每个结点内，除了要存放自身元素信息之外，还要存放一个指向其后继的指针。单链表结点结构图示如下：
其中 data 为数据域，用于存放数据元素；next 为指针域，用于存放后继结点的地址。
单链表中的结点声明如下：
typedef struct LNode { //定义单链表结点类型
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, *LinkList;
注意：代码使用 LNode 时，强调这是一个结点；代码使用 LinkList 时，强调这是一个单链表。*
单链表的元素并非连续存放在存储空间中，而是离散分布，所以其存储结构是顺序存取而非随机存取。所以在查找特定元素时，需要从表头开始遍历，依次查找，效率较低。
头节点和头指针的关系：无论是否有头节点，头指针始终指向链表的第一个结点，而头结点是带头链表的第一个结点，该结点内通常不存储信息。
引入头结点的优点：
这是带头结点的单链表初始化函数，先申请一块内存当这个头结点，再把它的 next 指针设成空，代表现在链表还没存任何有效数据，最后返回初始化成功的结果。
bool InitList(LinkList& L) //带头结点的单链表初始化
{
L = (LNode*)malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //头结点之后暂时没有元素节点
return true;
}
这是不带头结点的单链表初始化，逻辑更简单，直接把链表的头指针设成 NULL，就代表这个链表现在是空的，初始化就完成了，最后返回成功的状态。
bool InitList(LinkList& L)
{
L = NULL;
return true;
}
这是带头结点单链表的判空函数，给它传链表的头指针，它就帮你检查这个链表有没有存有效数据的节点，要是链表啥数据都没有，就返回 true，有数据的话就返回 false。
bool Empty(LinkList L)
{
if (L->next == NULL) //如果 L->next 为 NULL，说明链表没有任何有效数据节点，是空链表
return true;
else
return false;
}
这函数是用来算链表长度的，也就是数链表里有多少个存数据的节点。它会顺着链表一个一个往下走，每数到一个节点就给计数器加 1，直到走到链表的末尾，最后把数出来的总个数返回给你。
int Length(LinkList L)
{
int len = 0; //定义计数器 len，初始值为 0，用来统计数据节点的个数
LNode* p = L; //定义遍历用的指针 p，初始指向链表的头结点
while (p->next != NULL) //只要当前节点的下一个节点不为空，说明还有未统计的数据节点，继续遍历
{
p = p->next; //指针向后移动，走到下一个数据节点
len++; //每遍历到一个数据节点，计数器加 1
}
return len; //遍历结束，返回统计好的链表长度
}
这是按序号找节点的函数，给他要查的链表、还有要找的是第几个节点，它就顺着链表挨个往下找，找到对应节点就把这个节点的地址返回给你；要是你给的序号不对、或者链表没这么长，就返回 NULL，告诉你没找到对应的节点。
LNode* GetElem(LinkList L, int i)
{
LNode* p = L; //定义遍历用的指针 p，初始指向链表的头结点
int j = 0; //定义计数器 j，记录当前指针指向的节点序号，初始值 0 对应头结点
while (p != NULL && j < i) //只要指针没走到链表末尾，且还没到达目标序号 i，就继续遍历查找
{
p = p->next; //指针向后移动，走到下一个节点
j++; //计数器加 1，更新当前节点的序号
}
return p; //遍历结束，返回找到的节点地址（没找到对应节点则返回 NULL）
}
这是按值找节点的函数，给它要查的链表、还有要找的目标数值，它就顺着链表挨个节点看，找到第一个存了这个数值的节点，就把节点的地址返回给你；要是整个链表都找完了都没这个数，就返回 NULL，告诉你查找失败了。
LNode* LocateElem(LinkList L, ElemType e)
{
LNode* p = L->next; //定义遍历用的指针 p，初始指向第一个数据节点（跳过不存数据的头结点）
while (p != NULL && p->data != e) //只要指针没走到链表末尾，且当前节点的数据不等于目标值 e，就继续向后查找
p = p->next; //指针向后移动，检查下一个节点
return p; //遍历结束，返回找到的匹配节点地址（没找到对应节点则返回 NULL）
}
这是带头结点链表的按位置插入函数，给它要操作的链表、要在第几个位置插、还有要插入的数，它会先检查你给的位置是否合法，然后找到要插的位置的前一个节点，把新节点插进去，插成功了就返回 true，位置不对就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i < 1) //检查位序合法性
return false;
LNode* p = L; //定义遍历指针 p，初始指向链表的头结点
int j = 0; //定义计数器 j，记录当前 p 指向的节点序号，初始 0 对应头结点
while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 不为空，且还没到第 i-1 个节点，就继续遍历
{
p = p->next; //指针向后移动，走到下一个节点
j++; //计数器加 1，更新当前节点的序号
}
if (p == NULL) //如果 p 为空，说明 i 超过了链表的长度，位置不合法，返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点 s
s->data = e; //给新节点的 data 域赋值，存入要插入的元素 e
s->next = p->next; //新节点的 next 指向 p 原来的下一个节点，把链表后续的节点接在新节点后面
p->next = s; //p 的 next 指向新节点，把新节点接在 p 的后面，完成插入
return true; //插入成功，返回 true
}
这是不带头结点链表的按位置插入函数，和带头的不一样，插第一个位置的时候要单独处理，因为要修改链表的头指针；其他位置的话，也是先找到要插的位置的前一个节点，再把新节点插进去，插成功了返回 true，位置不合法就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i == 1) //单独处理插入第 1 个位置的情况（不带头结点的链表，插第一个位置要修改头指针）
{
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s
s->data = e; //给新节点赋值元素 e
s->next = L; //新节点的 next 指向原来的头节点，把原来的链表接在新节点后面
L = s; //头指针 L 指向新节点，新节点成为新的头节点
return true;
}
int j = 1; //处理插入位置不是第 1 位的情况：定义计数器 j，初始 1 对应第一个节点的序号
LNode* p = L; //定义遍历指针 p，初始指向链表的第一个节点（头指针 L）
while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 不为空，且还没到第 i-1 个节点，就继续遍历
{
p = p->next; //指针向后移动，走到下一个节点
j++; //计数器加 1，更新当前节点的序号
}
if (p == NULL) //如果 p 为空，说明 i 超过了链表的长度，位置不合法，返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s
s->data = e; //给新节点赋值元素 e
s->next = p->next; //新节点的 next 指向 p 原来的下一个节点，接好后续链表
p->next = s; //p 的 next 指向新节点，完成插入
return true;
}
这是给已知节点前插元素的函数，传入已知的节点指针 p，有要插入的数 e，它就能直接在 p 的前面插入新节点，不用从头遍历链表。操作成功就返回 true，要是你给的 p 是空的，就返回 false。
bool InsertPriorNode(LNode* p, ElemType e)
{
if (p == NULL) //如果节点 p 为空，位置不合法，直接返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s
s->next = p->next; //新节点的 next 指向 p 的下一个节点，把新节点插在 p 的后面
p->next = s;
s->data = p->data; //把 p 原来的数据复制到新节点 s 里
p->data = e; //把要插入的元素 e 存入 p 节点，相当于 p 变成了新插入的节点，s 变成了原来的 p 节点，实现前插效果
return true;
}
这是给已知节点后插元素的函数，传入已知节点的指针 p、要插入的元素 e，函数会在节点 p 的后面插入新元素 e。不用从头遍历链表，直接修改节点的指针即可完成插入，操作成功返回 true，若节点 p 为空则返回 false。
bool InsertNextNode(LNode* p, ElemType e)
{
if (p == NULL) //如果传入的节点 p 为空，位置不合法，直接返回 false，终止操作
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点 s，用来存放要插入的元素
s->data = e; //给新节点的 data 域赋值，存入要插入的元素 e
s->next = p->next; //新节点 s 的 next 指向 p 原来的下一个节点，把 p 后续的链表接在新节点后面
p->next = s; //把 p 的 next 指向新节点 s，将新节点接在 p 的后面，完成后插操作
return true;
}
入链表头指针 L、要删除的位置 i、用来接收被删除元素的变量 e，函数会检查删除位置的合法性，找到第 i-1 个前驱节点，删除第 i 个节点并释放内存，删除成功返回 true，位置不合法返回 false。
bool ListDelete(LinkList& L , int i, ElemType& e)
{
LNode* p = L; //定义遍历指针 p，初始指向链表的头结点
int j = 0; //定义计数器 j，记录当前 p 指向的节点序号，初始 0 对应头结点
while (p->next != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 的下一个节点不为空，且还没到第 i-1 个节点，就继续遍历
{
p = p->next; //指针向后移动，走到下一个节点
j++; //计数器加 1，更新当前节点的序号
}
if (p->next == NULL || j > i - 1) //校验位置合法性：如果 p 的下一个节点为空（要删除的节点不存在），或者 j 超过了 i-1（位置非法），返回 false
return false;
LNode* q = p->next; //用指针 q 指向要删除的第 i 个节点（p 的下一个节点）
e = q->data; //把被删除节点的元素值赋值给 e，带出去给调用者
p->next = q->next; //把 p 的 next 指向 q 的下一个节点，跳过要删除的节点，把链表接好
free(q); //释放 q 节点的内存，避免内存泄漏
return true;
}
传入链表头指针 L，函数会初始化带头结点的空链表，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表头结点的后，直到输入 9999 停止，最终返回建立好的链表头指针。
LinkList List_HeadInsert(LinkList& L)
{
LNode* s; //定义新节点指针 s，和用来接收用户输入的变量 x
int x;
L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点
L->next = NULL; //头结点的 next 置为 NULL，初始化空链表
scanf("%d", &x); //读取用户输入的第一个整数，存入 x
while (x != 9999) //循环：只要输入的 x 不是 9999，就继续插入节点
{
s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s
s->data = x; //给新节点赋值，存入用户输入的 x
s->next = L->next; //新节点的 next 指向头结点原来的下一个节点，接好链表的后续部分
L->next = s; //头结点的 next 指向新节点，把新节点插到链表头部
scanf("%d", &x); //读取下一个用户输入的整数，继续循环
}
return L;
}
传入链表头指针 L，函数会初始化带头结点的空链表，用尾指针 r 记录链表的最后一个节点，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表的尾部，直到输入 9999 停止，最终返回建立好的链表头指针。
LinkList List_TailInsert(LinkList& L)
{
int x; //定义用来接收用户输入的变量 x
L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点
LNode* s, * r = L; //定义新节点指针 s，和尾指针 r，初始 r 指向头结点（空链表的尾部就是头结点）
scanf("%d", &x); //读取用户输入的第一个整数，存入 x
while (x != 9999) //循环：只要输入的 x 不是 9999，就继续插入节点
{
s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s
s->data = x; //给新节点赋值，存入用户输入的 x
r->next = s; //尾指针 r 的 next 指向新节点，把新节点接到链表的尾部
r = s; //尾指针 r 移动到新节点，更新为新的链表尾部
scanf("%d", &x); //读取下一个用户输入的整数，继续循环
}
r->next = NULL; //循环结束，把链表最后一个节点的 next 置为 NULL，标记链表结束
return L; //链表建立完成，返回链表的头指针
}
单链表中只有一个指向后继结点的指针，这导致其在执行查找、插入和删除等操作的时候只能从头开始遍历，时间复杂度为 O(n) 。所以双链表的产生就是为了解决这种问题，其拥有 prior 指针和 next 指针，分别指向其直接前驱和直接后继。双链表结点结构图示如下：
单链表中的结点声明如下：
typedef struct DNode { //定义双链表结点类型
ElemType data; //数据域
struct DNode* prior, * next; //前驱指针和后驱指针
}DNode, *DLinklist;
注意：代码使用 DNode 时，强调这是一个结点；代码使用 DLinkList 时，强调这是一个双链表。*
双链表的按值查找和按位查找时间复杂度与单链表持同，因为其都为顺序存取结构；但是其插入与操作快于单链表，因为双链表拥有前驱指针，可以很容易地找到前一结点，时间复杂度为 O(1) 。
这是带头结点的双链表初始化函数，说白了就是给双链表建一个头结点，先申请一块内存当这个头结点，要是内存申请失败就返回 false；申请成功的话，就把头结点的前驱指针 prior 和后继指针 next 都设成 NULL，代表现在链表是空的，最后返回初始化成功的 true。
bool InitDLinklist(DLinklist& L)
{
L = (DNode*)malloc(sizeof(DNode)); //申请一块内存，大小是一个 DNode 节点的大小，把申请到的地址赋值给头指针 L，也就是创建头结点
if (L == NULL) //如果 L 是 NULL，说明刚才申请内存失败了，直接返回 false
return false;
L->prior = NULL; //把头结点的前驱指针 prior 设为 NULL，头结点前面没有节点
L->next = NULL; //把头结点的后继指针 next 设为 NULL，头结点后面也没有节点，现在链表是空的
return true;
}
这是双链表的节点后插函数，给它一个已知的节点 p，还有要插入的新节点 s，它就能把 s 插到 p 的后面。因为双链表有前后两个指针，所以要把新节点和前后的节点的指针都接好，要是 p 或者 s 是空的，就直接返回 false，操作成功就返回 true。
bool InsertNextDNode(DNode* p, DNode* s)
{
if (p == NULL || s == NULL) //如果 p 是空的，或者 s 是空的，位置不合法，直接返回 false
return false;
s->next = p->next; //让新节点 s 的后继指针，指向 p 原来的下一个节点，先把 p 后面的链表接在 s 的后面
if (p->next != NULL) //如果 p 原来的下一个节点不是空的
p->next->prior = s; //让 p 原来的后继节点的前驱指针，指向新节点 s，把后面节点的前向指针接好
s->prior = p; //让新节点 s 的前驱指针，指向节点 p，把 s 和 p 的前向关系接好
p->next = s; //让 p 的后继指针，指向新节点 s，把 p 和 s 的后向关系接好，完成插入
return true;
}
这是双链表的节点删除函数，作用是删掉节点 p 后面的那个节点。它会先检查 p 是不是空的，还有 p 后面有没有节点可以删，要是没的删就返回 false；有的话就把链表的前后指针重新接好，跳过要删的节点，再释放掉这个节点的内存，避免内存泄漏，删成功了就返回 true。
bool DeleteNextNode(DNode* p)
{
if (p == NULL) //如果 p 是空的，位置不合法，直接返回 false
return false;
DNode* q = p->next; //用指针 q 指向 p 的后继节点，也就是我们要删掉的节点
if (q == NULL) //如果 q 是空的，说明 p 后面没有节点，没的可删，返回 false
return false;
p->next = q->next; //让 p 的后继指针，直接指向 q 的下一个节点，跳过要删的 q 节点，把链表的后向接好
if (q->next != NULL) //如果 q 的下一个节点不是空的（也就是 q 不是链表最后一个节点）
q->next->prior = p; //让 q 的后继节点的前驱指针，指向 p，把链表的前向接好
free(q); //释放掉 q 节点的内存，把要删的节点彻底清掉，避免内存泄漏
return true;
}
这是销毁整个双链表的函数，说白了就是把整个链表的所有节点都删掉，释放所有占用的内存，避免内存泄漏。它会循环调用刚才的删除函数，一直删掉头结点后面的所有节点，最后把头结点也释放掉，再把头指针设成 NULL，整个链表就彻底销毁了。
void DestroyList(DLinklist& L)
{
while (L->next != NULL) //循环：只要头结点的后面还有节点，就继续删
DeleteNextNode(L); //调用删除函数，删掉头结点后面的第一个节点，循环执行直到所有数据节点都被删掉
free(L); //所有数据节点都删完了，现在释放头结点的内存
L = NULL; //把头指针 L 设为 NULL，避免变成野指针
return;
}
循环单链表与单链表的区别就是，原来表尾指针指向 NULL 的，现在改为指向头结点。
循环单链表结点结构图示如下：
因此循环单链表中不会出现指针域指向 NULL 的结点，因此判空条件从是否头结点指向 NULL 改为是否等于头指针 L。
**判空：*L->next == L;
**判 p 是否为尾：*p->next == L;
循环双链表相比循环单链表增加了头结点的 prior 指针也将指向表尾结点这一点。
循环双链表结点结构图示如下：
同理，循环双链表的判空条件是头结点的 prior 指针和 next 指针是否都指向头指针 L。
**判空：*L->next == L; L->prior == L;
**判 p 是否为尾：*p->next == L;
静态链表说白了就是用数组来实现线性表的链式存储结构，结点同样也分为用来存我们要放的实际数据的数据域 data 和指针域 next。不过这里的'指针'不是真正的内存地址，而是下一个节点在数组里的下标（也叫游标）。
**注意：**静态链表的数组大小是我们提前定好的，所以它能存的节点数量有固定上限，不能像动态链表那样随便加节点。
静态链表结点结构图示如下：
静态链表中的结点声明如下：
#define MaxSize 50 //宏定义一个静态链表的最大长度
typedef struct { //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
静态链表以 next == -1 作为结束标志，因为数组的下标都是 ≥0 的正数，-1 就代表'这个节点后面没有其他节点了'，作用和动态链表最后一个节点的 next=NULL 是一模一样的。
其余操作与动态链表几乎相同，比如插入、删除节点，都只需要修改 next 指针，不用移动其他元素。唯一的小区别是，静态链表不用手动申请、释放节点的内存，而是从我们提前开好的数组里找空闲的位置来用，动态链表则是需要的时候才申请内存。
顺序表：支持随机存取和顺序存取。
顺序表的本质是数组，只要给出元素的下标，就可以直接通过内存地址计算一步找到对应元素，时间复杂度为 O(1) 。比如我们要找顺序表的第 5 个元素，直接访问 data[4] 就能拿到，不需要遍历前面的元素。
链表：仅支持顺序存取。
链表的节点在内存中是分散的，要找到第 i 个元素，必须从链表的头结点开始，顺着指针一个一个遍历到目标位置，无法直接跳转到对应节点，时间复杂度为 O(n) 。比如要找链表的第 5 个元素，必须从第 1 个开始，依次往后数 4 次才能找到。
顺序表：采用顺序存储。逻辑上相邻，物理存储位置也相邻。
链表：采用链式存储。逻辑上相邻，物理存储位置不一定相邻。
**按序查找：**顺序表的随机存取结构使得时间复杂度为 O(1) ;链表必须从头开始遍历查找，所以时间复杂度为 O(n) 。
**按值查找：**如果表内元素是无序的，则顺序表和链表都必须从头开始找，时间复杂度均为 O(n) ；如果表内元素是有序的，则顺序表可以用二分法查找，时间复杂度为 O(nlog2n) ，而链表时间复杂度依旧为 O(n) 。
顺序表：分为静态分配顺序表和动态分配顺序表。
对于静态分配顺序表，数组大小在初始化的时候就已经定死了，若分配量过小，元素量超出存储空间上限就会溢出导致运行崩溃；若分配量过大，会使得空间闲置浪费。
而动态分配顺序表，虽然可以在存储空间不够用时随时扩容，但是它的扩容是开一个新空间，然后把旧空间装不下的内容全部复制到新空间中，操作量大，效率极低。并且还可能因为找不到足够大的连续内存而扩容失败.
**链表：**其结点内存是在插入时才申请、删除时就释放的，不需要提前确定链表的最大长度，只要系统还有可用内存，就可以继续添加结点；同时结点可以利用内存中零散的空闲空间，不会出现大块内存闲置的问题，唯一的空间开销是每个结点需要额外的内存来存放指针。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online