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

这里需要先遍历找到 pos 的前驱 p，然后复用'在 p 之后插入'的逻辑。

3. 指定位置删除

删除节点需修改前驱的 next 和后继的 prev，并释放内存。边界处理尤为重要。

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

注意：释放内存后务必将局部指针置空，避免悬垂指针。断言检查 pos 非空是防止崩溃的第一道防线。

4. 完整代码示例

以下是包含测试逻辑的完整工程结构，整合了头文件、实现与主函数。

list.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.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 LTDestory(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);

list.c

#include"list.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 LTDestory(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"list.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);
    
    LTDestory(h);
}

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

二、顺序表与链表的分析

相同点

两者均为线性表，逻辑结构一致，数据元素呈一对一关系。都支持插入、删除、查找、遍历等基本操作，且可存储同类型数据。

不同点（核心差异）

• 存储方式：顺序表占用连续内存空间，链表通过指针链接离散节点。
• 访问效率：顺序表支持随机访问（O(1)），链表仅支持顺序访问（O(n)）。
• 增删效率：顺序表插入删除需移动大量元素（O(n)），链表仅需修改指针（O(1)，已知位置）。
• 空间管理：顺序表需预分配空间，易浪费或溢出；链表动态分配，灵活但开销稍大。

关键结论

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

三、链表算法题

1. 移除链表元素

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

思路：创建新链表，遍历原链表，将不等于 val 的节点依次拼接到新链表尾部。虽然未释放原节点，但在 OJ 环境中通常可接受，重点在于掌握指针拼接逻辑。

typedef struct ListNode Node;
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)。

思路：使用三个指针 prev（已反转部分）、curr（当前节点）、next（暂存后继）。每次循环将 curr 指向 prev，然后三者同步后移。

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

此方法避免了递归带来的栈溢出风险，且无需额外空间，是面试中的高频考点。

总结

本章完成了双向链表的完整实现，包括查找、插入、删除等核心功能，并对比了其与顺序表的优劣。结合移除元素与反转链表两道算法题，重点训练了指针操作的熟练度与边界条件的处理能力。掌握这些基础是进阶复杂数据结构的前提。