C言語で単方向リンクリストを使って数値を逆順に表示する方法

リンクリスト（連結リスト）とは

リンクリストは動的メモリ割り当てを利用するデータ構造で、複数の「ノード」が連なった集合体です。各ノードはデータ部分とリンク部分（次のノードへのポインタ）の2つの要素で構成されています。

リンクリストの種類

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

• 単方向リンクリスト
• 双方向リンクリスト
• 循環単方向リンクリスト
• 循環双方向リンクリスト

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

下の図は、単方向リンクリストの構造を示したものです。各ノードがデータと次ノードへのポインタを持ち、末尾ノードのポインタはNULLを指します。

数値を逆順に表示するCプログラム

以下は、単方向リンクリストに入力した数値を逆順に表示するCプログラムです。「ノードの作成（createNodeList）」「リストの反転（reverseDispList）」「リストの表示（displayList）」という3つの関数で構成されています。

#include <stdio.h>
#include <stdlib.h>
struct node {
    int num;
    struct node *nextptr;
}*stnode;
void createNodeList(int n);
void reverseDispList();
void displayList();
int main(){
    int n;
    printf("\n\n single Linked List : print it in reverse order :\n");
    printf("------------------------------------------------------------------------------\n");
    printf(" Input the number of nodes : ");
    scanf("%d", &n);
    createNodeList(n);
    printf("\n Data entered in the list are : \n");
    displayList();
    reverseDispList();
    printf("\n The list in reverse are : \n");
    displayList();
    return 0;
}
void createNodeList(int n){
    struct node *fnNode, *tmp;
    int num, i;
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL) {
        printf(" Memory can not be allocated.");
    }
    else{
        // キーボードから1番目のノードのデータを読み込む
        printf(" Input data for node 1 : ");
        scanf("%d", &num);
        stnode->num = num;
        stnode->nextptr = NULL;
        tmp = stnode;
        // n個のノードを作成し、リンクリストに追加する
        for(i=2; i<=n; i++){
            fnNode = (struct node *)malloc(sizeof(struct node));
            if(fnNode == NULL) {
                printf(" Memory can not be allocated.");
                break;
            }
            else{
                printf(" Input data for node %d : ", i);
                scanf(" %d", &num);
                fnNode->num = num;
                fnNode->nextptr = NULL;
                tmp->nextptr = fnNode;
                tmp = tmp->nextptr;
            }
        }
    }
}
void reverseDispList(){
    struct node *prevNode, *curNode;
    if(stnode != NULL){
        prevNode = stnode;
        curNode = stnode->nextptr;
        stnode = stnode->nextptr;
        prevNode->nextptr = NULL; // 先頭ノードを末尾ノードとして扱う
        while(stnode != NULL){
            stnode = stnode->nextptr;
            curNode->nextptr = prevNode;
            prevNode = curNode;
            curNode = stnode;
        }
        stnode = prevNode; // 末尾ノードを先頭（ヘッド）として扱う
    }
}
void displayList(){
    struct node *tmp;
    if(stnode == NULL){
        printf(" No data found in the list.");
    }
    else{
        tmp = stnode;
        while(tmp != NULL){
            printf(" Data = %d\n", tmp->num);
            tmp = tmp->nextptr;
        }
    }
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。入力した順序とは逆の順序でデータが表示されていることが確認できます。

single Linked List : print it in reverse order :
------------------------------------------------------------------------------
Input the number of nodes : 5
Input data for node 1 : 12
Input data for node 2 : 45
Input data for node 3 : 11
Input data for node 4 : 9
Input data for node 5 : 10

Data entered in the list are :
Data = 12
Data = 45
Data = 11
Data = 9
Data = 10

The list in reverse are :
Data = 10
Data = 9
Data = 11
Data = 45
Data = 12

リスト反転の仕組み（ポイント解説）

reverseDispList関数では、stnode・curNode・prevNodeの3つのポインタを使いながらリストを先頭から走査し、各ノードのnextptrを「前のノード」へ向き直すことで反転を実現しています。

具体的には、まず先頭ノードのnextptrをNULLに設定して末尾ノードに変え、その後ループ処理で各ノードのリンクを逆向きにつなぎ替えます。ループが完了した時点で、元の末尾ノードを新しい先頭（ヘッド）としてstnodeに代入すれば、反転されたリストの完成です。この手法なら余分なメモリを消費せず、O(n)の計算量でリスト全体を反転できます。