トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 双方向連結リスト(Doubly Linked-List) (C言語)

双方向連結リスト(Doubly Linked-List)とは?

前回の説明 (単方向連結リスト)を踏まえ、双方向連結リストについて説明します^^;)

双方向連結リスト(Doubly Linked-List)とは、
リストの双方向(前・後)にリンクがつながっている連結リストの事です。
単方向連結リストでは、「次のノード」を指すリンクしか存在しませんでしたが、
双方向連結リストでは、「次のノード」と、「前のノード」を指すリンクが存在します。


図にするとこんな感じ↓
双方向連結リスト(Doubly Linked-List)

リストの先頭を指すポインタ(g_head)と、末尾を指すポインタ(g_tail)があります。

・・・なんだか線がゴチャゴチャしていて非常に見辛いですが、綺麗に整理された図よりも、こういったゴチャゴチャした図の方が、
より連結リストの特性を表しています。(←という言い訳^^)

それでは、さっそくコーディング開始~♪

ノードの定義・先頭ポインタ

まずは、ノードを定義します。そして、g_headとg_tailを宣言します。
typedef struct _tagNode {

    // 重複不可のID
    int nId;

    // 重複可能な名前
    char * pszName;

    struct _tagNode * prev;
    struct _tagNode * next;

} node;

node * g_head;
node * g_tail;
単方向連結リストで使用したノードに、struct _tagNode * prev;が追加されているだけです^^;)

ノードの作成

続いて、ノードのインスタンスを作成し、そこへユーザからの入力を埋め込む関数を作成します。
/*
 新規ノードの作成

 return : 成功 - 作成されたnodeのポインタ / 失敗 - NULL
*/
node * makeNode()
{
    node * n;
    int  nId, nLen;
    char buff[100];

    // 新規ノードの作成
    if ( ! (n = (node *)malloc(sizeof(node))) ) {
        return NULL;
    }

    memset(buff, '\0', sizeof(buff));

    puts("IDを入力して下さい。->");
    scanf("%d", &nId);

    if (listSearch(nId)) {
        printf("[%d]のIDは既に登録されています。\n", nId);
        return NULL;
    }

    puts("名前を入力して下さい。->");
    fflush(stdin);
    fgets(buff, 100, stdin);
    nLen = strlen(buff);
    buff[nLen - 1] = '\0'; // 文字列最後の改行を削除

    if ( ! (n -> pszName = (char *)malloc(sizeof(char) * nLen)) ) { // 文字列最後のNULL文字分を考慮し、(nLen + 1)とする必要はない。
        free(n);
        return NULL;
    }

    // 新規ノードへIDをセット
    n -> nId = nId;

    // 新規ノードへ名前をセット
    memset(n -> pszName, '\0', sizeof(char) * nLen);
    strcpy(n -> pszName, buff);

    // 新規ノードのリンクを初期化
    n -> prev = NULL;
    n -> next = NULL;

    return n;
}
説明は略w 詳細はこちらを参照して下さい。

リストへの追加

作成したノードを無条件リストの末尾へ追加する関数です。
/*
 連結リストへの追加

 add    : 追加するノード
 return : 成功 - 0 / 失敗(重複IDを入力した等) - 1
*/
int listAdd(node * add)
{
    if (! add) {
        return 1;
    }

    if (! g_head) {
        // 1つもノードが登録されていない場合
        g_head = g_tail = add;
    }
    else {
        g_tail -> next = add;
        add    -> prev = g_tail;
        g_tail         = add;
    }

    return 0;
}
g_headがNULLの場合、つまり、1つもリストにノードが登録されていない場合は、g_head, g_tailに新規ノードをセットします。 空の双方向連結リスト(Doubly Linked-List)にノードを追加 g_headがNULLで無い場合は、リストの末尾ノードを表すg_tailのnextに、新規ノードをセットし、 新規ノードのprevにg_tailをセットします。そして、新規ノードをg_tailにセットします。 双方向連結リスト(Doubly Linked-List)の末尾(Tail)にノードを追加

リストへソート(昇順・降順)追加

上で紹介したlistAdd()関数は、データを無条件でリストの後ろに繋げて行く関数でしたが、 以下は、ソートをかけながらノードをリストへ追加する関数です。
/*
 連結リストへID順にソートしながら追加

 add    : 追加するノード
 return : 成功 - 0 / 失敗(重複IDを入力した等) - 1
*/
int listSortAdd(node * add)
{
    node * tmp;

    if (! add) {
        return 1;
    }

    if (! g_head) {
        // 1つもノードが登録されていない場合
        g_head = g_tail = add;
    }
    else {
        tmp  = g_head;
        while (tmp) {

            if (add -> nId < tmp -> nId) {

                if (tmp == g_head) {
                    // リストの先頭に登録
                    add -> next    = g_head;
                    g_head -> prev = add;
                    g_head         = add;
                }
                else {
                    // リストの中間(この場合、tmpの前)に登録
                    tmp -> prev -> next = add;
                    add -> prev         = tmp -> prev;

                    add -> next         = tmp;
                    tmp -> prev         = add;
                }

                break;
            }

            if (tmp -> next) {
                tmp = tmp -> next;
            }
            else {
                // リストの末尾に登録
                g_tail -> next = add;
                add    -> prev = g_tail;
                g_tail      = add;

                break;
            }
        }
    }

    return 0;
}
関数の概要はこちらを参照して下さい。 新規ノードをセットする場所を探した後は、以下の3パターンで処理を行います。

① リストの先頭に登録する場合

追加ノードのnextに、現在のg_headを。そして、g_headへ追加ノードをセットします。 双方向連結リスト(Doubly Linked-List)の先頭にノードを追加

② リストの中間に登録する場合

追加場所の1つ前ノードのnextに、追加ノードをセット。そして、追加ノードのnextに、追加場所の1つ後ノードをセットします。 そして、新規ノードのprevに、追加場所の1つ前ノードをセット。そして、追加場所の1つ後ノードのprevに、追加ノードをセットします。 双方向連結リスト(Doubly Linked-List)の中間にノードを追加

③ リストの末尾に登録する場合

listAdd()の場合と同様です。

リストの検索

IDを元にノードを検索し、該当IDを持つノードを発見したら、ノードのポインタを返す関数です。
/*
 リストの検索

 nSearchId : 検索するID
 return    : 探し出したノード
*/
node * listSearch(int nSearchId)
{
    node * tmp = g_head;

    while (tmp) {
        if (tmp -> nId == nSearchId) {
            return tmp;
        }
        tmp = tmp -> next;
    }

    return NULL;
}
g_headから順に、ループで辿りながら検索を行います。

リストの削除

指定されたIDのノードを削除する関数です。
/*
 リストの削除

 nDeleteId : 削除するID
 return    : 成功 - 0 / 失敗(該当IDを持つノードがない) - 1
*/
int listDelete(int nDeleteId)
{
    node * del;

    if ( ! (del = listSearch(nDeleteId)) ) {
        return -1;
    }
    else {

        if (del == g_head) {
            // 削除対象ノードがリストの先頭
            g_head         = g_head -> next;

            if (g_head) {
                g_head -> prev = NULL;
            }
            else {
                // 全て削除した場合
                g_head = g_tail = NULL;
            }
        }
        else if (del == g_tail) {
            // 削除対象ノードがリストの末尾
            g_tail         = g_tail -> prev;
            g_tail -> next = NULL;
        }
        else {
            // 削除対象ノードがリストの中間
            del -> prev -> next = del -> next;
            del -> next -> prev = del -> prev;
        }

        free(del -> pszName);
        free(del);

        return 0;
    }

    return 1;
}
g_headから順に辿り、削除するノードを検索します。そして、削除するノードを探し出したら、以下の3パターンで処理を行います。

① 削除ノードが、リストの先頭(Head)の場合

g_headへ、現在のg_headのnextをセット。g_headのprevにNULLをセット。その後、対象ノードを削除 双方向連結リスト(Doubly Linked-List)の先頭(Header)を削除

② 削除ノードが、リストの中間に存在する場合

削除ノードの前ノードのnextに、削除ノードの後ノードをセット。 削除ノードの後ノードのprevに、削除ノードの前ノードをセット。その後、対象ノードを削除 双方向連結リスト(Doubly Linked-List)の中間を削除

③ 削除ノードが、リストの末尾(Tail)の場合

g_tailのprevをg_tailににセット。g_tailのnextをNULLにセット。その後、対象ノードを削除 双方向連結リスト(Doubly Linked-List)の末尾(Tail)を削除

リストの初期化(全削除)

リストを全削除する関数です。
/*
 連結リストの初期化(全削除)を行う
*/
void listInit()
{
    node * tmp, * del;

    if (g_head) {
        tmp = g_head;

        while (tmp) {
            del = tmp;
            tmp = tmp -> next;

            free(del -> pszName);
            free(del);
        }
    }

    g_head = g_tail = NULL;
}
g_headから順に辿り、全てのノードを削除します。
実行ファイルが作成できる形でソースコードを置いておくので、よろしければ参考にして下さい^^;) doubly-linked-list.h  doubly-linked-list.c  test.c 双方向連結リストは、検索関数でノードのポインタを取得した後、様々な処理がスマートにできるのが良いですね^^;) また、リスト追加時にソートを掛けておけば、表示の際、g_headから順に辿るだけではなく、g_tailから順に辿る事もできるので便利です。
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。