【C言語】双方向リンクリストで任意の位置にノードを挿入する方法

リンクリストとは

リンクリストは動的なメモリ確保（動的メモリ割り当て）を利用するデータ構造で、複数のノードがつながった集合体です。

各ノードは「データ部」と「リンク部（ポインタ）」という2つの要素で構成されており、ポインタによって次のノード（双方向リンクリストの場合は前のノードも）と接続されています。

リンクリストの種類

C言語で扱われる主なリンクリストには、以下の4種類があります。

• 単方向リンクリスト（Singly Linked List）
• 双方向リンクリスト（Doubly Linked List）
• 循環単方向リンクリスト（Circular Singly Linked List）
• 循環双方向リンクリスト（Circular Doubly Linked List）

双方向リンクリストの構造

双方向リンクリストでは、各ノードが前のノードへのポインタ（preptr）と次のノードへのポインタ（nextptr）の両方を持っています。そのため、リストを前方向・後方向のどちらにもたどれるのが特徴です。以下の図は、双方向リンクリストの構造イメージです。

サンプルプログラム

以下は、双方向リンクリストを使用して任意の位置にノードを挿入するCプログラムの完全なコード例です。

#include <stdio.h>
#include <stdlib.h>
struct node {
    int num;
    struct node * preptr;
    struct node * nextptr;
}*stnode, *ennode;
void DlListcreation(int n);
void DlLinsertNodeAtBeginning(int num);
void DlLinsertNodeAtEnd(int num);
void DlLinsertNodeAtAny(int num, int pos);
void displayDlList(int a);
int main(){
    int n,num1,a,insPlc;
    stnode = NULL;
    ennode = NULL;
    printf("\n\n Doubly Linked List : Insert a node at any position :\n");
    printf("-----------------------------------------------------------------------------------\n");
    printf(" Input the number of nodes : ");
    scanf("%d", &n);
    DlListcreation(n);
    a=1;
    displayDlList(a);
    printf(" Input the position ( 1 to %d ) to insert a new node : ",n+1);
    scanf("%d", &insPlc);
    printf(" Input data for the position %d : ", insPlc);
    scanf("%d", &num1);
    DlLinsertNodeAtAny(num1,insPlc);
    a=2;
    displayDlList(a);
    return 0;
}
/* リンクリストの作成 */
void DlListcreation(int n){
    int i, num;
    struct node *fnNode;
    if(n >= 1){
        stnode = (struct node *)malloc(sizeof(struct node));
        if(stnode != NULL){
            printf(" Input data for node 1 : "); /* 最初のノードにデータを代入 */
            scanf("%d", &num);
            stnode->num = num;
            stnode->preptr = NULL;
            stnode->nextptr = NULL;
            ennode = stnode;
            for(i=2; i<=n; i++){
                fnNode = (struct node *)malloc(sizeof(struct node));
                if(fnNode != NULL){
                    printf(" Input data for node %d : ", i);
                    scanf("%d", &num);
                    fnNode->num = num;
                    fnNode->preptr = ennode;
                    fnNode->nextptr = NULL;
                    ennode->nextptr = fnNode;
                    ennode = fnNode;
                }
                else{
                    printf(" Memory can not be allocated.");
                    break;
                }
            }
        }
        else{
            printf(" Memory can not be allocated.");
        }
    }
}
/* 任意の位置にノードを挿入 */
void DlLinsertNodeAtAny(int num, int pos){
    int i;
    struct node * newnode, *tmp;
    if(ennode == NULL){
        printf(" No data found in the list!\n");
    }
    else{
        tmp = stnode;
        i=1;
        while(i<pos-1 && tmp!=NULL){
            tmp = tmp->nextptr;
            i++;
        }
        if(pos == 1){
            DlLinsertNodeAtBeginning(num); /* 先頭への挿入 */
        }
        else if(tmp == ennode){
            DlLinsertNodeAtEnd(num); /* 末尾への挿入 */
        }
        else if(tmp!=NULL){
            newnode = (struct node *)malloc(sizeof(struct node));
            newnode->num = num;
            newnode->nextptr = tmp->nextptr;
            newnode->preptr = tmp;
            if(tmp->nextptr != NULL){
                tmp->nextptr->preptr = newnode; /* n+1番目のノードを新ノードに接続 */
            }
            tmp->nextptr = newnode; /* n-1番目のノードを新ノードに接続 */
        }
        else{
            printf(" The position you entered, is invalid.\n");
        }
    }
}
/* 先頭にノードを挿入 */
void DlLinsertNodeAtBeginning(int num){
    struct node * newnode;
    if(stnode == NULL){
        printf(" No data found in the list!\n");
    }
    else{
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->num = num;
        newnode->nextptr = stnode;
        newnode->preptr = NULL;
        stnode->preptr = newnode;
        stnode = newnode;
    }
}
/* 末尾にノードを挿入 */
void DlLinsertNodeAtEnd(int num){
    struct node * newnode;
    if(ennode == NULL){
        printf(" No data found in the list!\n");
    }
    else{
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->num = num;
        newnode->nextptr = NULL;
        newnode->preptr = ennode;
        ennode->nextptr = newnode;
        ennode = newnode;
    }
}
/* リンクリストの表示 */
void displayDlList(int m){
    struct node * tmp;
    int n = 1;
    if(stnode == NULL) {
        printf(" No data found in the List yet.");
    }
    else{
        tmp = stnode;
        if (m==1) {
            printf("\n Data entered in the list are :\n");
        }
        else{
            printf("\n After insertion the new list are :\n");
        }
        while(tmp != NULL){
            printf(" node %d : %d\n", n, tmp->num);
            n++;
            tmp = tmp->nextptr; /* 現在のポインタを次のノードへ移動 */
        }
    }
}

挿入処理のポイント

このプログラムの中核となるのは DlLinsertNodeAtAny() 関数です。指定された位置に応じて、処理が次のように分岐します。

• 位置が1の場合： 先頭への挿入関数 DlLinsertNodeAtBeginning() を呼び出します。
• 位置が末尾の場合： 末尾への挿入関数 DlLinsertNodeAtEnd() を呼び出します。
• 中間の位置の場合： 指定位置の直前のノードまでポインタを進め、新しいノードの前後のポインタを付け替えて挿入します。

また、無効な位置が入力された場合にはエラーメッセージを表示するようになっている点も、実用的なポイントです。

実行結果

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

Doubly Linked List : Insert node at any position:
-----------------------------------------------------------------------------------
Input the number of nodes : 5
Input data for node 1 : 23
Input data for node 2 : 12
Input data for node 3 : 11
Input data for node 4 : 34
Input data for node 5 : 10

Data entered in the list are :
node 1 : 23
node 2 : 12
node 3 : 11
node 4 : 34
node 5 : 10
Input the position ( 1 to 6 ) to insert a new node : 5
Input data for the position 5 : 78

After insertion the new list are :
node 1 : 23
node 2 : 12
node 3 : 11
node 4 : 34
node 5 : 78
node 6 : 10

この実行例では、5つのノードからなるリストの5番目の位置にデータ「78」を挿入しています。挿入後は元の5番目だった「10」が6番目に移動し、リスト全体が正しく更新されていることが確認できます。