时间复杂度与硬件现实：为何链表遍历可能比数组慢数倍？

1
2
3
4

r@r:/data/test/a-l-test$ gcc main.c -o main
r@r:/data/test/a-l-test$ ./main
ArrayList middle insert time: 0.066473 seconds
LinkedList middle insert time: 1.509272 seconds

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h> // For memmove

#define N 10000
#define INITIAL_SIZE 100000

// Simple dynamic array structure
typedef struct {
    int* data;
    size_t size;
    size_t capacity;
} ArrayList;

void arraylist_insert(ArrayList* arr, size_t index, int value) {
    if (arr->size >= arr->capacity) {
        // Basic resize (actual implementations are smarter)
        size_t new_capacity = arr->capacity == 0 ? 10 : arr->capacity * 2;
        int* new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
        if (!new_data) { perror("Failed to realloc"); exit(1); }
        arr->data = new_data;
        arr->capacity = new_capacity;
    }
    if (index > arr->size) index = arr->size; // Clamp index

    // Move elements: The O(n) part, but potentially cache-friendlier
    memmove(&arr->data[index + 1], &arr->data[index], (arr->size - index) * sizeof(int));

    arr->data[index] = value;
    arr->size++;
}

// LinkedList Node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Basic linked list insert (find + insert)
void linkedlist_insert(Node** head_ref, size_t index, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { perror("Failed malloc"); exit(1); }
    newNode->data = value;

    if (index == 0 || *head_ref == NULL) {
        newNode->next = *head_ref;
        *head_ref = newNode;
        return;
    }

    // Traverse: The cache-unfriendly O(n) part
    Node* current = *head_ref;
    for (size_t i = 0; i < index - 1 && current->next != NULL; ++i) {
        current = current->next; // Potential cache miss here
    }

    // Insert (O(1) pointer ops + allocation cost)
    newNode->next = current->next;
    current->next = newNode;
}


int main() {
     // --- ArrayList ---
    ArrayList arr = {NULL, 0, 0};
    // Pre-allocate to focus on insertion cost, not just realloc
    arr.capacity = INITIAL_SIZE + N;
    arr.data = (int*)malloc(arr.capacity * sizeof(int));
     if (!arr.data) return 1;
    for(size_t i = 0; i < INITIAL_SIZE; ++i) arr.data[i] = (int)i;
    arr.size = INITIAL_SIZE;

    size_t insertIndexArr = INITIAL_SIZE / 2;
    clock_t start_arr = clock();
    for (int i = 0; i < N; ++i) {
        arraylist_insert(&arr, insertIndexArr, -i);
        // insertIndexArr++; // Simulate always inserting in the expanding middle
    }
    clock_t end_arr = clock();
    printf("ArrayList middle insert time: %f seconds\n",
           ((double)(end_arr - start_arr)) / CLOCKS_PER_SEC);
    free(arr.data);


    // --- LinkedList ---
    Node* head = NULL;
    Node* tail = NULL;
     for(int i = 0; i < INITIAL_SIZE; ++i) { // Initialize
        Node* newNode = (Node*)malloc(sizeof(Node));
        if (!newNode) return 1;
        newNode->data = i; newNode->next = NULL;
        if (!head) head = newNode;
        else tail->next = newNode;
        tail = newNode;
    }

    size_t insertIndexList = INITIAL_SIZE / 2;
    clock_t start_list = clock();
    for (int i = 0; i < N; ++i) {
        linkedlist_insert(&head, insertIndexList, -i);
         // insertIndexList++;
    }
    clock_t end_list = clock();
    printf("LinkedList middle insert time: %f seconds\n",
           ((double)(end_list - start_list)) / CLOCKS_PER_SEC);

    // ... free list ...
    Node* current_free = head;
    while(current_free != NULL){
        Node* next_free = current_free->next;
        free(current_free);
        current_free = next_free;
    }

    // Compare the times. Often, ArrayList is faster despite O(n) move.
    return 0;
}