連結リスト①（単方向・線形） | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第３章

配列に続いて取り上げるデータ構造は、連結リスト（リンクドリスト）です。ここからちょっと難しくなっていきますが、これも基礎的なデータ構造ですから、確実に理解しましょう。

連結リストは、配列のように各要素を連続的に並べることをしません。各要素は、メモリ上に飛び飛びの位置に置かれており、それぞれを何らかの方法で「連結（リンク）」します。

どう連結するかといえば、Ｃ言語であればポインタを使います。そういう訳で、ここからはポインタの理解が必須事項ですから、そこに不安がある場合はＣ言語編で学習してからにしましょう。

ポインタの使えないプログラミング言語の場合、参照の仕組みがあればそれで実現できます。それも使えないような一部の言語では、配列で代用して、どの要素同士が連結されているかを添字を使って表現することによって、一応はシミュレートできます。

連結リストは、その実現の仕方によっていくつものパターンに細分化できます。

要素が、Ａ→Ｂ→Ｃ→Ｄ　のように、先へ先へと連結されていくものを線形リストと呼びます。一方、Ａ→Ｂ→Ｃ→Ｄ→Ａ　のように、最後の要素の先が最初の要素に戻ってくるようなものは、循環リストと呼ばれます。

さらに、Ａ⇔Ｂ⇔Ｃ⇔Ｄ　のように、先へも前へも連結されているものを、双方向リストと呼び、そうでなく、一方向だけに連結されているものを、単方向リストと呼びます。

循環リストや、双方向リストについては、第４章で解説します。

実際にはそれらを組み合わせて、全部で４通りのパターンが作られます。

より特殊な連結リストもありますが、まず基本となるのはこの４パターンです。

単方向線形リスト

では、まずは単方向で線形なリストを取り上げます。この構造のイメージ図は次のようになります。

この図において、１つの塊は次のような構造体で表現できます。

struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
};

ここでは、連結リストの要素は int型であると想定して、int型のメンバ value を持たせています。もちろん、この部分は何でも構いません。

連結リストの鍵となるのは、もう１つのメンバ next です。これは、この構造体と同じ型を指すポインタ変数になっています。このポインタ変数を使って、次の要素への連結を行う訳です。今後、このメンバnext のことを、「nextポインタ」と呼ぶことにします。

構造体メンバが、自分の属する構造体と同じ型の構造体変数を参照する形は、自己参照構造体と呼ばれます（Ｃ言語編第３７章）。

では実際にプログラムを作って、動作を確かめてみます。ちょっと長いですが、いろいろと実験できるプログラムを作りました。

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


/* コマンド */
enum Cmd_tag {
    CMD_ADD,
    CMD_DELETE,
    CMD_SEARCH,
    CMD_CLEAR,
    CMD_PRINT,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};


/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "a", "add" },
    { "d", "delete" },
    { "s", "search" },
    { "c", "clear" },
    { "p", "print" },
    { "e", "exit" }
};

static void init_head(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_add(void);
static enum CmdRetValue_tag cmd_delete(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag cmd_clear(void);
static enum CmdRetValue_tag cmd_print(void);
static enum CmdRetValue_tag cmd_exit(void);
static void add_elem(int value);
static int delete_elem(int value);
static void clear_list(void);
static void print_list(void);
static struct LinkedList_tag* search_tail(void);
static struct LinkedList_tag* search_elem(int value);
static void get_line(char* buf, size_t size);

/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_add,
    cmd_delete,
    cmd_search,
    cmd_clear,
    cmd_print,
    cmd_exit
};



/* 連結リスト型 */
struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
};

static struct LinkedList_tag gHead;  /* 先頭の要素 */



int main(void)
{
    init_head();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    return 0;
}

/* 先頭要素を初期化 */
void init_head(void)
{
    gHead.value = 0;
    gHead.next = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力してください。" );
    printf( "　連結リストに要素を追加する: %s (%s)\n", CMD_STR[CMD_ADD][CMD_STR_SHORT], CMD_STR[CMD_ADD][CMD_STR_LONG] );
    printf( "　連結リストから要素を削除する: %s (%s)\n", CMD_STR[CMD_DELETE][CMD_STR_SHORT], CMD_STR[CMD_DELETE][CMD_STR_LONG] );
    printf( "　連結リストから要素を探す: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
    printf( "　連結リストを空にする: %s (%s)\n", CMD_STR[CMD_CLEAR][CMD_STR_SHORT], CMD_STR[CMD_CLEAR][CMD_STR_LONG] );
    printf( "　連結リストの中身を出力する: %s (%s)\n", CMD_STR[CMD_PRINT][CMD_STR_SHORT], CMD_STR[CMD_PRINT][CMD_STR_LONG] );
    printf( "　終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    addコマンドの実行
*/
enum CmdRetValue_tag cmd_add(void)
{
    char buf[40];
    int value;

    puts( "追加する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    add_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    deleteコマンドの実行
*/
enum CmdRetValue_tag cmd_delete(void)
{
    char buf[40];
    int value;

    puts( "削除する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( delete_elem(value) >= 1 ){
        puts( "要素を削除しました。" );
    }
    else{
        puts( "削除する要素は見つかりませんでした。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    searchコマンドの実行
*/
enum CmdRetValue_tag cmd_search(void)
{
    char buf[40];
    int value;

    puts( "探索する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( search_elem(value) == NULL ){
        printf( "%d は連結リスト中に存在しません。\n", value );
    }
    else{
        printf( "%d は連結リスト中に存在します。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    clearコマンドの実行
*/
enum CmdRetValue_tag cmd_clear(void)
{
    clear_list();

    return CMD_RET_VALUE_CONTINUE;
}

/*
    printコマンドの実行
*/
enum CmdRetValue_tag cmd_print(void)
{
    print_list();

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を追加する

    引数：
        value:  追加する要素の数値データ。
*/
void add_elem(int value)
{
    struct LinkedList_tag* elem;
    struct LinkedList_tag* tail;

    /* リストの末尾を探す */
    tail = search_tail();

    /* 追加する要素を作る */
    elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

    /* これまで末尾だった要素は、末尾から２番目の位置になる。
       そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする */
    tail->next = elem;
}

/*
    要素を削除する

    引数：
        value：  削除する要素が持つ数値データ。
    戻り値：
        削除できた要素の個数を返す。
*/
int delete_elem(int value)
{
    struct LinkedList_tag* p = gHead.next;
    struct LinkedList_tag* prev = &gHead;
    int count = 0;

    while( p != NULL ){
        if( p->value == value ){
            /* 削除する要素の１つ手前の要素の nextメンバを、
               削除する要素の次の要素を指すように書き換える */
            prev->next = p->next;

            /* 要素は malloc関数で生成したので、free関数による解放が必要。
               上記の prev->next = p->next よりも後で行わないと、不正なポインタが
               prev->next に代入されてしまうことに注意。 */
            free( p );

            /* 続行するなら、p を正しい要素を指すようにする */
            p = prev->next;

            ++count;
        }
        else{
            prev = p;
            p = p->next;
        }
    }

    return count;
}

/*
    要素を空にする
*/
void clear_list(void)
{
    struct LinkedList_tag* p = gHead.next;
    struct LinkedList_tag* prev = &gHead;

    while( p != NULL ){
        /* 削除する要素の１つ手前の要素の nextメンバを、
            削除する要素の次の要素を指すように書き換える */
        prev->next = p->next;

        /* 要素は malloc関数で生成したので、free関数による解放が必要。
            上記の prev->next = p->next よりも後で行わないと、不正なポインタが
            prev->next に代入されてしまうことに注意。 */
        free( p );

        p = prev->next;
    }
}

/*
    要素を出力する
*/
void print_list(void)
{
    struct LinkedList_tag* p = gHead.next;

    if( p == NULL ){
        puts( "リストは空です。" );
        return;
    }

    while( p != NULL ){
        printf( "%d\n", p->value );
        p = p->next;
    }
}

/*
    末尾の要素を探す

    戻り値：
        連結リストの末尾にある要素を指すポインタ。
*/
struct LinkedList_tag* search_tail(void)
{
    struct LinkedList_tag* p = &gHead;

    while( p->next != NULL ){
        p = p->next;
    }

    return p;
}

/*
    指定した値を持つ要素を探す

    引数：
        value：  探し出す要素が持つ数値データ。
    戻り値：
        先頭から連結リストをたどり、最初に見つけた value と同じ値を持つ要素のメモリアドレス。
        見つからなかった場合は NULL を返す。
*/
struct LinkedList_tag* search_elem(int value)
{
    struct LinkedList_tag* p = gHead.next;

    while( p != NULL ){
        if( p->value == value ){
            return p;
        }
        p = p->next;
    }

    return NULL;
}

/*
    標準入力から１行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取れる最大文字数は size - 1 文字。

    引数：
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値：
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}

このプログラムを実行すると、コマンドの入力を求められます。例えば、"a" または "add" と入力すれば、リストへ要素を追加しようとします。このコマンドの場合は、続けて、追加する要素の入力を求められます。

リストへの要素の追加、要素の削除、全削除、探索、中身の出力のコマンドを実装しています。とりあえず、適当に追加や削除を行い、中身を出力してみて動作を確かめてみてください。

初期化

まず、main関数の最初に呼び出している init_head関数を見てください。この関数の中で、グローバル変数gHead のメンバを初期化しています。Ｃ言語編で何度か、「グローバル変数を使うべきではない」と書いていますが、ここではサンプルプログラムとして割り切ってください。より現実に即した実装方法については、後で詳しく取り上げます。

このグローバル変数gHead は、連結リストの先頭の要素のことです。この先頭要素は、実際にはデータを格納することはせず、ダミーの要素としての役割を持たせています。このようなダミーの要素を作ることで、連結リストが空の場合を考慮せずに各種機能を実装できます。

gHead.next は NULL が格納されていますが、このように nextポインタが NULL になっている要素は、連結リストの末尾の要素であることを表現しています。したがって gHead は、連結リストの先頭であると同時に末尾でもある訳です。この後、addコマンドによって要素を追加すれば、gHead は末尾ではなくなりますが、先頭ではあり続けます。

gHead.value に 0 を格納している点は、特に意味はありません。どのみちダミーの要素なので、この値が参照されることはないので、何が入っていても構いません。しかし、Ｃ言語では何もしなければメモリの状態は不定ですから、よからぬトラブルの原因になることもあるので、一応適当な値を入れておいた方が良いでしょう。

末尾への要素の追加

次に、要素の追加です。今回のサンプルでは、要素は必ずリストの最後尾に追加されるようになっています（要素を途中に挿入する方法は、後で取り上げます）。

末尾へ追加するには、末尾を探し出す必要があります。配列とは違い、直接アクセスできませんから、基本的に先頭の要素から順番に nextポインタをたどっていく必要があります（末尾の位置を高速に探せるように準備しておくことは可能です。これは次章で取り上げます）。

末尾を探す処理は、search_tail関数が行っています。末尾の要素を探す方法は、先頭要素である gHead から始めて、nextポインタをたどっていくという単純なものです。nextポインタが NULL である要素を発見したら、その要素が末尾だと分かります。単純ですが、要素数が非常に多ければ時間が掛かります。しかし、特別に工夫を加えない限り、連結リストとしてはやむを得ない部分でもあります。工夫の例は、今後取り上げます。

末尾の位置が分かれば、新しい要素を追加する作業に取り掛かります。この部分のコードを抜粋します。

/* 追加する要素を作る */
elem = malloc( sizeof(struct LinkedList_tag) );
if( elem == NULL ){
    fputs( "メモリ割り当てに失敗しました。", stderr );
    exit( 1 );
}
elem->value = value;
elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

/* これまで末尾だった要素は、末尾から２番目の位置になる。
   そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする */
tail->next = elem;

まず、要素を作ります。ここでは、動的なメモリ割り当てを行います。単なる、ローカル変数の定義では、関数を抜け出した時点で消えてしまうので正しくありません。

作られた要素の valueメンバに値を格納し、nextポインタには NULL を格納しておきます。今回は末尾に追加するので、nextポインタが NULL になる訳です。

さて、この後が問題です。新しく作られた要素が末尾に来る訳ですから、今まで末尾にあった要素はもはや末尾ではなくなります。ですから、今まで末尾だった要素の nextポインタを、新しく作った要素を指し示すように書き換える必要があるのです。このようにポインタの付け替えを頻繁に行うのが、連結リストの実装の特徴の１つです。ポインタの理解は必須なのです。

要素の探索

要素の削除

続いて、要素の削除です。実装は delete_elem関数を見てください。連結リストの理解で一番難しいのは、恐らく、この削除の部分です。ポインタの理解が曖昧だったり、連結リストの図解イメージが頭に浮かんでいなかったりすると理解できないでしょう。コードだけから理解しようとしないことが懸命です。

削除する要素を探し出す部分は、先ほど見た search_elem関数と同様に、先頭から順番に nextポインタをたどるだけですが、残念ながら search_elem関数を使えません。削除を行うときに、削除する要素の１つ手前の要素をどうにかして知る必要があるからです。

なぜかというと、削除された要素の１つ手前の要素には nextポインタがあり、それは削除する要素を指し示しているからです。削除によってなくなる要素を指し示したままにする訳にはいかないので、書き換える必要があります。

そこで、目的の要素を探しながら、１つ手前の要素も保存しておくようにします。１つ前の要素を指し示すポインタは、prev という名前になっていますが、これは「前の」という意味の「previous」を略したもので、よく使われる名前です。今後は prevポインタと表現します。

prevポインタを保存しておけば、１つ手前の要素の nextポインタの書き換えが可能です。ややこしいですが、prev->next を書き換えるということです。

削除する要素の１つ手前の要素の nextポインタは、削除する要素の１つ後続にある要素を指し示すようになります。すなわち、

prev->next = p->next;

です。この文の実行は、実際に要素を削除するコード (free関数の呼び出し）よりも先に行わなくてはなりません。free関数を呼び出したら、もうポインタp が指す先の状態は不定ですから、p->next は不定になっているためです。

削除後、続けてリストをたどる作業を続けるのなら、p = prev->next として、正しい要素を指し示すポインタp を用意し直します。

要素のクリア

リストの出力

要素を挿入する

先ほどのサンプルでは、要素は末尾に追加する形を取りました。そのためには、要素を先頭からたどっていき、末尾を探し出す必要があり、実は最も時間が掛かる場所に追加しています。

逆に、一番先頭に追加するのが一番高速です。配列の場合、後続の要素をすべてずらす必要がありますから、先頭に追加する方が時間が掛かります。その意味では、効率面では逆の関係にあります。

void add_elem_front(int value)
{
    struct LinkedList_tag* elem;

    /* 追加する要素を作る */
    elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = gHead.next;

    /* ダミーの先頭要素の次は、追加した要素になる */
    gHead.next = elem;
}

先頭に追加するといっても、ダミーの先頭要素よりも手前に置くのではなくて、ダミーの直後に挿入します。ダミーが持つ nextポインタの値を、追加する要素の nextポインタに代入し、ダミーの nextポインタは、追加した要素を指すように書き換えます。

途中に要素を挿入する方法も、結局のところは同じことです。添字が使えないため、挿入位置の指定方法がやや特殊ですが、別に難しくはありません。

次の関数は、指定した値を持つ要素を探し、その要素の直後に挿入します。

int insert_elem(int value, int pos)
{
    struct LinkedList_tag* p;
    struct LinkedList_tag* elem;

    /* 追加位置を探す */
    p = search_elem( pos );
    if( p == NULL ){
        return 0;
    }

    /* 追加する要素を作る */
    elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = p->next;  /* p と p->next の隙間に挿入する */

    p->next = elem;

    return 1;
}

挿入位置を探し出すには、既に作成済みの search_elem関数が利用できます。もし、挿入位置が見つからなければ、0 を返して終了するようにしてあります。成功した場合は 1 を返しています。

ここでもやはり、ポインタを付け替える処理が肝です。挿入位置は、見つけた要素の直後なので、p の次が elem、elem の次が p->next になるように付け替えます。ちなみに、挿入位置がリストの末尾に来る可能性もありますが、この場合でも問題なく動作します。

ライブラリ化の方法

今回使ったサンプルプログラムでは、グローバル変数にダミーの先頭要素を用意しておき、ここを起点としてリストを形作っています。しかし、実戦では、複数のリストを同時に扱いたいこともあるはずですから、この方法はサンプルとしてしか価値がありません。

同時に複数のリストを作るには、ダミーの先頭要素を必要な数だけ作り出せる必要があります。そのためには、先頭要素自体も動的に作ります。そうすれば、必要に応じて何個でもリストを作り出せます。

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


static struct LinkedList_tag* create_list(void);
static void add_elem(struct LinkedList_tag* list, int value);
static void clear_list(struct LinkedList_tag* list);
static void print_list(struct LinkedList_tag* list);
static void delete_list(struct LinkedList_tag* list);
static struct LinkedList_tag* search_tail(struct LinkedList_tag* list);


/* 連結リスト型 */
struct LinkedList_tag {
    int                         value;
    struct LinkedList_tag*      next;
};


int main(void)
{
    struct LinkedList_tag* list0;
    struct LinkedList_tag* list1;
    struct LinkedList_tag* list2;

    /* リストを作る */
    list0 = create_list();
    list1 = create_list();
    list2 = create_list();

    /* リストに要素を追加 */
    add_elem( list0, 10 );
    add_elem( list0, 20 );
    add_elem( list1, 100 );
    add_elem( list1, 200 );
    add_elem( list2, 1000 );
    add_elem( list2, 2000 );

    /* 各リストの中身を出力 */
    print_list( list0 );
    print_list( list1 );
    print_list( list2 );

    /* リストを破棄 */
    delete_list( list0 );
    delete_list( list1 );
    delete_list( list2 );

    return 0;
}

/*
    リストを作成する

    戻り値：
        作成されたリスト。
*/
struct LinkedList_tag* create_list(void)
{
    struct LinkedList_tag* head;

    head = malloc( sizeof(struct LinkedList_tag) );
    if( head == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }

    head->value = 0;
    head->next = NULL;

    return head;
}

/*
    リストを破棄する

    引数：
        list:   破棄するリスト。
*/
void delete_list(struct LinkedList_tag* list)
{
    clear_list( list );

    free( list );
}

/*
    要素を追加する

    引数：
        list:   対象のリスト。
        value:  追加する要素の数値データ。
*/
void add_elem(struct LinkedList_tag* list, int value)
{
    struct LinkedList_tag* elem;
    struct LinkedList_tag* tail;

    /* リストの末尾を探す */
    tail = search_tail( list );

    /* 追加する要素を作る */
    elem = malloc( sizeof(struct LinkedList_tag) );
    if( elem == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( 1 );
    }
    elem->value = value;
    elem->next = NULL;   /* 末尾に追加するので、次の要素は無い */

    /* これまで末尾だった要素は、末尾から２番目の位置になる。
       そのため、nextメンバを書き換えて、新たな末尾の要素を指すようにする */
    tail->next = elem;
}

/*
    要素を空にする

    引数：
        list:   対象のリスト。
*/
void clear_list(struct LinkedList_tag* list)
{
    struct LinkedList_tag* p = list->next;
    struct LinkedList_tag* prev = list;

    while( p != NULL ){
        /* 削除する要素の１つ手前の要素の nextメンバを、
            削除する要素の次の要素を指すように書き換える */
        prev->next = p->next;

        /* 要素は malloc関数で生成したので、free関数による解放が必要。
            上記の prev->next = p->next よりも後で行わないと、不正なポインタが
            prev->next に代入されてしまうことに注意。 */
        free( p );

        p = prev->next;
    }
}

/*
    要素を出力する

    引数：
        list:   対象のリスト。
*/
void print_list(struct LinkedList_tag* list)
{
    struct LinkedList_tag* p = list->next;

    if( p == NULL ){
        puts( "リストは空です。" );
        return;
    }

    while( p != NULL ){
        printf( "%d\n", p->value );
        p = p->next;
    }
}

/*
    末尾の要素を探す

    引数：
        list:   対象のリスト。
    戻り値：
        連結リストの末尾にある要素を指すポインタ。
*/
struct LinkedList_tag* search_tail(struct LinkedList_tag* list)
{
    struct LinkedList_tag* p = list;

    while( p->next != NULL ){
        p = p->next;
    }

    return p;
}

リストを作るには、create_list関数を呼び出します。この関数の内部で、ダミーの先頭要素が動的に作られ、メンバを初期化した後、戻り値として返されます。これを受け取れば、グローバル変数で管理する必要はなくなります。

create_list関数以外の関数はすべてそうですが、引数に struct LinkedList_tag型のポインタを渡すようになっています。ここに、create_list関数が返したポインタを渡せば、そのリストを対象として処理が行われます。これで、リストがいくつあっても、適切なリストに対して処理が行える訳です。

まとめ

練習問題

問題①　この章の最初のサンプルプログラムに、連結リストに含まれている要素の個数を返すコマンドを追加してください。

問題②　この章の最初のサンプルプログラムに、連結リストの要素を逆順に並べなおすコマンドを追加してください（やや難しいです）。

問題③　連結リストの要素を、配列のように添字でアクセスするようにできるでしょうか？実装してみてください。この機能は、実用上どのような問題があるでしょうか。

参考リンク

更新履歴

'2018/2/22　要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2018/2/12　サンプルプログラムの改善（fgets が受け取った改行文字の削除の方法を修正。const、static の付加）

'2017/11/13　サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

'2015/2/21　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/12/20　サンプルプログラムで、コマンド処理の方法を整理。

はてなブックマークに保存	Pocket に保存	Facebook でシェア
Twitter でツイート	Twitter をフォロー	LINE で送る
RSS	管理者情報	プライバシーポリシー

この章の概要