双向链表原理与 C 语言实现

双向链表

链表分类包括带头/不带头、单向/双向、循环/非循环等 8 种。最常用的是单链表（不带头单向不循环）和双向链表（带头双向循环链表）。

双链表特点：

• 有头节点（哨兵位）
• 包含后继指针 (next) 和前驱指针 (prev)
• 为空时，仅存在一个指向自身的哨兵位

1. 申请节点

LTNode* LTBuyNode(LTDataType x) {
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL) {
        perror("malloc fail");
        exit(1);
    }
    node->data = x;
    node->next = node->prev = node;
    return node;
}

2. 链表初始化

创建哨兵位作为头结点。

void LTInit(LTNode** pphead) {
    *pphead = LTBuyNode(-1);
}

3. 尾插

在头结点和最后一个数据节点之间插入新节点。

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev->next = newnode;
    phead->prev = newnode;
}

4. 打印链表

从 phead->next 开始遍历，直到回到 phead。

void LTPrint(LTNode* phead) {
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    ();
}