数据结构：双向链表详解与实现

核心实现细节

申请新节点

分配内存时务必检查是否成功，并初始化指针指向自身以形成闭环。

LTNode* LTBuyNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode; // 初始化为自环
    return newnode;
}

初始化与销毁

初始化直接返回哨兵节点，销毁时记得释放哨兵本身并将头指针置空。

LTNode* LTInit() {
    LTNode* phead = LTBuyNode(-1); // -1 仅为哨兵占位符
    return phead;
}

LTNode* LTDestroy(LTNode* phead) {
    assert(phead != NULL);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead); // 最后释放哨兵
    return NULL;
}

插入操作

插入是双向链表最容易出错的地方，指针修改顺序至关重要。如果先改了后继，再改前驱，可能会丢失原节点地址导致断链或内存泄漏。

尾插逻辑：

1. 新节点的前驱指向当前尾节点（哨兵的前驱）。
2. 新节点的后继指向哨兵。
3. 原尾节点的后继指向新节点。
4. 哨兵的前驱指向新节点。

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

头插逻辑： 同理，注意不要覆盖 phead->next 的地址。

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

删除操作

删除时同样要注意顺序，先断开连接，再释放内存。

尾删： 直接操作哨兵的前驱节点即可。

void LTPopBack(LTNode* phead) {
    assert(!LTEmpty(phead));
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

头删：

void LTPopFront(LTNode* phead) {
    assert(!LTEmpty(phead));
    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

任意位置插入与删除：

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

void LTErase(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

辅助功能

判空只需判断头节点的后继是否指向自己。打印则遍历一圈即可。

bool LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead;
}

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

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

顺序表与链表分析

通过对比表格可以更直观地理解两者的差异：

在实际开发中，若对查询效率要求高且数据量稳定，首选顺序表；若数据变动频繁且位置不确定，链表则是更好的选择。