数据结构：双向链表原理与 C 语言实现

核心操作实现

1. 节点申请与初始化

申请新节点时，需要分配内存并检查是否成功。对于带头结点的循环链表，新节点初始化时可以先自环，或者在插入时再调整。

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

LTNode* LTInit() {
    // 创建一个哨兵节点，数据可以是任意值，这里用 -1 示意
    LTNode* phead = LTBuyNode(-1);
    return phead;
}

2. 销毁链表

销毁时需要遍历所有有效节点释放内存，最后释放头结点。注意使用二级指针或返回值来更新外部指针，防止野指针。

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

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

头插

逻辑与尾插类似，只是方向相反。先连接新节点与旧头节点，再连接新节点与头结点。

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

指定位置后插入

在 pos 节点之后插入，只需将 pos 的后继节点作为桥梁即可。

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

4. 删除操作

尾删与头删

删除时需确保链表非空。删除后记得将断开节点的指针置为 NULL，避免悬垂指针。

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 LTErase(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

5. 辅助功能

判空

由于是循环链表，当 next 指向自己时，说明只有头结点，即为空。

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

顺序表与链表对比

通过上述分析可以看出，双向链表在插入和删除操作上具有显著优势，适合对数据变动频繁的场景；而顺序表则在访问效率上更胜一筹。实际开发中，应根据具体需求选择合适的结构。