链表分类详解与带头双向循环链表初始化实现

链表作为数据结构的基础，形态多样。本文梳理常见分类，并重点讲解带头双向循环链表的初始化逻辑，帮助大家建立完整认知。

链表的结构分类

链表结构灵活，总共能组合出多种形态，核心维度主要有三个：

单向或双向

双向链表包含前驱节点和后继节点指针。相比单向链表，它不仅能找到当前节点的下一个节点，还能方便地访问上一个节点。

带头或不带头

带头链表中的头节点不存储有效数据，仅用于站岗放哨，我们称之为'哨兵位'。在之前的单链表学习中，有时会将第一个节点表述为头节点，其实这种称呼并不严谨，为了区分，我们将带头链的辅助节点称为哨兵位。

循环或不循环

循环链表的尾节点不会指向空，而是指向了第一个节点，形成闭环。

虽然存在多种组合，但实际开发中最常用的还是两种：单链表（不带头单向不循环）和双向链表（带头双向循环链表）。接下来我们重点学习后者。

双向链表定义

双向链表由一个个节点组成，每个节点包含三个部分：

• 前驱指针：指向前一个元素的指针
• 后继指针：指向后一个元素的指针
• 数值域：存储元素数据

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;
}

代码实现

下面展示完整的文件结构，包含头文件、源文件及测试入口。

List.h