/********************************************************
// アルゴリズムとデータ構造演習：リストを作ろう！
// by TECRA 2008/12/03
//
// TAをやるついでに、自分でも似たようなことをやってみる
// もしかしたら、このページを参考にする人がいるかもしれないし。
// 質問はこちらまで。 tera1984@ui.is.s.u-tokyo.ac.jp
********************************************************/

今回はC言語を使ってリスト(Linked List)構造を作ってみようと思います。
リストとは、簡単に言うと同じタイプのデータがつながった状態になっていることです。
（私なりの解釈なので、間違っているかもしれませんが）

これと似たデータ構造で既に用意されているものとして、配列と言うのがあります。
完全な初心者向けに書いている訳ではないので、これについての説明は省きます。

配列とリストには一長一短があります。
簡単にまとめると、以下のようになります。

                   | 配列 | リスト |
---------------------------------------
列の長さ           | 固定 |  可変  |
ランダムアクセス   | 早い |  遅い  |
データの挿入・削除 | 遅い |  早い  |

なので、用途に応じた使い分けをするのが理想と言えるでしょう。
（まあ、アクセスの早さだとか、データの挿入・削除なんてものは工夫次第である程度改善できるものですが）
一応補足しておくと、ランダムアクセスと言うのはリストの適当な位置のデータを取ってくるまでにかかる時間を言っています。
細かいこと（オーダー）などはネットで他のページを見るか、教科書を見てください。

では、リストの構造について見てみましょう。
リストは、それぞれがデータを１つ（あるいはそれ以上）持つセル（細胞）が連なったものだと考えることができます。
これを簡単な図で説明すると下のようになります。

|------セル------|     |------セル------|     |------セル------|  
|     データ     |     |     データ     |     |     データ     |  
| 次へのポインタ------>| 次へのポインタ------>| 次へのポインタ------> ...
|----------------|     |----------------|     |----------------|

セルの中には、データと、次のセルを指し示すポインタがまとまっていなければなりません。どうやってこれを表現できるでしょうか？そうです、構造体ですね。

/* リストのセル　サンプルコード */
struct List {
  char data[32];      /* データ（今回は文字列） */
  struct List* next;  /* 次の構造体へのポインタ */
};

次は、先ほど定義した構造体を使ってリスト構造を作ってみましょう。

/* セルを使ったリスト　サンプルコード */
#include <stdio.h>
#include <string.h>

/* 構造体の定義 */
struct List {
  char data[32];
  struct List* next;
};

int main()
{
  struct List apple, grape, orange;
  struct List* p;
  
  /* 初期化 */
  p = &apple;
  strncpy(apple.data, "apple\n", 32);
  apple.next = &grape;
  strncpy(grape.data, "grape\n", 32);
  grape.next = &orange;
  strncpy(orange.data, "orange\n", 32);
  orange.next = NULL;
  
  /* 表示させてみる */
  while (p != NULL) {
    printf(p->data);
    fflush(stdout);
    p = p->next;
  }
  
  return 0;
}

今回はapple、grape、orangeという３つのセルをつないでリストを作りました。
初期化が終わった時点では、変数同士の関係は下のようになっています

      |-----apple-----|   |-----grape-----|   |-----orange-----|
 p -->| data("apple") |   | data("grape") |   | data("orange") |
      |     next--------->|     next--------->|      next---------> NULL
      |---------------|   |---------------|   |----------------|

NULLというのは、何も指していないことを意味します。
ポインタ変数は宣言した時点ではメモリ上のどこを指しているのか分からないため、すぐに値を代入するのでなければNULLで初期化しておくと良いでしょう。

表示部分では、pが何らかの構造体を指していればその内容を表示して次を見に行く、と言う作業を繰り返し行っています。
"->"は「アロー演算子」と言って、ポインタが指し示す構造体の要素を取って来たいときに使います。
すなわち、

p->data

は、

(*p).data

と同じ意味です。

しかし、このプログラムはいまいち面白味に欠けます。
最初からapple、grape、orangeしか使わないと分かっていれば、配列を使って管理すればいいだけの話ですし。

そこで。

プログラム実行時にユーザからの入力に応じて自由に要素を追加したり、削除したりすることができるリストを作ってみましょう。
リストの要素数が動的に変化するため、ただの配列ではこのプログラムを表現できません（いや、工夫次第でもちろん表現できたりするのですが・・・）
まず、プログラムの大まかな流れは以下のようになります。

ユーザからの入力を受け付ける <-------
  ↓              ↓                 |
終了？    挿入、削除、表示           | 繰り返し
  ↓              ↓                 |
終了する  要求されたタスクを行う ----

これをコードで書くと、次のようになります

/* プログラムの大まかな流れ　サンプルコード */
#include <stdio.h>

int main()
{
  /* 変数の宣言 */
  int cmd = 1;
  
  while (cmd != 0) {
    printf("コマンドを入力してください\n");
    printf("表示:1 挿入:2 削除:3 終了:0 -> ");
    scanf("%d", &cmd);
    scanf("%*c");       /* 改行を読み飛ばしている */
    
    switch (cmd) {
    case 1:
      /* リストを先頭から表示する */
      break;
    case 2:
      /* リストに要素を挿入する */
      break;
    case 3:
      /* リストの要素を削除する */
      break;
    case 0:
      /* 終了処理 */
      printf("終了します。\n");
      break;
    default:
      printf("未定義のコマンドです。\n");
    }
  }
  
  return 0;
}

特に説明すべきことは無いと思います。
リストのセルは、先ほど定義したものを流用しましょう。

/* リストのセルに関するコード */
#define BUFSIZE 32

struct List {
  char data[BUFSIZE];
  struct List* next;
};

今回、dataの長さは様々なところで使うことになると思われるので、defineで定義してあげます。
こうすることによってコード内での一貫性を保ち、また後になって文字列の長さを変更したくなったときにもdefineの部分を書き換えるだけで済みます。

では、リストに関するコードを書いていきましょう。
まず、メインとなるプログラムはリストの先頭を指し示すポインタを持っていなければなりません。

struct List* head = NULL;

まずはリストの挿入から考えて行きましょう。
ユーザから挿入する文字列を受け取り、先ほどのheadが指すリストの最後尾に追加していきましょう。

/* 入力を受け取るためのバッファ */
char str[32];

/* 挿入：呼び出し部分 */
printf("挿入する文字列を入力してください :");
fgets(str, BUFSIZE, stdin);
head = add(head, str);
printf("%sが追加されました。\n", str);

追加するために新しくサブ関数を作成しましょう。
このように機能ごとに関数で切り分けることで、使いまわしがしやすくなります（いっそ別ファイルに作成するのが望ましいのですが、今回はそこまではしません）し、後ほど説明する再起という考え方を表現することができるようになります。
add関数では、リストの先頭のポインタと挿入する文字列を受け取り、挿入が完了したリストの先頭のポインタを返すことにします。

では、add関数の中身を書いていきましょう。
add関数では、与えられたポインタの先を見て、何も指していなければそこに新たなセルを作り、セルのポインタを返します。
既にセルがある場合は、次々とセルの先を見ていきます。
既にセルがある場合の返り値はどうしたらいいでしょうか？
新しくセルが作られた場合、そのセルのポインタが返ってくるので、そのポインタをnextにしてあげます。
既にセルがある場合、nextにはもともとあったセルのポインタが収まっていれば良いわけですから、セル自身のポインタを返してあげればいいわけです。
コードにすると、以下のようになります

/* add関数部分　サンプルコード */
struct List* add(struct List* lst, char* str)
{
  struct List* new;
  
  if (lst == NULL) {
    new = (struct List*)malloc(sizeof(struct List));
    if (new == NULL) { /* エラー処理 */
      printf("mallocに失敗しました。\n");
      return NULL;
    }
    new->next = NULL;
    strncpy(new->data, str, BUFSIZE);
    return new;
  } else {
    lst->next = add(lst->next, str);
    return lst;
  }
}

strncmpを使うために<string.h>、mallocを使うために<stdlib.h>のインクルードが必要になります。ファイル先頭に追加しておきましょう。
サンプルコードのelse部分では再帰的にaddを呼び出しています。このように再起を使うとコードがシンプルになります（概念はややとっつきづらいですが）。
さて、これでリストに要素を追加することができるようになりました。しかし、このままだと表示関数が無いので結果の確認ができませんね。
では次に表示関数を作ってみることにしましょう。
表示関数の中身は、リストの最後尾（NULL）に到達するまでひたすらデータを書き出すようにします。

/* 表示：呼び出し部分 */
show(head);

/* show関数部分　サンプルコード */
void show(struct List* lst)
{
  if (lst == NULL) return;
  printf(lst->data);
  show(lst->next);
}

再起を使えば、このようにシンプルに書くことができます。
次は、リスト内の要素を削除する関数を作りましょう。まずはユーザから入力を受け取って、それを関数に渡すようにしましょう。
関数の引数はリストの先頭ポインタと、削除するためのキーワード、返り値は削除した後のリストの先頭ポインタを返すようにしましょう。

/* 削除：呼び出し部分 */
printf("削除する文字列を入力してください :");
fgets(str, BUFSIZE, stdin);
head = del(head, str);

delの中身を考えます。
先頭から順にdataの内容と与えられた文字列を比較して、それらが等しくなければ次を見に行きます。返り値には自分自身のアドレスを返し、それをnextに入れてもらうようにします。
もし等しかった場合、その要素をfreeによって解放すると同時に、あらかじめ退避させておいたセルのnextを返すようにすれば次からはその要素だけを飛ばしてセル同士がつながった状態になります。
また、最後まで見て無かった場合は、その処理をしなければなりません。
コードにすると、以下のようになります。

/* del関数部分　サンプルコード */
struct List* del(struct List* lst, char* str)
{
  struct List* tmp;
  
  if (lst == NULL) { /* エラー処理 */
    printf("%sが見つかりませんでした。\n", str);
    return NULL;
  }
  
  if (strncmp(lst->data, str, BUFSIZE) == 0) { /* 要素が見つかった */
    tmp = lst->next; /* ポインタの退避 */
    free(lst); /* 解放 */
    printf("%sを削除しました。\n", str);
    return tmp;
  } else {
    lst->next = del(lst->next, str);
    return lst;
  }
}

さて、表示、挿入、削除の関数を作成しました。
これで必要な関数は全部でしょうか？
実は、まだ最後に大切な作業が残っています。

mallocのおはなしをしたときに、「mallocで確保した領域はちゃんとfreeすること」という注意をしたと思います。
終了のときにfinalizeという関数を呼ぶことにしましょう。

/* 終了処理：呼び出し部分 */
finalize(head);

finalize関数はfor文、while文でも十分シンプルに書けますが、せっかくなので再起関数で統一してみましょう。

/* finalize関数部分　サンプルコード */
void finalize (struct List* lst)
{
  struct List* tmp;
  
  if (lst != NULL) {
    tmp = lst->next;
    free(lst);
    finalize(tmp);
  }
}

最後に、今まで作った関数を全部まとめると、下のようになります。

/* リスト　サンプルコードまとめ */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* リストのセルに関するコード */
#define BUFSIZE 32

struct List {
  char data[BUFSIZE];
  struct List* next;
};

/* add関数部分　サンプルコード */
struct List* add(struct List* lst, char* str)
{
  struct List* new;
  
  if (lst == NULL) {
    new = (struct List*)malloc(sizeof(struct List));
    if (new == NULL) { /* エラー処理 */
      printf("mallocに失敗しました。\n");
      return NULL;
    }
    new->next = NULL;
    strncpy(new->data, str, BUFSIZE);
    return new;
  } else {
    lst->next = add(lst->next, str);
    return lst;
  }
}

/* del関数部分　サンプルコード */
struct List* del(struct List* lst, char* str)
{
  struct List* tmp;
  
  if (lst == NULL) { /* エラー処理 */
    printf("%sが見つかりませんでした。\n", str);
    return NULL;
  }
  
  if (strncmp(lst->data, str, BUFSIZE) == 0) { /* 要素が見つかった */
    tmp = lst->next; /* ポインタの退避 */
    free(lst); /* 解放 */
    printf("%sを削除しました。\n", str);
    return tmp;
  } else {
    lst->next = del(lst->next, str);
    return lst;
  }
}

/* show関数部分　サンプルコード */
void show(struct List* lst)
{
  if (lst == NULL) return;
  printf(lst->data);
  show(lst->next);
}

/* finalize関数部分　サンプルコード */
void finalize (struct List* lst)
{
  struct List* tmp;
  
  if (lst != NULL) {
    tmp = lst->next;
    free(lst);
    finalize(tmp);
  }
}

/* メイン関数 */
int main()
{
  /* 変数の宣言 */
  int cmd = 1;
  struct List* head = NULL;
  char str[32];
  
  while (cmd != 0) {
    printf("コマンドを入力してください\n");
    printf("表示:1 挿入:2 削除:3 終了:0 -> ");
    scanf("%d", &cmd);
    scanf("%*c");
    
    switch (cmd) {
    case 1:
      /* リストを先頭から表示する */
      show(head);
      break;
    case 2:
      /* リストに要素を挿入する */
      printf("挿入する文字列を入力してください :");
      fgets(str, BUFSIZE, stdin);
      head = add(head, str);
      printf("%sが追加されました。\n", str);
      break;
    case 3:
      /* リストの要素を削除する */
      printf("削除する文字列を入力してください :");
      fgets(str, BUFSIZE, stdin);
      head = del(head, str);
      break;
    case 0:
      /* 終了処理 */
      finalize(head);
      printf("終了します。\n");
    default:
      printf("未定義のコマンドです。\n");
    }
  }
  
  return 0;
}

ちなみに、c++環境ではnewが予約語なので、このままだとコンパイルに失敗します。適当に変数名を変えてください。