数据结构：双向链表（1~2）
目录
前言
本篇文章将讲解双向链表概念与结构，实现双向链表，顺序表与链表的分析，链表算法题等知识的相关内容，为本章节知识的内容。
一、双向链表概念与结构
双向链表概念
双向链表是一种链式存储的数据结构，每个节点包含两个指针：一个指向前驱节点（prior），一个指向后继节点（next），同时包含数据域（data）存储数据。这种结构允许双向遍历（从头到尾或从尾到头），并支持更灵活的插入、删除操作，但相比单链表会增加一定的空间开销（额外的指针域）。
图示：（不带头双向循环链表）
双向链表不仅能找到当前节点的下一个节点还可以找到当前节点的上一个节点，使用起来是很方便的。
因为刚刚讲解过的单链表为单向不带头不循环链表，目前还没有讲过带头形式的，所以本双链表为
带头双向循环链表。
带头双向循环链表
带头双向循环链表是一种兼具“头节点”“双向指针”“循环结构”三大特性的链表，是应用最广泛的双向链表类型。其结构稳定、边界处理简单，支持高效的插入、删除和双向遍历操作。
对于上面头结点讲解：
带头链中的头节点，是不存储任何有效数据，只用来站岗放哨，我们可称之为"哨兵位" 在单链表的学习中，我们有时候也会把第一个节点表述为头节点，其实这个称呼是不严谨的：按照定义来说，严谨的定义：头节点是链表中第一个节点，但不存储有效数据（部分场景可存储链表长度等元信息），其核心价值是简化边界操作（如插入/删除首节点时无需特殊判断）。
双向链表结构
根据前文知识讲解，以及前面单向不带头不循环链表的知识，我们来实现下双向链表结构：
typedef int type; typedef struct ListNode { type data; //前驱指针,指向前一个指针 struct ListNode* prev; //后继指针，指向后一个指针 struct ListNode* next; }ListNode;二、实现双向链表
1.双向链表的初始化
我们在双向链表中头节点（可叫哨兵位）是需要初始化一下的，数据域可以存任意的数据，前驱指针和后继指针都指向自己即可。
函数形式：
void LTInit(ListNode** h);
实现：
void LTInit(ListNode** h) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } *h = ph; (*h)->data = -1; (*h)->next = *h; (*h)->prev = *h; }细讲：代码逐行解析
初始图示：
void test() { ListNode* h; LTInit(&h); } int main() { test(); }
2.双向链表的尾插
双向链表尾插是指在链表的 尾部（最后一个有效节点之后） 插入新节点。对于 带头节点的双向循环链表，尾插可直接通过头节点的 prev 指针定位尾节点，无需遍历链表，时间复杂度为 O(1)。
void LTPushBack(ListNode* h, type x)
不过，该函数为实现尾插入，需要插入一个新节点，但传入的参数为type，需要先将type类型转化为ListNode*类型，所以，应有下面函数:
创建节点
ListNode* LTcreat(type x)
ListNode* LTcreat(type x) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } ph->data = x; ph->next = ph; ph->prev = ph; return ph; } void LTPushBack(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h; p->prev = h->prev; h->prev->next = p; h->prev = p; }讲解：LTcreat函数：创建新节点（含哨兵位初始化）功能：创建一个新节点，初始化data为x，并让next和prev指针自指（形成循环）。用途：可用于 初始化链表的哨兵位头节点（此时x通常为无意义值，如-1）；也可用于 创建普通有效节点（此时x为实际数据）。LTPushBack函数：尾插操作核心逻辑：通过LTcreat(x)创建新节点p，并插入到链表尾部（头节点h的prev位置）。步骤拆解：ListNode* p = LTcreat(x);→ 创建新节点p（p->next和p->prev初始指向自身）。p->next = h;→ 新节点p的next指向头节点h（保持循环）。p->prev = h->prev;→ 新节点p的prev指向原尾节点（h->prev是原尾节点）。h->prev->next = p;→ 原尾节点的next指向新节点p。h->prev = p;→ 头节点h的prev指向新节点p（更新尾节点为p）。
newNode->prev = h->prev; // 新节点 prev 指向原尾节点 newNode->next = h; // 新节点 next 指向头节点 h->prev->next = newNode; // 原尾节点 next 指向新节点 h->prev = newNode; // 头节点 prev 更新为新节点（新尾节点）图示：
3.双向链表的头插
头插是双向链表中最常用的操作之一，指将新节点插入到 头节点之后、第一个有效节点之前 的位置。适用于需频繁在头部添加数据的场景。
根据上面所说，我们可以知晓一点：插入到 头节点之后、第一个有效节点之前 的位置，所以实现上要考虑考虑：
void LTPushFront(ListNode* h, type x)
ListNode* LTcreat(type x) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } ph->data = x; ph->next = ph; ph->prev = ph; return ph; } void LTPushFront(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h->next; p->prev = h; h->next->prev = p; h->next = p; }细讲一下：
向 带头节点的双向循环链表 头部插入新节点（头插）。
前提：链表已初始化（头节点h存在，且h->next和h->prev初始指向自身，即空链表状态）。
完整头插流程（以空链表插入第一个节点为例）
假设头节点h已通过LTcreat(-1)创建（-1为哨兵位无效数据），插入第一个有效节点x=10：创建新节点：ListNode* p = LTcreat(10);LTcreat分配内存并初始化p->data=10，p->next=p，p->prev=p。结果：链表变为h <-> p（双向循环，p为唯一有效节点）。
插入新节点：
p->next = h->next; // 步骤1：p->next = h（因空链表 h->next = h） p->prev = h; // 步骤2：p->prev = h（头节点为 p 的前驱） h->next->prev = p; // 步骤3：h->prev = p（原 h->next 是 h，故 h->prev 指向 p） h->next = p; // 步骤4：h->next = p（头节点 next 指向 p，p 成为第一个有效节点） 图示：
4.双向链表的尾删
双向链表的尾删（删除链表最后一个有效节点）是链表操作的高频场景，其核心是 安全释放尾节点内存并修复前驱节点的指针关系。实现尾删之前，我们需要先实现一个判空的函数，如果链表为空则不能继续删除了：
尾删函数形式：
void LTPopBack(ListNode* h)
双向链表的判空
bool LTEmpty(ListNode* phead)
bool LTEmpty(ListNode* phead) { assert(phead); return phead->next == phead; }讲解:空链表：头节点的next指针指向自身（phead->next == phead），此时链表无任何有效节点。非空链表：头节点的next指向第一个有效节点（phead->next != phead）。
接下来回归正题：
bool LTEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } void LTPopBack(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->prev; h->prev = p->prev; p->prev->next = h; free(p); }讲解：
步骤1：判空——避免对空链表操作（核心安全检查！）LTEmpty 逻辑：return phead->next == phead（头节点的next指向自身，说明无有效节点）。作用：若链表为空（如h <-> h），直接返回，避免后续p->prev访问空指针导致 程序崩溃。
步骤2：定位尾节点——无需遍历，O(1) 效率！双向循环链表特性：头节点的prev指针 直接指向尾节点（无需从h->next开始遍历），时间复杂度 O(1)（单向链表需 O(n)，这是双向链表的核心优势）。
步骤3：修复指针——确保链表循环关系不中断修复后链表结构：h <-> A <-> B <-> h（尾节点 C 已从逻辑上“脱离”链表）。关键对比：若仅修改h->prev = p->prev而不修改p->prev->next，会导致 B 的 next 仍指向 C，链表出现“断裂”（B <-> C <-> h <-> A <-> B），形成错误的循环子链。
步骤4：释放内存——避免内存泄漏（必须！）
尾删图示：
5.双向链表的头删
双向链表的头删指删除链表的第一个有效节点（即头节点后的第一个节点）。带头节点的链表可避免对空链表的特殊处理，实现更简洁。
根据前文所讲，我们可知其实现图示：
函数形式：
void LTPopFront(ListNode* h);
void LTPopFront(ListNode* h) { if (LTEmpty(h) ) { printf("链表为空，无法头删\n"); return; } ListNode* p = h->next; h->next = p->next; p->next->prev = h; free(p); }讲解：
核心代码逐行解析
1. 判空处理（避免操作无效链表）h == NULL：检查头节点指针是否为空（链表未初始化）。h->next == h：检查链表是否为空（头节点的next指向自身，说明无有效节点）。处理逻辑：若满足任一条件，打印错误信息并退出函数，避免后续非法操作。
2. 记录待删除节点头节点h的next指针指向链表的第一个有效节点，用p临时保存该节点地址，便于后续释放内存。
3. 更新链表指针关系（断链与重连）步骤1：头节点h不再指向p，而是直接指向p的下一个节点（p->next），完成“前向断链”。步骤2：p的下一个节点（p->next）的prev指针从指向p改为指向头节点h，完成“反向断链”。效果：通过双向指针的更新，p节点从链表中完全脱离。
4. 释放内存（避免内存泄漏）手动释放p指向的节点内存（C语言需显式管理内存，否则会导致内存泄漏）。
6.双向链表的销毁
双向链表的销毁需遍历所有节点并逐个释放内存，避免内存泄漏，顺序为：先销毁除了头结点（哨兵位）之外的所有节点，在最后释放头结点空间。
函数形式：
void LTDestory(ListNode* h)；
void LTDestory(ListNode* h) { if (LTEmpty(h)) { free(h); return; } ListNode* p = h->next; while (p != h) { ListNode* pr = p; p = p->next; free(pr); } free(h); h = NULL; }讲解：
按道理来说是要传入二级指针的，但是前面其它接口都用的一级，这里和初始化部分统一比较好点，我们可以在测试文件中最后销毁完手动将头节点置为空。
借助现有实现测试：
本代码通过三个文件来实现的：
首先：
1.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct ListNode { type data; //前驱指针,指向前一个指针 struct ListNode* prev; //后继指针，指向后一个指针 struct ListNode* next; }ListNode; void LTInit(ListNode** h); void LTPushBack(ListNode* h, type x); ListNode* LTcreat(type x); void LTPushFront(ListNode* h, type x); void LTPopBack(ListNode* h); void LTPopFront(ListNode* h); void LTDestory(ListNode* h); void print(ListNode* h);1.cpp
#include"1.h" void LTInit(ListNode** h) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } *h = ph; (*h)->data = -1; (*h)->next = *h; (*h)->prev = *h; } ListNode* LTcreat(type x) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } ph->data = x; ph->next = ph; ph->prev = ph; return ph; } void LTPushBack(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h; p->prev = h->prev; h->prev->next = p; h->prev = p; } void LTPushFront(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h->next; p->prev = h; h->next->prev = p; h->next = p; } bool LTEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } void LTPopBack(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->prev; h->prev = p->prev; p->prev->next = h; free(p); } void LTPopFront(ListNode* h) { if (LTEmpty(h) ) { printf("链表为空，无法头删\n"); return; } ListNode* p = h->next; h->next = p->next; p->next->prev = h; free(p); } void LTDestory(ListNode* h) { if (LTEmpty(h)) { free(h); return; } ListNode* p = h->next; while (p != h) { ListNode* pr = p; p = p->next; free(pr); } free(h); h = NULL; } void print(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->next; while (p != h) { printf("%d ", p->data); p = p->next; } printf("\n"); }main.cpp
#include"1.h" void test() { ListNode* h; LTInit(&h); LTPushBack(h, 10); //10 LTPushBack(h, 15); //10 15 LTPushBack(h, 111); //10 15 111 print(h); LTPushFront(h, 2); //2 10 15 111 LTPushFront(h, 12); //12 2 10 15 111 print(h); LTPopBack(h); // 12 2 10 15 print(h); LTPopFront(h); //2 10 15 print(h); LTDestory(h); } int main() { test(); }结果：
7.双向链表查找
双向链表的查找操作与单链表类似，但可利用创建一个暂时的指针实现遍历。
函数形式：
ListNode* LTFind(ListNode* h, type x)；
实现：
ListNode* LTFind(ListNode* h, type x) { if (LTEmpty(h)) { return NULL; } ListNode* p = h->next; while (p != h) { if (p->data == x) { return p; } p = p->next; } return NULL; }细讲：
通过遍历来实现，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空。
8.双向链表在指定位置插入
双向链表在指定位置插入分为双向链表在指定位置之前插入与双向链表在指定位置之后插入：
双向链表在指定位置之后插入
函数形式：
void LTInsert(ListNode* pos, type x)
实现：
void LTInsert(ListNode* pos, type x) { assert(pos); ListNode* p = pos->next; ListNode* newnode = LTcreat(x); pos->next = newnode; newnode->prev = pos; newnode->next = p; p->prev = newnode; }细讲：该函数用于在双向链表的 指定节点pos之后插入新节点，核心逻辑是通过调整指针关系实现无缝插入。
1.参数与前置检查作用：pos是插入位置的基准节点（新节点将插入其后），x是新节点的数据。风险控制：assert(pos)防止用户传入nullptr导致后续操作崩溃。
2. 保存后继节点必要性：插入新节点后，pos的next指针会指向新节点，若不提前保存原后继pos->next，将导致原链表后半部分丢失。
核心：调整指针关系（4步插入法）
在指定位置之后的插入操作其实也没有很难，还是先断言，后续就是先申请一个新节点，跟头插尾插相似的方式。
双向链表在指定位置之前插入
函数形式：
void LTInsertfront(ListNode* pos, type x);
实现：
void LTInsertfront(ListNode* h, ListNode* pos, type x) { if (LTEmpty(h)) { return ; } ListNode* p = h; while (p->next != h) { if (p->next == pos) { break; } p = p->next; } if (p->next == h) { return; } ListNode* newnode = LTcreat(x); ListNode* pr = p->next; newnode->next = pr; newnode->prev = p; p->next = newnode; pr->prev = newnode; }细讲：核心功能是 在指定节点pos的前驱位置插入新节点（即“在pos前面插入”）。
9.双向链表指定位置删除
删除节点需修改 前驱节点的 next 和 后继节点的 prev，并释放被删节点内存。关键是 处理边界情况（如 pos 是头/尾节点）。
函数形式：
void LTErase(ListNode* pos)
实现：
void LTErase(ListNode* pos) { assert(pos); ListNode* p = pos->prev; p->next = pos->next; pos->next->prev = p; free(pos); pos = NULL; }细讲：步骤：通过pos->prev获取前驱节点p；调整指针：p->next = pos->next（切断p与pos的连接，指向pos的后继）；调整后继节点的前驱指针：pos->next->prev = p（切断后继与pos的连接，指向p）；释放pos节点内存，并置空局部指针pos。前置断言assert(pos)作用：确保pos不为空指针，避免后续pos->prev等操作引发崩溃。
10.总代码展示：(加入了测试代码)
1.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct ListNode { type data; //前驱指针,指向前一个指针 struct ListNode* prev; //后继指针，指向后一个指针 struct ListNode* next; }ListNode; void LTInit(ListNode** h); void LTPushBack(ListNode* h, type x); ListNode* LTcreat(type x); void LTPushFront(ListNode* h, type x); void LTPopBack(ListNode* h); void LTPopFront(ListNode* h); void LTDestory(ListNode* h); void print(ListNode* h); ListNode* LTFind(ListNode* h, type x); void LTInsert(ListNode* pos, type x); void LTInsertfront(ListNode* h,ListNode* pos, type x); void LTErase(ListNode* pos);1.cpp
#include"1.h" void LTInit(ListNode** h) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } *h = ph; (*h)->data = -1; (*h)->next = *h; (*h)->prev = *h; } ListNode* LTcreat(type x) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } ph->data = x; ph->next = ph; ph->prev = ph; return ph; } void LTPushBack(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h; p->prev = h->prev; h->prev->next = p; h->prev = p; } void LTPushFront(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h->next; p->prev = h; h->next->prev = p; h->next = p; } bool LTEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } void LTPopBack(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->prev; h->prev = p->prev; p->prev->next = h; free(p); } void LTPopFront(ListNode* h) { if (LTEmpty(h) ) { printf("链表为空，无法头删\n"); return; } ListNode* p = h->next; h->next = p->next; p->next->prev = h; free(p); } void LTDestory(ListNode* h) { if (LTEmpty(h)) { free(h); return; } ListNode* p = h->next; while (p != h) { ListNode* pr = p; p = p->next; free(pr); } free(h); h = NULL; } void print(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->next; while (p != h) { printf("%d ", p->data); p = p->next; } printf("\n"); } ListNode* LTFind(ListNode* h, type x) { if (LTEmpty(h)) { return NULL; } ListNode* p = h->next; while (p != h) { if (p->data == x) { return p; } p = p->next; } return NULL; } void LTInsert(ListNode* pos, type x) { assert(pos); ListNode* p = pos->next; ListNode* newnode = LTcreat(x); pos->next = newnode; newnode->prev = pos; newnode->next = p; p->prev = newnode; } void LTInsertfront(ListNode* h, ListNode* pos, type x) { if (LTEmpty(h)) { return ; } ListNode* p = h; while (p->next != h) { if (p->next == pos) { break; } p = p->next; } if (p->next == h) { return; } ListNode* newnode = LTcreat(x); ListNode* pr = p->next; newnode->next = pr; newnode->prev = p; p->next = newnode; pr->prev = newnode; } void LTErase(ListNode* pos) { assert(pos); ListNode* p = pos->prev; p->next = pos->next; pos->next->prev = p; free(pos); pos = NULL; }main.cpp
#include"1.h" void test() { ListNode* h; LTInit(&h); LTPushBack(h, 10); //10 LTPushBack(h, 15); //10 15 LTPushBack(h, 111); //10 15 111 print(h); LTPushFront(h, 2); //2 10 15 111 LTPushFront(h, 12); //12 2 10 15 111 print(h); LTPopBack(h); // 12 2 10 15 print(h); LTPopFront(h); //2 10 15 print(h); ListNode* p = LTFind(h,10); LTInsert(p, 100); //2 10 100 15 print(h); LTInsert(p, 200); //2 10 200 100 15 print(h); LTErase(p); print(h); //2 200 100 15 LTDestory(h); } int main() { test(); }
三、顺序表与链表的分析
本图列举了顺序表与链表之间的相同点与不同点：
一、相同点逻辑结构一致：均为线性表，数据元素之间呈一对一的顺序关系。核心操作相同：都支持插入、删除、查找、遍历等基本线性表操作。存储数据类型：均可存储相同类型的数据元素（如整数、结构体等）。二、不同点（核心差异）三、关键结论顺序表：适合 频繁随机访问、数据量固定 的场景（如存储学生信息表）。链表：适合 频繁插入删除、数据量动态变化 的场景（如实现队列、栈）。
四、链表算法题
一、移除链表元素
由题意可知，本题要求移除值为val的节点，并要求返回新的头结点：1.链表的解法可以通过遍历整个链表，用一个节点存储前一个节点，在发现值为val时候改变next区域的指向解答：2.我们也可以选择创建一个新链表，存储符合要求的节点，虽然没有释放原链表空间，但做OJ题不释放也没什么问题的，该方法较为简单，本次解题选择此方法：
解题代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode Node; struct ListNode* removeElements(struct ListNode* head, int val) { Node *h=NULL,*pr=NULL; Node * p=head; while(p) { if(p->val!=val) { if(h==NULL) { h=p; pr=p; } else { pr->next=p; pr=p; } } p=p->next; } if(pr) pr->next=NULL; return h; }解题思路：
1.变量初始化h：新链表的头节点，初始为NULL（表示新链表为空）。pr：新链表的尾节点指针，用于拼接有效节点（值不等于val的节点）。p：遍历指针，从原链表头节点head开始，依次访问每个节点。
2. 遍历原链表（while (p)）
循环条件p等价于p != NULL，即遍历至原链表末尾时停止。情况1：当前节点p的值不等于val（需保留）首次保留节点（h == NULL）：
新链表为空，因此h（头节点）和pr（尾节点）都指向当前节点p。非首次保留节点（h != NULL）：
通过pr->next = p将当前节点p拼接到新链表尾部，然后pr = p更新尾节点指针。情况2：当前节点p的值等于val（需删除）
不执行任何操作（不拼接至新链表），直接通过p = p->next跳过当前节点。
3. 处理新链表尾节点（if (pr) pr->next = NULL）遍历结束后，pr指向新链表的最后一个有效节点。若新链表非空（pr != NULL），需将其next置为NULL，避免原链表中后续节点（已删除节点）的指针残留，导致野指针风险。
4. 返回新链表头节点h指向新链表的第一个有效节点，若原链表所有节点都被删除（如head = [2,2,2], val=2），则h保持NULL，返回空链表。
二、反转链表
解题思路:
反转题中给出的链表，如果简单来想，我们可以创建一个新链表一个一个节点的复制，但是题中的是单链表，不可找到前驱节点的，如果用上面思路，那会相当麻烦了。正确思路：通过三个指针来实现：迭代法（推荐：时间O(n)，空间O(1)）核心思路：通过 3个指针 遍历链表，逐次反转节点指向：prev：指向 已反转部分 的头节点（初始为NULL）。curr：指向 当前待反转节点（初始为head）。next：临时保存curr的下一个节点（避免反转后断链）。
简单来做，我将其命名为s1,s2,s3了。
基本结构是这样的，接下来我将结合代码来讲解:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode node; struct ListNode* reverseList(struct ListNode* head) { node * s1=NULL; node *s2=head,*s3=NULL; if(s2) { s3=s2->next; } while(s2) { s2->next=s1; s1=s2; s2=s3; if(s3) { s3=s3->next; } } return s1; }讲解：
图示：
根据上图：我们可知代码 if (s3) { s3 = s3->next; 的原因了：
while (s2) { // 循环条件：当前待反转节点 s2 不为 NULL（遍历完所有节点后终止）
// 步骤1：反转当前节点 s2 的指向（指向已反转部分的头节点 s1）
s2->next = s1;
// 步骤2：s1 后移到 s2（已反转部分的长度+1，s1 成为新的“已反转头节点”）
s1 = s2;
// 步骤3：s2 后移到 s3（继续处理下一个待反转节点）
s2 = s3;
// 步骤4：若 s3 不为空，s3 后移到下一个节点（为下次循环做准备）
if (s3) {
s3 = s3->next;
}
}
return s1; // 循环结束后，s1 指向原链表的尾节点（即新链表的头节点）
总结
以上就是今天要讲的内容，本篇文章涉及的知识点为： 讲解双向链表概念与结构，实现双向链表，顺序表与链表的分析，链表算法题等知识的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，接下来的内容我会很快更新。
