双向链表实现与核心算法解析

双向链表概念与结构

双向链表是一种链式存储的数据结构，每个节点包含两个指针：一个指向前驱节点（prev），一个指向后继节点（next），同时包含数据域（data）存储数据。这种结构允许双向遍历（从头到尾或从尾到头），并支持更灵活的插入、删除操作，但相比单链表会增加一定的空间开销。

我们这里采用的是带头双向循环链表。它兼具'头节点''双向指针''循环结构'三大特性，是应用最广泛的双向链表类型。其结构稳定、边界处理简单，支持高效的插入、删除和双向遍历操作。

关于头节点

带头链表中的头节点不存储有效数据，只用来简化边界操作（如插入/删除首节点时无需特殊判断）。在单链表学习中有时会把第一个节点表述为头节点，其实严谨定义下，头节点是链表中第一个节点但不存储有效数据，核心价值是简化边界操作。

双向链表结构定义

根据单向链表的知识，我们可以扩展出双向链表的结构：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int type;

typedef struct ListNode {
    type data;              // 数据域
    struct ListNode* prev;  // 前驱指针
    struct ListNode* next;  // 后继指针
} ListNode;

实现双向链表

1. 初始化

我们在双向链表中头节点（哨兵位）是需要初始化的。数据域可以存任意值，前驱指针和后继指针都指向自己即可，形成空循环状态。

void LTInit(ListNode** h) {
    ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
    if (ph == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    *h = ph;
    (*h)->data = -1;      // 哨兵位数据
    (*h)->next = *h;      // 指向自己
    (*h)->prev = *h;      // 指向自己
}

这里要注意，传入的是二级指针 ListNode** h，因为我们需要修改外部传入的头指针变量本身。

2. 创建节点辅助函数

为了复用逻辑，我们封装一个创建节点的函数。无论是初始化哨兵位还是创建普通有效节点，都可以用这个逻辑。

ListNode* LTCreate(type x) {
    ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
    if (ph == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    ph->data = x;
    ph->next = ph;  // 自指
    ph->prev = ph;  // 自指
    return ph;
}

3. 尾插操作

对于带头节点的双向循环链表，尾插可直接通过头节点的 prev 指针定位尾节点，无需遍历链表，时间复杂度为 O(1)。

void LTPushBack(ListNode* h, type x) {
    ListNode* p = LTCreate(x);  // 创建新节点
    
    // 关键步骤：调整指针关系
    p->next = h;                // 新节点 next 指向头节点
    p->prev = h->prev;          // 新节点 prev 指向原尾节点
    h->prev->next = p;          // 原尾节点 next 指向新节点
    h->prev = p;                // 头节点 prev 更新为新节点
}

注意指针顺序：一定要先保存好原尾节点的信息，否则一旦修改了 h->prev，就找不到原来的尾节点了，导致链表断裂。

4. 头插操作

头插是将新节点插入到头节点之后、第一个有效节点之前的位置。

void LTPushFront(ListNode* h, type x) {
    ListNode* p = LTCreate(x);
    
    p->next = h->next;  // 新节点 next 指向原第一个有效节点
    p->prev = h;        // 新节点 prev 指向头节点
    h->next->prev = p;  // 原第一个有效节点 prev 指向新节点
    h->next = p;        // 头节点 next 指向新节点
}

如果是空链表（h->next == h），上述逻辑依然成立，因为此时 h->next 就是 h 自己，逻辑上等同于插入到尾部再调整，但在循环结构中直接视为头部插入。

5. 判空与尾删

删除操作前必须先判空，避免对空链表进行操作导致崩溃。

bool LTEmpty(ListNode* phead) {
    assert(phead);
    return phead->next == phead;  // 头节点 next 指向自身即为空
}

void LTPopBack(ListNode* h) {
    if (LTEmpty(h)) {
        return;
    }
    ListNode* p = h->prev;  // 获取尾节点
    
    // 修复指针
    h->prev = p->prev;      // 头节点 prev 指向新尾节点
    p->prev->next = h;      // 新尾节点 next 指向头节点
    
    free(p);                // 释放内存
}

这里利用了双向循环的特性，h->prev 直接指向尾节点，所以不需要遍历，效率很高。

6. 头删操作

删除链表的第一个有效节点（即头节点后的第一个节点）。

void LTPopFront(ListNode* h) {
    if (LTEmpty(h)) {
        printf("链表为空，无法头删\n");
        return;
    }
    ListNode* p = h->next;  // 待删除节点
    
    h->next = p->next;      // 头节点 next 跳过 p
    p->next->prev = h;      // p 的后继 prev 指向头节点
    
    free(p);                // 释放内存
}

7. 销毁

销毁需遍历所有节点并逐个释放内存，最后释放头结点空间。

void LTDestroy(ListNode* h) {
    if (LTEmpty(h)) {
        free(h);
        return;
    }
    ListNode* p = h->next;
    while (p != h) {
        ListNode* pr = p;
        p = p->next;
        free(pr);
    }
    free(h);
    h = NULL;  // 置空防止悬空指针
}

8. 查找与插入删除

查找

利用临时指针遍历，找到目标返回节点，未找到返回 NULL。

ListNode* LTFind(ListNode* h, type x) {
    if (LTEmpty(h)) {
        return NULL;
    }
    ListNode* p = h->next;
    while (p != h) {
        if (p->data == x) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

指定位置后插入

在指定节点 pos 之后插入新节点。

void LTInsert(ListNode* pos, type x) {
    assert(pos);
    ListNode* p = pos->next;
    ListNode* newnode = LTCreate(x);
    
    pos->next = newnode;
    newnode->prev = pos;
    newnode->next = p;
    p->prev = newnode;
}

指定位置前插入

在指定节点 pos 的前驱位置插入新节点。

void LTInsertFront(ListNode* h, ListNode* pos, type x) {
    if (LTEmpty(h)) {
        return;
    }
    ListNode* p = h;
    // 找到 pos 的前驱
    while (p->next != h) {
        if (p->next == pos) {
            break;
        }
        p = p->next;
    }
    if (p->next == h) {
        return; // 没找到
    }
    
    ListNode* newnode = LTCreate(x);
    ListNode* pr = p->next;
    
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

指定位置删除

删除节点需修改前驱节点的 next 和后继节点的 prev，并释放被删节点内存。

void LTErase(ListNode* pos) {
    assert(pos);
    ListNode* p = pos->prev;
    
    p->next = pos->next;
    pos->next->prev = p;
    
    free(pos);
    pos = NULL; // 局部指针置空
}

测试代码整合

为了方便验证，我们将接口整合到一个测试流程中：

void test() {
    ListNode* h;
    LTInit(&h);
    
    LTPushBack(h, 10);
    LTPushBack(h, 15);
    LTPushBack(h, 111);
    print(h); // 输出：10 15 111
    
    LTPushFront(h, 2);
    LTPushFront(h, 12);
    print(h); // 输出：12 2 10 15 111
    
    LTPopBack(h);
    print(h); // 输出：12 2 10 15
    
    LTPopFront(h);
    print(h); // 输出：2 10 15
    
    ListNode* p = LTFind(h, 10);
    LTInsert(p, 100);
    LTInsert(p, 200);
    print(h); // 输出：2 10 200 100 15
    
    LTErase(p);
    print(h); // 输出：2 200 100 15
    
    LTDestroy(h);
}

顺序表与链表的分析

特性	顺序表	链表
逻辑结构	线性表，一对一顺序关系	线性表，一对一顺序关系
存储方式	连续内存空间	离散内存空间，通过指针连接
随机访问	O(1)，支持下标访问	O(n)，需遍历
插入/删除	平均 O(n)，涉及大量移动	平均 O(1)，仅需修改指针
内存占用	静态分配或动态扩容，可能浪费	按需分配，无额外空间浪费
适用场景	频繁随机访问、数据量固定	频繁插入删除、数据量动态变化

关键结论：顺序表适合存储学生信息表等固定场景；链表适合实现队列、栈等动态场景。

链表算法题实战

一、移除链表元素

题目要求移除值为 val 的节点，返回新的头结点。

思路：创建一个新链表，存储符合要求的节点。虽然不释放原链表空间，但在 OJ 解题中通常可接受，且逻辑清晰。

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *h = NULL, *pr = NULL;
    struct ListNode *p = head;
    
    while (p) {
        if (p->val != val) {
            if (h == NULL) {
                h = p;
                pr = p;
            } else {
                pr->next = p;
                pr = p;
            }
        }
        p = p->next;
    }
    
    if (pr) {
        pr->next = NULL; // 断开旧链接，防止野指针
    }
    return h;
}

要点：遍历结束后，务必将新链表尾节点的 next 置为 NULL，避免残留原链表后续节点导致死循环或野指针风险。

二、反转链表

使用三个指针迭代法，时间 O(n)，空间 O(1)。

• s1：指向已反转部分的头节点（初始为 NULL）
• s2：指向当前待反转节点（初始为 head）
• s3：临时保存 s2 的下一个节点

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *s1 = NULL;
    struct ListNode *s2 = head, *s3 = NULL;
    
    if (s2) {
        s3 = s2->next;
    }
    
    while (s2) {
        s2->next = s1;  // 反转指向
        s1 = s2;        // s1 后移
        s2 = s3;        // s2 后移
        if (s3) {
            s3 = s3->next; // s3 后移
        }
    }
    return s1;
}

图解逻辑：每次循环将 s2 的 next 指向 s1，然后三者同步向后移动。循环结束后，s1 指向原链表的尾节点，即新链表的头节点。

以上涵盖了双向链表的核心实现细节及常见算法题解法，重点在于理解指针操作的顺序和内存管理的安全性。