面试题：C语言结构体指针与成员访问的优化

Question

定义一个结构体链表，struct Node { int data; struct Node *next; }; 编写一个函数，接收链表头指针，通过指针访问每个节点的data成员并计算所有data的总和。要求优化指针访问的效率，说明优化的思路和依据。

Answer 1

#include <stdio.h>
#include <stdlib.h>

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

// 计算链表所有data总和的函数
int sumOfData(struct Node *head) {
    int sum = 0;
    struct Node *current = head;
    // 优化思路：减少指针的间接访问，直接用current指针顺序遍历
    // 依据：减少指针跳转带来的额外开销，在顺序访问内存时利用局部性原理提高缓存命中率
    while (current != NULL) {
        sum += current->data;
        current = current->next;
    }
    return sum;
}

// 创建新节点的辅助函数
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // 创建链表 1 -> 2 -> 3
    struct Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    int total = sumOfData(head);
    printf("Sum of data in the linked list: %d\n", total);

    // 释放链表内存
    struct Node *current = head;
    struct Node *nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }

    return 0;
}

上述代码中，sumOfData 函数实现了计算链表所有 data 成员总和的功能。优化思路在于直接使用 current 指针顺序遍历链表，减少指针间接访问带来的开销。在顺序访问内存时，利用局部性原理，后续访问的数据更有可能在缓存中，从而提高缓存命中率，提升效率。