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

#define LEN1 1000000 /* 対象の配列／リストの長さ */
#define LEN2 1000 /* 対象の配列／リストに挿入するもう一つの配列／リストの長さ */

struct cell {
    int content;
    struct cell *next;
};

struct cell *
add(int x, struct cell *p) {
    struct cell *q;

    q = (struct cell *) malloc(sizeof(struct cell));
    q->content = x;
    q->next = p;
    return q;
}

void insert_list(struct cell *pos, struct cell *first, struct cell *last) {
    /* pos が指している対象の線形リストのノードの直後にもう一つの線形リスト
    を挿入する関数。
    first, last は挿入される線形リストの最初と最後のノードを指すポインタ。 */
    last->next = pos->next; /* 先ず、挿入されるリストの最後のノードを pos の直後のノードとつなげる */
    pos->next = first; /* そして pos を、挿入されるリストの最初のノードとつなげる */
}

int *insert_array(int a1[], int a2[], int pos) {
    /* 配列 a1 の pos 番目（インデックスがpos-1）の要素の直後に配列 a2 の要素を挿入した新しい配列（new）
    を返す関数。 */
    int *new;
    int new_size = LEN1+LEN2; /* 両方の配列の要素が入り切れるように長さを合計にする */
    int i;
    new = (int *)malloc(sizeof(int)*new_size); /* 関数で作られた配列を返すからメモリの動的確保をする */
    /* a1 と a2 の全要素を new にコピーする */
    for (i=0; i<pos; i++) { /* pos 番目の要素までコピー */
        new[i] = a1[i];
    }
    for (i=LEN1-1; i>=pos; i--) { /* a1 の残りの部分を後ろからコピー */
        new[i+LEN2] = a1[i];
    }
    for (i=0; i<LEN2; i++) { /* 挿入される配列のコピー */
        new[pos+i] = a2[i];
    }
    return new;
}

int main() {
    int i;
    /* 挿入位置は対象の配列／リストの末尾にする（２つの配列／リストを
    連結することになる） */
    int insert_pos = LEN1;

    long start, end;
    double time_used;

    int a1[LEN1];
    int a2[LEN2];
    int *a3; /* a1 に a2 の要素を挿入した新しい配列を表すポインタ */

    struct cell *lst1_first = NULL; /* 対象のリストの先頭の要素へのポインタ */
    struct cell *lst1_last = NULL; /* 対象のリストの末尾の要素へのポインタ */
    struct cell *lst2_first = NULL; /* 挿入されるリストの先頭の要素へのポインタ */
    struct cell *lst2_last = NULL; /* 挿入されるリストの末尾の要素へのポインタ */

    /* 配列の初期化 */
    for (i=0; i<LEN1; i++) {
        a1[i] = i;
    }
    for (i=0; i<LEN2; i++) {
        a2[i] = i;
    }

    /* 線形リストの初期化 */
    lst1_last = add(0, lst1_last);
    lst1_first = lst1_last;
    lst2_last = add(0, lst2_last);
    lst2_first = lst2_last;
    for (i=1; i<LEN1; i++) {
        lst1_first = add(i, lst1_first);
    }
    for (i=1; i<LEN2; i++) {
        lst2_first = add(i, lst2_first);
    }

    /* 2つの配列を連結し処理時間を計測 */
    start = clock();
    a3 = insert_array(a1, a2, insert_pos);
    end = clock();
    time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("配列の場合の処理時間: %fs\n", time_used);

    /* 2つの線形リストを連結し処理時間を計測 */
    start = clock();
    insert_list(lst1_last, lst2_first, lst2_last);
    end = clock();
    time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("連結リストの場合の処理時間: %fs\n", time_used);
}