引言
链表是数据结构入门阶段的核心知识点，其结构灵活多变，可分为单向/双向、带头/不带头、循环/不循环等多种形式。本文先系统梳理链表的分类，帮助大家建立完整认知，再重点讲解带头双向循环链表这一高效实用的结构。从节点定义、哨兵位初始化到完整代码实现，一步步带你理解双向链表的设计思想。
一、链表的分类基础
链表的结构组合多样，主要可以从以下三个维度进行划分：
1. 单向或双向
双向链表包含前驱节点和后继节点指针。不仅能找到当前节点的下一个节点，还可以找到上一个节点，遍历更加灵活方便。
2. 带头或不带头
带头链表中的头节点不存储有效数据，仅用于站岗放哨，通常称为'哨兵位'。在之前的单链表学习中，有时会将第一个节点表述为头节点，这种称呼不够严谨，仅为方便理解。
3. 循环或不循环
循环链表的尾节点不会指向空，而是指向了第一个节点，形成闭环。
虽然存在多种链表结构，但实际开发中最常用的其实是两种：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）。接下来我们重点学习双向链表。
二、双向链表定义
双向链表由一个个节点组成，每个节点包含三个部分：
- 前驱指针：指向前一个元素的指针
- 后继指针：指向后一个元素的指针
- 数值域：存储元素
typedef struct ListNode {
struct ListNode* prev; // 前驱
struct ListNode* next; // 后继
LDataType data;
} ListNode;
三、哨兵位头节点初始化
双向链表中哨兵位的头节点需要初始化。数据可以随便给个不用的值，然后前驱和后继指针都指向自己即可。
void LTInit(ListNode** pphead) {
ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
if (ph == NULL) {
printf("开辟失败!\n");
exit(-1);
}
*pphead = ph;
(*pphead)->data = -1; // 看个人习惯
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
四、代码实现
以下是完整的文件结构展示，包括头文件、源文件和测试文件。
1. List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LDataType;
typedef struct ListNode {
struct ListNode* prev;
struct ListNode* next;
LDataType data;
} ListNode;
// 初始化
void LTInit(ListNode** head);
2. List.c
#include "List.h"
// 初始化
void LTInit(ListNode** pphead) {
ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
if (ph == NULL) {
printf("开辟失败!\n");
exit(-1);
}
*pphead = ph;
(*pphead)->data = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
3. test.c
#include "List.h"
int main() {
ListNode* head;
LTInit(&head);
return 0;
}
通过上述步骤，我们完成了带头双向循环链表的基本初始化逻辑。数据结构的学习重在理解结构本质与设计思路，每一步都要夯实基础，把每一个知识点学透、每一段代码写稳。