数据结构：链表分类详解与双向链表初始化实现

前言

链表作为数据结构的核心基石，其灵活性体现在多种组合形式上。本文将系统梳理链表的分类体系，并重点剖析带头双向循环链表的设计思想与初始化实现，为后续操作打下基础。

链表分类概览

链表结构主要由三个维度决定，理论上可组合出八种形态：

1. 指针方向

分为单向与双向。双向链表每个节点包含前驱和后继两个指针，既能向后遍历也能向前回溯，灵活性更高。

2. 头节点设计

分为带头与不带头。带头链表中的头节点不存储有效数据，仅作为哨兵位存在，用于简化边界处理逻辑。

3. 连接方式

分为循环与非循环。循环链表的尾节点指向头节点，形成闭环，遍历时无需特殊判断结束条件。

实际开发中，单链表（不带头单向非循环）和双向链表（带头双向循环）最为常用。

双向链表核心结构

双向链表节点由三部分组成：前驱指针、后继指针和数据域。

#include <stdio.h>
#include <stdlib.h>

typedef int LDataType;

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