C++双指针链表插入问题：为何currPage指针意外变更？

近期有一项作业，涉及处理以双指针表示的单页内存块。现有一个Page指针数组，每个Page结构体包含next_free和prev_free两个Page*类型指针，需将输入的Page*按value值插入以pageArray[0]为头节点的有序链表中。

编写了insertPage函数，但添加打印语句后发现，执行(*prevPage)->next_free = page时，(*currPage)指向的内容发生了意外变更。原本认为修改(*prevPage)不会影响(*currPage)，想请教该问题的原因及正确实现方式。

代码如下：

struct Page {
    int value;
    Page* next_free;
    Page* prev_free;
};

Page* pageArray[10];

void insertPage(Page* page) {
    Page** currPage = &pageArray[0];
    while (*currPage) {
        double value = (*currPage)->value;
        if (value < page->value) {
            currPage = &(*currPage)->next_free; 
        } else {
            break;
        } 
    }

    Page** prevPage = &(*currPage)->prev_free;
    std::cout << "Value of current block: "
              << (*currPage)->value << std::endl;
    (*prevPage)->next_free = page;
    std::cout << "Value of current block after changing previous block: "
              << (*currPage)->value << std::endl;
    (*currPage)->prev_free = page;
}

核心问题是你对二级指针的使用逻辑完全错误：

• Page** prevPage = &(*currPage)->prev_free;这行代码取的是当前节点currPage的prev_free成员指针的地址，而不是当前节点的前一个节点的指针地址。
• 如果currPage指向的是链表头节点，且头节点的prev_free是未初始化的野指针，那么(*prevPage)就指向了一块随机内存。当你修改(*prevPage)->next_free时，这块随机内存恰好覆盖了(*currPage)的value字段，导致值被意外篡改。
• 就算prev_free是合法指针，你这里的逻辑也不是获取前一个节点，而是直接操作当前节点的前驱指针指向的对象，这完全不符合双向链表插入的逻辑。

正确的做法是遍历链表时同时跟踪前一个节点，逻辑更清晰，也避免了二级指针带来的混淆：

#include <iostream>
#include <string>

struct Page {
    int value;
    Page* next_free;
    Page* prev_free;
};

Page* pageArray[10];

void insertPage(Page* page) {
    Page* prev = nullptr;
    Page* curr = pageArray[0];

    // 找到插入位置：curr是第一个value >= page->value的节点
    while (curr != nullptr && curr->value < page->value) {
        prev = curr;
        curr = curr->next_free;
    }

    // 配置新节点的双向指针
    page->prev_free = prev;
    page->next_free = curr;

    // 更新前一个节点的next指针
    if (prev != nullptr) {
        prev->next_free = page;
    } else {
        // 插入到链表头部，更新头节点
        pageArray[0] = page;
    }

    // 更新后一个节点的prev指针
    if (curr != nullptr) {
        curr->prev_free = page;
    }

    // 调试输出
    std::cout << "插入完成，当前位置节点value：" 
              << (curr ? std::to_string(curr->value) : "无") << std::endl;
}

关键说明 #

• 遍历过程中用prev记录当前节点的前一个节点，确保插入位置的前后节点都能被正确获取。
• 插入时先设置新节点的双向指针，再分别修改前后节点的指针：
  • 若prev为空，说明要插入到链表头部，直接更新pageArray[0]。
  • 若curr不为空，需要将curr的prev_free指向新节点。
• 彻底避免了野指针和错误的二级指针操作，不会出现内存篡改的问题。

内容的提问来源于stack exchange，提问作者frank