C言語で学ぶリンクリスト（連結リスト）への要素挿入の基本と実装方法

リンクリスト（連結リスト）は、動的メモリ確保を利用するデータ構造です。そのため、要素の追加や削除に応じて、リストのサイズが柔軟に伸縮します。リンクリストは「ノード」と呼ばれる要素の集合体として定義され、各ノードはデータ部とリンク部（ポインタ）の2つの部分で構成されています。

データ・リンク・リンクリスト全体の構造は、以下のように表現されます。

リンクリストに対する主な操作

C言語において、リンクリストに対して行える基本的な操作は主に次の3種類です。

• 挿入（Insertion）
• 削除（Deletion）
• 走査（Traversing）

挿入操作のポイント

ここでは、ノード2とノード3の間に新しいノード5を挿入する例を考えてみましょう。

同様に、リストの先頭にノード5を挿入することもできます。

また、リストの末尾にノード5を追加する場合も見てみましょう。

注意点

• ノードには名前が付けられていないため、単純に「ノード2の前に挿入する」という指定はできません。
• ただし、挿入位置（何番目か）が明示的に与えられている場合は、ノード2の前にノード5を挿入することが可能です。

サンプルプログラム

以下は、リンクリストに要素を挿入するC言語のサンプルプログラムです。先頭への挿入、末尾への挿入、指定ノードの後ろへの挿入、指定ノードの前への挿入の4つの関数を実装しています。

#include <stdio.h>
#include <stdlib.h>
struct node{
    int val;
    struct node *next;
};
void print_list(struct node *head){
    printf("H->");
    while(head){
        printf("%d->", head->val);
        head = head->next;
    }
    printf("……\n\n");
}
void insert_front(struct node **head, int value){
    struct node * new_node = NULL;
    new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL){
        printf(" Out of memory");
    }
    new_node->val = value;
    new_node->next = *head;
    *head = new_node;
}
void insert_end(struct node **head, int value){
    struct node * new_node = NULL;
    struct node * last = NULL;
    new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL){
        printf(" Out of memory");
    }
    new_node->val = value;
    new_node->next = NULL;
    if( *head == NULL){
        *head = new_node;
        return;
    }
    last = *head;
    while(last->next) last = last->next;
    last->next = new_node;
}
void insert_after(struct node *head, int value, int after){
    struct node * new_node = NULL;
    struct node *tmp = head;
    while(tmp) {
        if(tmp->val == after) { /*対象ノードを発見*/
            new_node = (struct node *)malloc(sizeof(struct node));
            if (new_node == NULL) {
                printf("Out of memory");
            }
            new_node->val = value;
            new_node->next = tmp->next;
            tmp->next = new_node;
            return;
        }
        tmp = tmp->next;
    }
}
void insert_before(struct node **head, int value, int before){
    struct node * new_node = NULL;
    struct node * tmp = *head;
    new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL){
        printf("Out of memory");
        return;
    }
    new_node->val = value;
    if((*head)->val == before){
        new_node->next = *head;
        *head = new_node;
        return;
    }
    while(tmp && tmp->next) {
        if(tmp->next->val == before) {
            new_node->next = tmp->next;
            tmp->next = new_node;
            return;
        }
        tmp = tmp->next;
    }
    /*対象ノードが見つからなかった場合*/
    free(new_node);
}
void main(){
    int count = 0, i, val, after, before;
    struct node * head = NULL;
    printf("Enter no: of elements: ");
    scanf("%d", &count);
    for (i = 0; i < count; i++){
        printf("Enter %dth element: ", i);
        scanf("%d", &val);
        insert_front(&head, val);
    }
    printf("starting list: ");
    print_list(head);
    printf("enter front element: ");
    scanf("%d", &val);
    insert_front(&head, val);
    printf("items after insertion: ");
    print_list(head);
    printf("enter last element: ");
    scanf("%d", &val);
    insert_end(&head, val);
    printf("items after insertion: ");
    print_list(head);
    printf("Enter an ele to insert in the list: ");
    scanf("%d", &val);
    printf("Insert after: ");
    scanf("%d", &after);
    insert_after(head, val, after);
    printf("List after insertion: ");
    print_list(head);
    printf("Enter an ele to insert in the list: ");
    scanf("%d", &val);
    printf("Insert before: ");
    scanf("%d", &before);
    insert_before(&head, val, before);
    printf("List after insertion: ");
    print_list(head);
}

実行結果

上記のプログラムをコンパイルして実行すると、以下のような出力が得られます。

Enter no: of elements: 4
Enter 0th element: 1
Enter 1th element: 2
Enter 2th element: 3
Enter 3th element: 4
starting list: H->4->3->2->1->......
enter front element: 5
items after insertion: H->5->4->3->2->1->......
enter last element: 0
items after insertion: H->5->4->3->2->1->0->......
Enter an ele to insert in the list: 6
Insert after: 0
List after insertion: H->5->4->3->2->1->0->6->......
Enter an ele to insert in the list: 7
Insert before: 5
List after insertion: H->7->5->4->3->2->1->0->6->......

このように、malloc関数による動的メモリ確保とポインタ操作を組み合わせることで、リンクリストの任意の位置へ柔軟に要素を挿入できます。各挿入関数では、メモリ確保の失敗チェックや、対象ノードが見つからない場合のfree処理なども行っており、実践的な実装例となっています。