数据结构实战：双向链表实现与算法解析

在之前的讲解中，我们建立了双向链表的基础结构。今天我们将深入实现双向链表的剩余核心操作，并对比顺序表与链表的区别，最后通过两道经典算法题巩固理解。

一、实现双向链表

1. 查找操作

双向链表的查找逻辑与单链表类似，但利用 prev 指针可以反向遍历。这里我们采用从头结点开始正向遍历的方式。

函数原型：

ListNode* LTFind(ListNode* h, type x);

核心实现：

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

注意： 循环条件 p != h 确保了不会越过尾结点回到头结点，形成死循环。找到目标直接返回节点指针，未找到则返回 NULL。

2. 指定位置插入

双向链表的插入比单链表更灵活，分为在指定节点后插入和在指定节点前插入。

在指定节点之后插入

这是最基础的操作，关键在于保存后继节点指针，防止断链。

函数原型：

void LTInsert(ListNode* pos, type x);

核心实现：

void LTInsert(ListNode* pos, type x) {
    assert(pos); // 确保 pos 有效
    ListNode* p = pos->next;       // 先保存原后继
    ListNode* newnode = LTcreat(x);
    
    // 调整指针关系（4 步）
    pos->next = newnode;         // 1. 新节点接在 pos 后
    newnode->prev = pos;         // 2. 新节点指回 pos
    newnode->next = p;           // 3. 新节点指向原后继
    p->prev = newnode;           // 4. 原后继指回新节点
}

细节： 这里的顺序不能乱。必须先保存 pos->next 给 p，否则一旦执行 pos->next = newnode，原链表后半部分就找不到了。

在指定节点之前插入

这需要先找到 pos 的前驱节点，然后再调用上述逻辑或手动调整指针。

函数原型：

void LTInsertfront(ListNode* h, ListNode* pos, type x);

核心实现：

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; // 没找到 pos
    }
    
    ListNode* newnode = LTcreat(x);
    ListNode* pr = p->next;      // 保存原后继（即 pos）
    
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

3. 指定位置删除

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

函数原型：

void LTErase(ListNode* pos);

核心实现：

void LTErase(ListNode* pos) {
    assert(pos);
    ListNode* p = pos->prev;     // 获取前驱
    
    p->next = pos->next;         // 前驱跳过 pos
    pos->next->prev = p;         // 后继指回前驱
    
    free(pos);                   // 释放内存
    pos = NULL;                  // 置空局部指针
}

边界处理： 如果 pos 是头结点或尾结点，由于是循环链表，逻辑依然适用，因为 prev 和 next 始终存在且指向有效节点。

4. 完整代码参考

为了便于测试和理解，这里整合了初始化、增删改查及销毁的完整代码。

头文件 (1.h)

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

typedef int type;

typedef struct ListNode {
    type data;
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

// 声明所有接口
void LTInit(ListNode** h);
void LTPushBack(ListNode* h, type x);
ListNode* LTcreat(type x);
void LTPushFront(ListNode* h, type x);
void LTPopBack(ListNode* h);
void LTPopFront(ListNode* h);
void LTDestroy(ListNode* h); // 修正拼写
void print(ListNode* h);
ListNode* LTFind(ListNode* h, type x);
void LTInsert(ListNode* pos, type x);
void LTInsertfront(ListNode* h, ListNode* pos, type x);
void LTErase(ListNode* pos);
bool LTEmpty(ListNode* phead);

实现文件 (1.c)

#include "1.h"

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* LTcreat(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;
}

void LTPushBack(ListNode* h, type x) {
    ListNode* p = LTcreat(x);
    p->next = h;
    p->prev = h->prev;
    h->prev->next = p;
    h->prev = p;
}

void LTPushFront(ListNode* h, type x) {
    ListNode* p = LTcreat(x);
    p->next = h->next;
    p->prev = h;
    h->next->prev = p;
    h->next = p;
}

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

void LTPopBack(ListNode* h) {
    if (LTEmpty(h)) {
        return;
    }
    ListNode* p = h->prev;
    h->prev = p->prev;
    p->prev->next = h;
    free(p);
}

void LTPopFront(ListNode* h) {
    if (LTEmpty(h)) {
        printf("链表为空，无法头删\n");
        return;
    }
    ListNode* p = h->next;
    h->next = p->next;
    p->next->prev = h;
    free(p);
}

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

void print(ListNode* h) {
    if (LTEmpty(h)) {
        return;
    }
    ListNode* p = h->next;
    while (p != h) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

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

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

void LTInsertfront(ListNode* h, ListNode* pos, type x) {
    if (LTEmpty(h)) {
        return;
    }
    ListNode* p = h;
    while (p->next != h) {
        if (p->next == pos) {
            break;
        }
        p = p->next;
    }
    if (p->next == h) {
        return;
    }
    ListNode* newnode = LTcreat(x);
    ListNode* pr = p->next;
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

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

测试主程序 (main.c)

#include "1.h"

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

int main() {
    test();
    return 0;
}

双向链表示意图

二、顺序表与链表的分析

在实际开发中，选择顺序表还是链表取决于具体场景。下图直观展示了两者的异同：

顺序表与链表对比图

相同点

逻辑结构：均为线性表，元素一对一排列。
基本操作：都支持插入、删除、查找、遍历。
数据类型：均可存储任意类型数据。

不同点（核心差异）

存储方式：顺序表连续存储，链表离散存储。
访问效率：顺序表随机访问 O(1)，链表遍历 O(n)。
空间开销：顺序表需预留空间，链表每个节点多存指针。

关键结论

顺序表：适合频繁随机访问、数据量相对固定的场景（如配置表）。
链表：适合频繁插入删除、数据量动态变化的场景（如任务队列）。

三、链表算法题

1. 移除链表元素

题目描述：给定链表头结点和值 val，移除所有值为 val 的节点。

思路：我们可以创建一个新链表，只保留不等于 val 的节点。虽然这种方法没有原地释放内存，但在算法竞赛中通常可接受，且逻辑清晰。

代码实现：

struct ListNode* removeElements(struct ListNode* head, int val) {
    Node *h = NULL, *pr = NULL;
    Node *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，避免野指针。

2. 反转链表

题目描述：反转一个单链表。

思路：使用三个指针迭代法，时间复杂度 O(n)，空间复杂度 O(1)。这是面试中的高频考点。

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

代码实现：

struct ListNode* reverseList(struct ListNode* head) {
    node *s1 = NULL;
    node *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，然后三个指针依次向后移动，直到 s2 为空，此时 s1 即为新的头结点。