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

实现逻辑：

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

这里先遍历找到 pos 的前驱 p，确认存在后再执行插入操作。

3. 双向链表指定位置删除

删除节点需修改前驱节点的 next 和后继节点的 prev，并释放内存。边界情况如头尾节点需特殊处理，但循环链表结构下通常统一处理即可。

函数原型：

void LTErase(ListNode* pos);

实现步骤：

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

关键点： 获取前驱 p 后，直接让 p 指向 pos 的后继，同时让后继的 prev 指向 p，形成闭环，最后释放 pos。

4. 完整代码展示

包含头文件定义、核心实现及测试主函数。

头文件 (1.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;
// 声明部分略，见下方完整实现

核心实现 (1.cpp)

#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.cpp)

#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(); 
}

二、顺序表与链表的分析

相同点

• 逻辑结构一致：均为线性表，数据元素之间呈一对一的顺序关系。
• 核心操作相同：都支持插入、删除、查找、遍历等基本线性表操作。
• 存储数据类型：均可存储相同类型的数据元素。

不同点（核心差异）

• 顺序表：适合频繁随机访问、数据量固定的场景（如存储学生信息表）。内存连续，缓存友好，但扩容成本高。
• 链表：适合频繁插入删除、数据量动态变化的场景（如实现队列、栈）。内存离散，无需预分配，但随机访问效率低。

三、链表算法题

1. 移除链表元素

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

思路： 可以通过遍历整个链表，用一个节点存储前一个节点，在发现值为 val 时改变 next 区域的指向。或者创建一个新链表，存储符合要求的节点。虽然第二种方法没有释放原链表空间，但在 OJ 刷题中较为简单且直观。

解题代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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; 
}

解析：

1. 初始化 h 为新链表头，pr 为尾节点，p 为遍历指针。
2. 遍历原链表，若当前节点值不等于 val，将其拼接到新链表尾部。
3. 首次保留节点时，h 和 pr 均指向它；后续节点通过 pr->next 连接。
4. 遍历结束后，将新链表尾节点的 next 置为 NULL，避免野指针风险。

2. 反转链表

题目要求反转给定的链表。对于单链表，无法直接找到前驱节点，因此不能简单复制。正确思路是通过三个指针迭代实现，时间复杂度 O(n)，空间复杂度 O(1)。

核心思路： 使用 prev（已反转部分的头）、curr（当前待反转节点）、next（临时保存下一个节点）三个指针，逐次反转节点指向。

解题代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode node;
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; 
}

解析：

1. s1 初始为 NULL，代表反转后的链表头部。
2. s2 指向当前节点，s3 暂存下一节点以防断链。
3. 循环中先将 s2->next 指向 s1，完成当前节点的反转。
4. 随后 s1 后移至 s2，s2 后移至 s3，s3 继续向后推进。
5. 循环结束，s1 即为原链表尾节点，也就是新链表的头节点。

本文涵盖了双向链表的剩余核心操作实现，对比了顺序表与链表的适用场景，并通过算法题演示了指针操作的细节。理解这些底层机制有助于在实际开发中做出更优的数据结构选择。