プログラミング作法 第２章 アルゴリズムとデータ構造 ２．７ リスト

　個々の項目がデータと次の項目へのポインタを含んでいる項目の集合を、単一リンクリスト(singly-linked list)という。リストのヘッドは最初の項目を指すポインタで、リストの最後はヌルポインタでマークされる。次ぎに示すのは要素が４個のリストを表した図だ。

　配列とリストには重要な違いがいくつかある。第１に、配列は決まったサイズになるが、リストのサイズは、リストの中身を記憶するのに必要なサイズに、項目ごとにポインタを記憶するためのオーバーヘッドを加算したサイズに常に等しくなる。第２に、リストはほんの少しポインタを交換すれば順序を変更できる。これは配列に必要なブロック移動より安価な作業だ。そして最後に、リストの場合には、項目を挿入したり削除したりしてもほかの項目は移動されない。そのため、要素を指すポインタを何か別のデータ構造に入れておけば、リストに変更が施されてもポインタが無効になったりするようなことはない。
　こうした違いからわかるように、項目の集合が頻繁に変化する場合、とりわけ事前に項目数がわからない場合には、それを記憶する手段としてふさわしいのはリストだ。これに対して配列は、どちらかと言うと静的なデータを得意としている。
　基本的なリスト操作としては、先頭または末尾への新たな項目の追加、特定の項目の探索、特定の項目の前か後への新たな項目の追加、そして項目の削除がある。リストの単純な性質のおかげで、必要に応じてこれ以外の処理も簡単に追加できる。

リストに対する汎用的な処理の説明として

しかしこれに代わる方法として、リストをたどって個々のリスト要素に対して関数を呼び出す単一の関数applyを書くやり方もある。applyに引数を渡して、applyが別の関数を呼び出すたびにその引数が渡されるようにすれば柔軟性が向上する。そのためapplyの引数は、リスト、リストの個々の要素に適用される関数、その関数に渡す引数の３つになる。

/* apply: listpの個々の要素にfnを実行 */
void apply(Nameval *listp, void (*fn)(Naveval *, void *), void *arg)
{
  for( ; listp != NULL; listp = listp->next)
    (*fn)(listp, arg); /* 関数を呼び出す */
}

　リストは途中の項目を挿入したり削除したりするケースにふさわしいだけでなく、サイズがまちまちで順番もばらばらなデータの管理にも適している。とくにそれが言えるのは、スタックのように、アクセスがたいてい後入れ先出し(LIFO)で発生するケースだ。複数のスタックが互いに別個に伸張したり縮退したりするように場合には、配列よりもリストのほうがメモリ使用効率が高くなる。また、文書中の連続した単語のように、情報が未知のアプリオリなサイズのチェインとして固有の順序で並んでいる場合にも良好に動作する。しかし、頻繁な更新とランダムアクセスを両立させなければならない場合には、ツリーやハッシュテーブルのような比較的線形性の弱いデータ構造を使ったほうがいいかもしれない。

情報が未知のアプリオリなサイズのチェイン＝[情報が未知の][アプリオリなサイズの][チェイン]＝情報があることはわかっているが、情報量がわかっておらず、そのサイズを事前に知ることができない、チェイン　という意味だと思う。アプリオリの意味についてはウィキペディア等を参考のこと。
問題２−７
コピー

/* copyNameval:srcの内容をdstにコピーする */
void copyNameval(Nameval *dst, Nameval *src)
{
  for ( ; src != NULL; src = src->next)
    addend(dst, newitem(src->name, src->value);
}

マージ

/* merge:srcの内容をdstの末尾に追加して、新しいリストを返す */
Nameval *mergeNamevel(Nameval *dst, Nameval *src)
{
  Nameval *p;
  if (dst == NULL)
    return src;
  for (p = dst; p->next != NULL; p = p->next)
    ;
  p->next = src;
  return dst;
}

分割

/* divide:srcのリストを先頭からkeyで検索して最初に見つかった位置で分割 */
void divideNameval(Nameval **div1, Nameval **div2, Nameval *src, char *key)
{
  Nameval *p;
  Nameval *pre;
　*div1 = *div2 = NULL;
  pre = NULL;
  for (p = src; p != NULL; p = p->next) {
    if (strcmp(key, p->name) == 0) {
      if (pre != NULL) {
        pre->next = NULL;
        *div1 = src;
      }
      *div2 = p;
      return;
    }
    pre = p;
  }  
}

特定の項目の前への挿入

/* insertFront:src中のtargetの前にitemを追加する */
Nameval *insertFront(Nameval *src, Nameval *target, Nameval *item)
{
  Nameval *tmp;
  Nameval *p;
  Nameval *pre;
  pre = NULL;
  for(p = src ; p != NULL; p = p->next) {
    if (p == target) {
       if (pre != NULL) {
         tmp = pre->next;
         pre->next = item;
         item->next = tmp;
       } else {
         item->next = src;
       }
       return src;
    }
    pre = p;
  }
  /* 見つからなかった場合 */
  return NULL;
}

特定の項目の後への挿入

/* insertEnd:src中のtargetの後ろにitemを追加する */
Nameval *insertEnd(Nameval *src, Nameval *target, Nameval *item)
{
  Nameval *tmp;
  Nameval *p;
  for(p = src ; p != NULL; p = p->next) {
    if (p == target) {
       tmp = p->next;
       p->next = item;
       item->next = tmp;
       return src;
    }
  }
  /* 見つからなかった場合 */
  return NULL;
}

問題２−８
「新しいリスト項目を生成するのではなく、既存の項目を再利用する手法を使うこと」という縛りが難しい。
reverseの再帰バージョン

static Nameval *newtop; /* 逆順リストのトップ */
static Nameval *oldtop; /* 逆順化する前のトップ */
Nameval *reverse(Nameval *src)
{
  oldtop = src;
  reverseList(src);
  return newtop;
}

static Nameval *reverseList(Nameval *src)
{
  Nameval *list;
  if (src != NULL) {
    list = reverseList(src->next);
    if(list != NULL) {
      if (oldtop == src) {
        list->next = NULL;
      } else {
        list->next = src;
      }
    } else {
      /* ここが逆順の先頭になる */
      newtop = src;
    }
    return src;
  } else {
    return NULL;
  }
}

reverseの繰り返しバージョン

Nameval *reverse(Nameval *src)
{
  Nameval *new;  
  Nameval *p1;
  Nameval *p2;

  if(src->next != NULL) {
　  new = NULL;
  } else {
    new = src; /* リストが１つの場合 */
  }
  
  while(src->next != NULL) { 
    for(p1 = src; p1->next != NULL; p1 = p1->next){
      prep1 = p1;
    }
    for(p2 = new; p2 != NULL; p2 = p2->next) {
      prep2 = p2;
    }
    if (new != NULL) {
      prep2->next = p1;
    } else {
      new = p1;
    }
    p1->next = NULL;
    prep1->next = NULL;
  }
  return new;
}

問題２−９
Cの汎用List型

struct genericlist {
  struct *genericlist; /* 単方向リスト */
  void   *data;        /* 汎用データへのポインタ */
};

Cで記述する長所は、型が構造体を使ってシンプルに記述できること。短所は、データを扱う型がvoid*でしか記述できないため、扱うデータ型について使う人が注意を払うことがあること。
C++のテンプレートについては、C++は不勉強なので回答せず。また、Java用の型をObject型のリストを保持するクラスについては、Javaを勉強していないので回答せず
問題２ー１０
テスト内容の考案

まずデータを昇順になるようにリストに記録する。次にリストのデータを先頭から順に取得し、昇順になっているか確認する。