ポインター（+malloc関数）を利用した線形リストの実現

これが本講義でベストとする方法です。まず上記の配列を利用する方法には問題があります．配列はデータがいくつあるのかをあらかじめ決めないといけません。→ 漠然と100くらいとか 1000くらい．．．として決めておくとメモリが無駄になります． プ ログラム中で宣言された変数は，コンパイル時にスタック領域に確保されます．例えば， int a[100]と宣言した → int型のメモリ領域が100個分確保したということです．もし，100個以上のデータが出現したらそれ以上は格納できません．

この問題を解決するのが ポインターとmalloc/calloc関数を利用した動的メモリ確保です．

mallocで動的に生成されたメモリ領域は名前（変数名）がありませんが、ポインタ変数によりその領域を指し示す（実質、変数名を割り当てる）ことができます。

関連項目

以下の項目は理解しておくこと

• ポインター
• malloc/calloc関数

ポインタの復習

例えば、上記の図のように、

P=mallocNode();

と書くと、mallocNodeで確保された領域は、Pというポインタ変数で呼ぶ事ができます。そして、その状態で

Q=P;

と書くと、mallocNodeで確保された領域は、QでありまたPでもあります。

ポインターを利用した線形リストのイメージ

構造体の構造

下記のように、次のデータの位置を指し示すポインタ変数がメンバーとしてあることに注意してください

５．topの次にnewが来るように（newをリストの末尾にする）

６．その領域の場所をポインタ変数（tail）で捕捉

７．次のデータを格納するメモリ領域を動的確保（mallocNode）

８．その領域の場所をポインタ変数（new）で捕捉

９．newをリストの末尾に追加

１０．末尾のノードをtailとする

データの数だけmalloc で メモリ（変数）を生成し，作成されたメモリ領域の位置（アドレス）をたどっていくようにリストを作ればよいわけですが、いきなりそのプログラムを見ても意味不明だと思いますので、まずは簡単なサンプルで説明します。

１．とりあえず2チーム分のデータを格納するメモリ領域をcallocで確保し、ポインタと関連付けます。

Node *node1 = mallocNode();

Node *node2 = mallocNode();

この記述が意味することは，

「mallocNode関数によって確保された領域を，node1、node2というポインタで指し示します」ということです．

node1、node2にはそれぞれ異なったメモリ領域が確保されたということを理解してください。

２．各ノードにデータを格納する

node1->name="nishioka";

node1->name="yamato";

３． 構造体メンバーのnextに次のノードの情報を渡す

node1->next = node2;

この記述は、「node1の次 は、node2である」ということを意味します。

４．先頭ノードから検索する

以下のように辿っていきます。

Node *head =node1;

Node  *now = head;

  //（コ）リストの端になるまでnowを移動しながらデータを出力

  while(now!=NULL){

    printf("%s\n",now->data);

    now=now->next;

  }

注意！メモリの解放を意識すること

callocで確保したメモリ領域は、free関数を利用して解放するのが一般的です。ただし、解放したアドレスの対して再度解放しようとした際の挙動は、環境（OS）などによって変わってきます。