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

3. 指定位置删除

删除时需断开前驱和后继的连接，释放内存，并处理边界空指针风险。

void LTErase(ListNode* pos) {
    assert(pos);
    ListNode* p = pos->prev;
    p->next = pos->next;           // 前驱跳过当前节点
    pos->next->prev = p;           // 后继指向前驱
    free(pos);
    pos = NULL;                    // 防止野指针
}

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 && p->next != pos) {
        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;
}

二、顺序表与链表分析

两者均为线性表，但存储方式决定了适用场景。

结论：若场景侧重频繁随机访问且数据量固定（如学生信息表），首选顺序表；若侧重频繁增删且数据动态变化（如队列、栈实现），链表更优。

三、链表算法实战

1. 移除链表元素

题目要求移除所有值为 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) { h = p; pr = p; } // 首节点
            else { pr->next = p; pr = p; } // 拼接后续
        }
        p = p->next;
    }
    if (pr) pr->next = NULL; // 尾节点置空
    return h;
}

关键点：遍历时需保留新链表的尾指针 pr，并在循环结束后将其 next 置为 NULL，避免残留野指针。

2. 反转链表

反转链表的核心在于改变节点的指向。使用三个指针迭代是最稳妥的方法，时间复杂度 O(n)，空间复杂度 O(1)。

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

执行流程：每轮循环中，先将当前节点 s2 的 next 指向 s1，然后整体后移。注意 s3 必须在修改 s2->next 之前保存，否则链表会断裂。

总结

双向链表的实现重点在于指针维护的准确性，尤其是插入和删除时的前后关联。相比顺序表，它在动态操作上更具优势，但牺牲了随机访问性能。掌握这两类结构的特性，配合指针操作的算法训练，能更好地应对底层数据结构相关的面试与工程问题。