数据结构入门：带头双向循环链表实现

双链表概述

本篇介绍双链表，是一种链表数据结构。它的每个节点除了包含数据域（用于存储数据）之外，还包含两个指针域，一个指向前一个节点（prev），另一个指向后一个节点（next）。

1. 双链表接口实现

本次实现的是带头双向循环的链表。不仅有指向前一个节点的 prev 指针，还有指向下一个节点的 next 指针。最后一个节点有指向开头的指针 next，开头的节点有指向结尾的指针 prev，形成循环。

双链表定义

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

为便于修改数据类型，建议统一使用 typedef 定义。

1.1 双链表节点创建

LTNode* BuyListNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed");
        return NULL;
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

1.2 双链表初始化

LTNode* LTInit() {
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

通常会在主函数创建一个指针接收初始化指针。prev 和 next 都指向自己形成循环，也就是一个哨兵位，间接规避了链表为空的情况，可以直接 PushBack 节点。