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

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;                // 置空局部指针
}

注意：assert(pos) 确保传入的节点有效，避免野指针访问。

二、完整代码结构展示

为了便于测试和理解，我们将头文件、实现文件和主测试程序分开整理。

头文件 (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 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);

实现文件 (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 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"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); 
    
    LTDestory(h); 
} 

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

三、顺序表与链表对比

在实际开发中，选择顺序表还是链表取决于具体场景。

相同点：

1. 逻辑结构一致：均为线性表，元素一对一排列。
2. 核心操作相同：都支持插入、删除、查找、遍历。
3. 数据类型：均可存储同类型数据。

不同点：

1. 存储方式：顺序表连续存储，链表离散存储。
2. 访问效率：顺序表支持随机访问（O(1)），链表需遍历（O(n)）。
3. 增删效率：顺序表涉及大量移动，链表只需修改指针。

结论：

• 顺序表：适合频繁随机访问、数据量相对固定的场景。
• 链表：适合频繁插入删除、数据量动态变化的场景。

四、链表算法题实战

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==NULL) { 
                h=p; 
                pr=p; 
            } else { 
                pr->next=p; 
                pr=p; 
            } 
        } 
        p=p->next; 
    } 
    if(pr) pr->next=NULL; 
    return h; 
}

关键点： 遍历结束后，务必将新链表的尾节点 next 置为 NULL，防止残留旧指针导致野指针问题。

2. 反转链表

将单链表逆序，例如 1->2->3 变为 3->2->1。

解题思路： 使用三个指针进行迭代，时间复杂度 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; 
        s2=s3; 
        if(s3) { 
            s3=s3->next; 
        } 
    } 
    return s1; 
}

执行流程： 每次循环将 s2 指向 s1，然后三者依次后移。当 s2 为空时，s1 即为新的头节点。

以上就是双向链表的核心实现与相关算法分析。掌握指针的正确流转是理解链表的关键，建议多动手调试代码以加深记忆。