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

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

一、实现双向链表

1. 双向链表查找

双向链表的查找操作与单链表类似，但可利用创建一个暂时的指针实现遍历。

函数形式：

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

实现：

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

说明： 通过遍历来实现，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空。

2. 双向链表在指定位置插入

双向链表在指定位置插入分为双向链表在指定位置之前插入与双向链表在指定位置之后插入。

双向链表在指定位置之后插入

函数形式：

void LTInsert(ListNode* pos, type x);

实现：

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 之后插入新节点，核心逻辑是通过调整指针关系实现无缝插入。需先保存后继节点，防止原链表后半部分丢失。

双向链表在指定位置之前插入

函数形式：

void LTInsertfront(ListNode* h, ListNode* pos, type x);

实现：

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 的前驱位置插入新节点（即在 pos 前面插入）。

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；调整指针切断连接；释放 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;

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

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

二、顺序表与链表的分析

相同点

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

不同点（核心差异）

• 存储方式：顺序表占用连续内存，链表占用离散内存。
• 访问效率：顺序表支持随机访问，链表只能顺序访问。
• 增删效率：顺序表增删涉及大量移动，链表仅需修改指针。

关键结论

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

三、链表算法题

一、移除链表元素

题目描述：移除值为 val 的节点，返回新的头结点。

解题思路： 创建新链表，遍历原链表，将值不等于 val 的节点拼接至新链表尾部。

代码实现：

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 为尾节点。
2. 遍历原链表，若当前节点值不等于 val，则将其加入新链表。
3. 遍历结束后，将新链表尾节点 next 置为 NULL，避免野指针。

二、反转链表

题目描述：反转给定的单链表。

解题思路： 使用三个指针迭代法，逐次反转节点指向。

• s1：指向已反转部分的头节点（初始为 NULL）。
• s2：指向当前待反转节点（初始为 head）。
• s3：临时保存 s2 的下一个节点。

代码实现：

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

说明： 循环中依次执行：反转当前节点指向 -> 更新已反转头 -> 移动当前节点 -> 移动暂存节点。最终 s1 指向原链表尾节点，即新链表头。