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

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 配列と連結リストの比較 (C言語)

配列と連結リスト(Linked-List)の違いについて (C言語)

配列と連結リスト(Linked-List)は、共にメモリ上にデータを格納する方法です。
ここでは、配列と連結リストの長所、短所について、説明します。

以下のデータを扱う場合を例に挙げます。
typedef struct _tagPeople {

    int  nID;
    char * pszName;

} people;
個人データを格納する構造体 people。 「そのpeople内には、IDを格納するnIDと、氏名を格納するpszNameが、メンバとして存在している」 という状況です^^;) ユーザーから次々と入力されてくる個人データを、上記peopleを使用し格納します。

1.配列を使用してデータを格納する場合

【パターン1:静的配列】
people datas[100];
配列のサイズを最初から固定(この場合100人分のデータ)しておく方法です。 入力されるデータ数が分かっている場合は、この方法が最も便利です。 デメリットとしては、メモリを無駄に消費する可能性がある事や、 (ex 100人分のデータ領域を割り当てておいても、10人分しかデータが入ってこなかったら、90人分のメモリ領域が無駄になる。) 固定サイズ以上のデータを保持できない事です。 (ex 100人分のデータ領域を割り当てておいて、110人分のデータが入力された場合、最後の10人分のデータは保持できない。) 【パターン2:動的配列】
if ( !(datas = (people *)malloc(sizeof(people) * 100))) {
    // error処理
}

if ( !(tmp = (people *)realloc(datas, 150))) {
    // error処理
}

// reallocの戻り値は、別変数に一旦保管してNULLチェックをかける
datas = tmp;

free(datas);

datas = NULL;
tmp   = NULL;
malloc()で動的にメモリを割当、メモリサイズを変更する場合はrealloc()を使用します。 入力されるデータ数が不定な場合は、静的配列を使用する場合に比べ、データの取りこぼし 及び メモリの無駄遣いが少ないです。 デメリットとしては、メモリの割当てに失敗する可能性があること。 その為、malloc, realloc後のエラーチェックは必須です。

2.連結リスト(Linked-List)を使用してデータを格納する場合

people構造体に、以下の様にメンバを追加します。
typedef struct _tagPeople {

    int  nID;
    char * pszName;
    struct _tagPeople * next

} people;
そして、グローバル変数としてpeople構造体へのポインタを宣言しておき(便宜上 g_head)、 データが入力される都度、g_headから順に、構造体メンバのnextを経由して、メモリ領域を論理的に繋いで行きます。 ※ ちなみに、データの1つ1つ(この場合people構造体のインスタンス)をノード(NODE)、   ノードとノードを繋ぐ線の事をリンク(LINK)といいます。 ・・・これだけの説明では分かりづらいと思うので、図にしてみました。 まずは配列
配列のメモリ展開図
データが整列してメモリ上に格納されています。 次に連結リスト
リスト(Linked-List)のメモリ展開図
メモリ上の空地に、飛び飛びでデータを格納。そして、次の格納場所のメモリアドレスを、ポインタとして所持しています。 配列は、データへのランダムアクセス速度が超高速です(※ 予め配列の添字が分かっている場合)。 逆に連結リストは、任意のデータへアクセスする場合、g_headから順に辿ってアクセスを行う為、低速です。 しかし、サイズ数が不特定の大容量データを扱う場合、 動的配列を使用した場合のマシン負荷は、かなりのものになります。 (malloc, reallocで、ヒープ領域中の連続した巨大領域を取得するのは、あまりよろしくない...) 一方連結リストは、メモリの使用効率という点から考えると、 サイズ数が不定で大容量のデータを扱う場合に適しています。 (各構造体中に、連結リスト形成の為の余計なポインタが増えてしまうという点を考慮しても、メリットの方が大きい) 次ページ以降に、連結リストの具体的なソースコードが載せてあります。
単方向連結リスト(Simple Linked-List) へ続く。
         このエントリーをはてなブックマークに追加   


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




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





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




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