双链表概述
本篇介绍双链表,是一种链表数据结构。它的每个节点除了包含数据域(用于存储数据)之外,还包含两个指针域,一个指向前一个节点(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 节点。




