Array vs List

array_vs_list.c

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

#define N 10000
#define TRIAL 10000

typedef struct Cell {
    int value;
    struct Cell *next;
} Cell;

Cell *make_cell(int i) {
    Cell *c = malloc(sizeof(Cell));
    c->value = i;
    c->next = NULL;
    return c;
}

int main(void) {
    Cell *cells[N];

    int v = 1;
    for (int i=0; i<N; i++) {
        cells[i] = make_cell(v);
        v *= -1;
    }

    //for (int i=0; i<N; i++) {
    //  cells[i] = make_cell(i);
    //}

    for (int i=0; i<N-1; i++) {
        cells[i]->next = cells[i+1];
    }


    {
        long start = clock();
        for (int j=0; j<TRIAL; j++) {
            int sum = 0;
            for (int i=0; i<N; i++) {
                sum += cells[i]->value;
            }
            //printf("%d\n", sum);
        }
        printf("%f s\n", (double)(clock() - start)/CLOCKS_PER_SEC);
    }

    {
        long start = clock();
        for (int j=0; j<TRIAL ; j++) {
            int sum = 0;
            Cell *cur = cells[0];
            do {
                sum += cur->value;
                cur = cur->next;
            } while (cur != NULL);
            //printf("%d\n", sum);
        }
        printf("%f s\n", (double)(clock() - start)/CLOCKS_PER_SEC);
    }

    return 0;
}

% gcc -O0 array_vs_list.c  && ./a.out
0.158545 s
0.243200 s