7、双向链表的插入与删除：头插法、尾插法、指定位置插入与删除

双向链表，说白了就是每个节点多了一根“回头箭”。

单向链表只能从头走到尾，想往回走？没门。双向链表每个节点都存了前驱和后继两个指针，往前能走，往后也能走。我刚开始学的时候觉得这玩意儿多此一举，直到有一次做项目，需要在链表中频繁地删除节点——用单向链表删一个节点，你得从头遍历找到它的前一个节点，效率低得让人抓狂。换成双向链表，直接通过前驱指针就搞定了，代码写起来也清爽很多。

7.1 双向链表的结构定义

先看看节点长什么样：

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prev;     // 前驱指针
    struct DNode *next;     // 后继指针
} DNode, *DLinkList;

嗯，比单向链表多了一个 prev 指针。这个指针指向谁？指向链表中的前一个节点。头节点的 prev 一般是 NULL，尾节点的 next 是 NULL。

核心区别一句话：单向链表只有一条路，双向链表有两条路。代价是每个节点多占一个指针的内存，换来的是操作上的灵活性。

7.2 头插法：新节点永远插在头部

头插法，就是把新节点塞到链表的最前面。我习惯用头插法来快速构建一个链表，尤其是测试的时候，几行代码就能生成一串数据。

int insertAtHead(DLinkList *L, int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (!newNode) return -1;  // 内存分配失败
    
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *L;
    
    if (*L != NULL) {
        (*L)->prev = newNode;  // 老头节点的prev指向新节点
    }
    *L = newNode;  // 新节点成为头节点
    return 0;
}

这里有个细节：一定要判断原链表是否为空。如果原链表是空的，(*L)->prev = newNode 这行代码就会崩溃。我曾经在项目里犯过这个错，调试了半天才发现是空链表的问题。

小技巧：头插法插入的顺序和最终链表顺序是相反的。如果你想让链表顺序和输入顺序一致，用尾插法。

7.3 尾插法：新节点永远插在尾部

尾插法需要先找到链表的尾巴，然后把新节点接上去。如果链表很长，每次都从头遍历到尾，效率是 O(n)。我一般会维护一个尾指针，这样尾插就是 O(1) 了。

int insertAtTail(DLinkList *L, int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (!newNode) return -1;
    
    newNode->data = data;
    newNode->next = NULL;
    
    if (*L == NULL) {
        // 空链表，新节点就是头节点
        newNode->prev = NULL;
        *L = newNode;
        return 0;
    }
    
    DNode *p = *L;
    while (p->next != NULL) {
        p = p->next;  // 遍历到尾部
    }
    p->next = newNode;
    newNode->prev = p;
    return 0;
}

你想想看，如果每次插入都要遍历，数据量大了之后性能会很难看。所以实际项目中，我通常会在链表结构体里加一个 tail 指针，专门指向尾节点。

7.4 指定位置插入

指定位置插入，核心是找到第 i 个节点。找到之后，把新节点“塞”进去。双向链表的好处在这里就体现出来了——你不需要记住前一个节点是谁，因为每个节点都自带前驱指针。

int insertAtPos(DLinkList *L, int data, int pos) {
    if (pos < 1) return -1;  // 位置不合法
    
    if (pos == 1) {
        return insertAtHead(L, data);  // 头插法复用
    }
    
    DNode *p = *L;
    int count = 1;
    while (p != NULL && count < pos) {
        p = p->next;
        count++;
    }
    
    if (p == NULL) {
        // 位置超出链表长度，可以报错或者尾插
        return -1;
    }
    
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (!newNode) return -1;
    newNode->data = data;
    
    // 核心：四步连接
    newNode->prev = p->prev;
    newNode->next = p;
    p->prev->next = newNode;
    p->prev = newNode;
    
    return 0;
}

注意：上面代码中 p->prev->next = newNode 这行，如果 p 是头节点，p->prev 是 NULL，就会出问题。所以实际写代码时，要单独处理插入位置是头节点的情况。我上面的代码已经通过 pos==1 调用了头插法来规避这个问题。

7.5 删除操作：头删、尾删、指定位置删除

删除操作比插入稍微简单一点，因为不需要分配内存，只需要释放内存。但指针操作一个都不能少。

头删

int deleteHead(DLinkList *L) {
    if (*L == NULL) return -1;
    
    DNode *p = *L;
    *L = p->next;
    if (*L != NULL) {
        (*L)->prev = NULL;
    }
    free(p);
    return 0;
}

尾删

int deleteTail(DLinkList *L) {
    if (*L == NULL) return -1;
    
    DNode *p = *L;
    while (p->next != NULL) {
        p = p->next;
    }
    
    if (p->prev == NULL) {
        // 只有一个节点
        *L = NULL;
    } else {
        p->prev->next = NULL;
    }
    free(p);
    return 0;
}

指定位置删除

int deleteAtPos(DLinkList *L, int pos) {
    if (*L == NULL || pos < 1) return -1;
    
    DNode *p = *L;
    int count = 1;
    while (p != NULL && count < pos) {
        p = p->next;
        count++;
    }
    
    if (p == NULL) return -1;  // 位置不存在
    
    if (p->prev == NULL) {
        // 删除头节点
        *L = p->next;
        if (*L != NULL) (*L)->prev = NULL;
    } else {
        p->prev->next = p->next;
    }
    
    if (p->next != NULL) {
        p->next->prev = p->prev;
    }
    
    free(p);
    return 0;
}

避坑指南：我曾经在删除节点后忘记把被删节点的 next 和 prev 置 NULL，结果后续代码误用了这个已释放的节点，导致野指针崩溃。free 之后，最好把指针也置为 NULL，虽然不能完全避免问题，但至少能让你在调试时更容易发现错误。

7.6 双向链表操作流程图

下面这张图把双向链表的核心操作串起来了，你看一遍就能理解整体逻辑：

双向链表核心操作流程 头节点 中间节点 中间节点 尾节点 头插法：新节点插入头节点之前，更新头指针 尾插法：新节点插入尾节点之后，更新尾指针 指定位置插入（以插入到节点2之前为例） 插入前： 节点1 节点2 节点3 插入后： 节点1 新节点 节点2 节点3 删除操作要点 • 头删：释放头节点，更新头指针，新头节点的 prev 置 NULL • 尾删：释放尾节点，前一个节点的 next 置 NULL • 指定位置删除：将被删节点的前后节点直接连接，然后释放

7.7 总结一下

双向链表的插入和删除，核心就是处理好四个指针：新节点的 prev 和 next，以及前后两个节点的 prev 和 next。顺序搞错了，链表就断了。

我个人习惯在写代码之前，先在纸上画一下指针的指向变化。画清楚了再写代码，基本一次过。如果你在调试时发现链表乱了，别急着改代码，先画图，往往一眼就能看出问题。

嗯，双向链表的内容就到这里。代码看着多，但核心逻辑就那么几条。多写几遍，自然就熟了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →