先頭へ戻る

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

Programming Place Plus トップページ – アルゴリズムとデータ構造編

先頭へ戻る

この章の概要

この章の概要です。


連結リスト

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

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

要素を連結するために、Ｃ言語であればポインタを使います。ここからはポインタの理解が必須事項ですから、不安がある場合はＣ言語編で先に学習してください。

【上級】ポインタや、それに類する機能が使えないプログラミング言語の場合は、配列で代用することがあります。どの要素が連結されているかを添字を使って表現することによって、一応実現できます。

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

要素が Ａ→Ｂ→Ｃ→Ｄ のように、一方向に連結されるものを単方向リストと呼びます。Ａ⇔Ｂ⇔Ｃ⇔Ｄ　のように、前にも後ろにも連結されるものを双方向リストと呼びます。

また、違う観点からも分類できます。リストに端（先頭と末尾）があるものを線形リストと呼び、最初の要素と最後の要素も連結してループ状のかたちになっているものを循環リストと呼びます。

これら２つずつの組み合わせによって、以下の４つのタイプがあります。

この章では、一番シンプルな「単方向で線形なリスト」、すなわち単方向線形リストだけを取り上げます。ほかのタイプについては、次の章で解説します。

単方向線形リスト

単方向線形リストのイメージ図は次のようになります。

単方向線形リスト

この図で、２つの □ が組み合わさったものが１つの要素を表しています。「35」や「24」といったものが、その要素が持つ値（データ）だと思ってください。もう１つの空の □ がポインタ変数になっており、青い線によって、次の要素を指し示しています。

１つの要素は、次のような構造体で表現できます。

struct LinkedList_tag {
    int                         value;  // データ
    struct LinkedList_tag*      next;   // 次の要素へのポインタ
};

ここでは、扱いたいデータが int型であることを想定していますが、もちろんどんな型のデータを持たせても構いません。

// データが文字列
struct LinkedList2_tag {
    const char*                 name;
    struct LinkedList_tag*      next;
};

// データが複数
struct LinkedList2_tag {
    const char*                 name;
    int                         age;
    struct LinkedList_tag*      next;
};

連結リストを実装するカギとなるのは、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];
    get_line( buf, sizeof(buf) );

    enum Cmd_tag cmd = CMD_NUM;
    for( int 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[cmd]();
    }
    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* tail = search_tail();

    // 追加する要素を作る
    struct LinkedList_tag* 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.next が NULL なので、gHead はリストの先頭であると同時に末尾でもあります。この後、addコマンドによって要素を追加すれば、gHead は末尾ではなくなりますが、先頭ではあり続けます。

gHead.value に 0 を格納していることには、特に意味はありません。どのみちダミーの要素なので、この値が参照されることはないので、何が入っていても構いません。しかし、Ｃ言語では有効な値を与えないと不定な状態のままですから、一応適当な値を入れておいた方が良いでしょう。

末尾への要素の追加

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

配列と違って、連結リストの各要素を添字でアクセスすることができませんから、末尾へ追加するには、まずは末尾の要素を探し出さなければなりません。

そのためには、先頭の要素から順番に nextポインタをたどっていく必要があります。nextポインタが NULL の要素を発見したら、それが末尾の要素です。この処理は、search_tail関数が行っています。

想像どおり、末尾を探す処理は効率が悪いです。リストの要素数が多ければ多いほど時間がかかることも想像できると思います。

末尾を探す時間を減らすには、末尾の要素をどこかに記憶しておくと良いでしょう。

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

// 追加する要素を作る
struct LinkedList_tag* 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ポインタを、新しく作った要素を指し示すように書き換える必要があります。

このようにポインタの付け替えを頻繁に行うのが、連結リストの実装の特徴の１つです。ポインタの理解は必須なのです。

要素の探索

次に、目的の要素の探し方を確認しておきましょう。この処理は、search_elem関数が行っています。

方法としては、やはり先頭要素から順番に nextポインタをたどっていくだけです。nextポインタが NULL の要素を見つけるまでの間に、valueメンバの中身が目的の値と一致しているものがあるかを調べています。

なお、search_tail関数と違い、最初に探す場所が gHead ではなくて gHead.next から始まっていることに注意してください。gHead はダミーの要素なので、ここを探索対象に加えてしまうと、偶然ダミーデータと一致してしまうかもしれません。

要素の削除

続いて、要素の削除です。

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

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

なぜかというと、削除する要素の１つ手前の要素を知りたいからです。要素が削除されたら、その手前の要素の nextポインタが、削除された要素の次の要素を指すように書き換わらなければならないのです。

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

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

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

prev->next = p->next;

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

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

要素のクリア

要素の削除の方法さえ理解すれば、全要素を削除する処理はそれほど苦労しないでしょう。実装は、clear_list関数を見てください。

今回はすべての要素がなくなるので、１つ手前の要素の nextポインタを書き換える必要はありません。それでも prevポインタを作っているのは、free関数の呼び出し後に、続きから再開できるようにするためだけです。

リストの出力

最後に、リストの全要素の出力です。これは、print_list関数を見てください。

ここまで理解できていたら、この関数は簡単です。先頭要素から nextポインタをたどりながら、データを出力するだけです。

要素を挿入する

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

逆に、先頭に追加するのが一番高速です。配列の場合だと、後続の要素をすべてずらす必要がありますから、先頭に追加する方が時間が掛かりますが、単方向線形リストでは、そのような作業が不要です。

先頭への要素の追加は、次のようなコードになります。

void add_elem_front(int value)
{
    // 追加する要素を作る
    struct LinkedList_tag* 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 = search_elem( pos );
    if( p == NULL ){
        return 0;
    }

    // 追加する要素を作る
    struct LinkedList_tag* 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 = 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* tail = search_tail( list );

    // 追加する要素を作る
    struct LinkedList_tag* 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;
}

実行結果：

10
20
100
200
1000
2000

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

リストを削除するときには、delete_list関数を使います。

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

このような実装をさらにヘッダファイルとソースファイルに分割して行うと、コードライブラリの ppps_int_slist.c と ppps_int_slist.h のようなかたちになります。

まとめ

単方向線形リストの特徴は、次のようになります。

[長所]

[短所]


練習問題

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

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

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


解答ページはこちら。


参考リンク


更新履歴

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

≪さらに古い更新履歴を展開する≫


前の章へ　（第２章　多次元配列）

次の章へ　（第４章　連結リスト②（双方向・循環））

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

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