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

双向链表实现与算法分析

承接上文关于双向链表基础概念的内容，本节重点深入其具体实现细节，包括查找、插入、删除等核心操作，并对比顺序表与链表的差异，最后通过经典算法题巩固理解。

一、双向链表核心操作实现

1. 查找操作

双向链表的查找逻辑与单链表类似，但可以利用双向特性进行遍历优化。我们需要创建一个临时指针来遍历整个链表。

接口定义：

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

实现逻辑： 首先判断链表是否为空，若为空直接返回 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; 
}

这里要注意循环终止条件 p != h，因为是循环链表，必须防止死循环。

2. 指定位置插入

插入操作分为'在指定节点之后'和'在指定节点之前'两种情况，核心在于维护好前驱和后继指针的指向关系。

在指定节点之后插入 该函数用于在节点 pos 之后插入新节点。关键在于先保存原后继节点，防止断链。

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;       // 修改原后继前驱
}

在指定节点之前插入 这需要找到 pos 的前驱节点 p，然后利用上述'之后插入'的逻辑，或者手动调整四个指针。

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

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 即为新的头节点。

---

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