面试题：C++ 引用与指针在复杂数据结构中的性能表现

性能差异分析

内存访问：
- 指针方式：直接使用指针操作链表节点时，每次访问节点的数据成员（如data）或指针成员（如prev和next），都是通过指针间接访问内存。现代CPU通常有缓存机制，指针的间接访问可能导致缓存不命中，因为指针指向的内存地址可能是不连续的，从而降低内存访问效率。
- 引用传递指针方式：引用本质上是一个常量指针，通过引用传递指向链表节点的指针，在访问节点数据时，同样是通过指针间接访问内存，与直接使用指针方式在内存访问上没有本质区别。但在传递指针时，引用在语法上更简洁，并且可以避免空指针的意外传递（因为引用必须初始化）。
时间复杂度：
- 指针方式：无论是遍历链表（查找特定节点、遍历修改所有节点等）还是修改节点数据，时间复杂度主要取决于链表的长度。例如，遍历链表查找特定节点，平均时间复杂度为 ( O(n) )，其中 ( n ) 是链表节点的数量。因为在最坏情况下，需要遍历整个链表。修改节点数据本身是常数时间操作 ( O(1) )，但结合遍历查找等操作，整体时间复杂度仍由遍历主导。
- 引用传递指针方式：时间复杂度与指针方式相同。因为核心操作如遍历链表和修改节点数据的方式本质不变，只是指针的传递方式不同，不影响基本操作的时间复杂度。

代码示例

使用指针操作链表

#include <iostream>

struct Node {
    int data;
    Node* prev;
    Node* next;
};

// 创建新节点
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

// 使用指针遍历并修改链表节点数据
void traverseAndModifyWithPtr(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        current->data *= 2;
        current = current->next;
    }
}

// 打印链表
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;

    std::cout << "Original list: ";
    printList(head);

    traverseAndModifyWithPtr(head);

    std::cout << "Modified list: ";
    printList(head);

    // 释放链表内存
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        delete current;
        current = next;
    }

    return 0;
}

通过引用传递指针操作链表

#include <iostream>

struct Node {
    int data;
    Node* prev;
    Node* next;
};

// 创建新节点
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    return newNode;
}

// 通过引用传递指针遍历并修改链表节点数据
void traverseAndModifyWithRefPtr(Node*& head) {
    Node* current = head;
    while (current != nullptr) {
        current->data *= 2;
        current = current->next;
    }
}

// 打印链表
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->prev = head;
    head->next->next = createNode(3);
    head->next->next->prev = head->next;

    std::cout << "Original list: ";
    printList(head);

    traverseAndModifyWithRefPtr(head);

    std::cout << "Modified list: ";
    printList(head);

    // 释放链表内存
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        delete current;
        current = next;
    }

    return 0;
}

在这两个示例中，traverseAndModifyWithPtr 函数使用指针直接操作链表，而 traverseAndModifyWithRefPtr 函数通过引用传递指针来操作链表。从代码逻辑上看，两者在遍历和修改链表节点数据的核心操作上是一致的，体现了两种方式在性能上的一致性，但引用传递指针在语法上更安全和简洁（如在函数参数传递时可以避免空指针误传）。

星途面试题库

面试题：C++ 引用与指针在复杂数据结构中的性能表现

知识考点

面试题答案

性能差异分析

代码示例