C言語 リスト構造

Question

C言語(又はＣ++)でのリスト構造について詳しく教えて欲しいです。new演算子からわからないです。

Comments

[argius]

new演算子がわからないレベルでしたら、C言語かC++のどちらかに絞った方が良いと思います。new演算子はC言語には無いC++の機能です。

Answer 1

まずC言語にはnew 演算子はありません。
C++でのリスト構造には、stlで用意されたコンテナとしてstd::listが存在します。たいていの場合は、それを利用します。

Cでリスト構造を作成するには、多くの場合、構造体のポインタをメンバとして持ちます。例えば次の様な形です。

struct No {
  int n;
  struct No* next;
}

この場合、nextにNo構造体のポインタを格納することで、リスト構造を作成します。
例えばこのように使用します。

struct No number;
struct No* pNum = &number;
for ( i = 2; i < 11; i++) {
  pNum->n = i;
  pNum->next = (struct No*)malloc(sizeof(struct No));/* C++の場合はnewでもOK */
  pNum = pNum->next;
}

こうすることで、1から10までの数字のリストができたことになります。
（上のコードは適当に書いているので、間違っているかも）

なおリストと配列の違いは、メモリ上で隣り合うかどうかです。
配列の場合、10個の要素は必ず隣り合うメモリに展開されますが、リストの場合はポインタを保持しているだけなので、隣り合ってはいません。

配列に対して、リストを使用するメリットは、データの挿入に強いことです。
例えば1と2の間に、100を挿入したい場合、配列の場合は2がある場所の後ろすべてを1つずつ、ずらして行かなければならないのに対し、リストの場合は、次の要素のポインタを変更するだけで対処できます。

Answer 2

リスト構造を使う時、１つ１つの要素をnewで確保することは多いですが、必ずしもそうしなければならないわけではないです。
このことを念頭に下記を見られるとよいと思います。

ロベールのＣ＋＋教室
第１部 先ずは基本から 第７１章 借りたら返す
第３部 さらなる高みへ... 第３２章 数珠繋ぎ

Answer 3

とりあえず、以下のページを見ると理解が進むと思います

第十一回-02 new 演算子によるメモリの動的確保