リスト・二分木の実現するにあたりなぜ構造体を定義する必要があるのか？ 配列では難しいのか？

Question

C言語にてスタック・キューでは配列で実現しているのに、
リスト・二分木だけは、構造体を定義しなければならないのですが、
なぜリスト・二分木だけは構造体を定義しないといけないのですか？　

スタック・キューでは構造体の定義は不要なのに
逆に、リスト・二分木では構造体を定義する必要があるのですか？

配列では効率が悪いのですか？

回答のほうよろしくお願いいたします。

Comments

[swordone]

それ、どこで聞いたor読んだ話ですか？

Answer 1

作れます。ヒープは二分木ですが、配列が使われることが多いですし、.NET の List は配列で実装されています。
ただ配列の場合は挿入削除の効率が悪かったりする事があるので、何が最適なのかはそれぞれのアルゴリズムによります。

Answer 2

配列の利点

• ランダムアクセスが出来る(i番目の要素を定数時間で出来る)
• メモリ空間の確保・解放が簡単

欠点

• 高速な挿入が出来ない(メモリを拡張して、一旦ずらして、挿入する)
• メモリ空間の拡張・伸縮が難しい(JavaのArrayList、C++のstd::vectorならすでに実装があるので容易)

リスト（構造体を定義する方法）の利点

• 要素数だけメモリを確保すれば良い
• 高速な挿入・削除が実装しやすい

欠点

• 一般に配列より低速（参照の局所性と呼ばれるもの）

スタック・キューは任意箇所の挿入・削除を実装しないので、リストの恩恵を受けにくいとも言えます。
二分木はランダムアクセスが出来ないリストの欠点をカバーしやすいです。

Comments

[maisumakun]

えっと、「配列とリストの比較」ではなく、「リストや二分木を配列で定義してはいけないのか？」という質問だと思いますが。

[mit0223]

むしろ、質問者の方はメモリの解放と再利用にかかるコストに気がついておられないので、構造体へのポインタと配列を使い分ける理由がわからないのではないでしょうか。そういう意味でこの回答がそれほどピント外れとも思えません。

Answer 3

連結リストなら各セルが2つの値（そのセルの値（参照でも可）と次のセルへのポインタ）を持つことになります。二分木は2つの子と、あとそれに加えて中間ノードが何らかの値を持つかもしれません。

データ構造の各要素が複数の値を持つので、構造体で表現するのが自然だと思います。

スタック、キューは（少なくとも初歩的な実装では）データ構造の要素が一つの値しか持たないので、配列で表現するのが自然だと思います。

構造体を使って書けることは、構造体を使わなくても書けます。たとえば連結リストなら、ポインタの配列にして、偶数番号と奇数番号で使い分けるとかやってもいいのかもしれません。でも、それは不自然だと思います。

という話のような気がします。

Answer 4

リスト・二分木だけは、構造体を定義しなければならないのですが、
なぜリスト・二分木だけは構造体を定義しないといけないのですか？　

いえ、リスト・二分木も配列で実装することは可能です。

スタック・キューでは構造体の定義は不要なのに
逆に、リスト・二分木では構造体を定義する必要があるのですか？

スタック・キューは途中の要素を削除する操作がないので、配列を隙間なく使って表現できます。
これに対して、リスト・二分木では、途中の要素を削除するという操作が可能ですので、配列で実装すると、要素を削除したときに配列の途中に空き要素ができます。
このため、この空き要素を管理し、次に要素が追加されたときに再利用する仕組みを自分で実装しなければなりません。また、空き要素がたくさんできたときに、そのメモリを他の用途に利用することができません。

これに対して、リスト・二分木を構造体と libc の malloc+free で実装すると空きメモリの管理を libc に任すことができて、実装が楽です。また、空きメモリは別の用途（ただし、そっちも malloc+freeを使って実装されている場合に限る）に再利用されます。

配列では効率が悪いのですか？

上記のような事情ですので、要素の個別削除が行われることが少ない場合や、メモリを動的に使う必要が少ない場合、配列での実装するほうが効率が高い場合があります。
ただし、教科書でリストや二分木を学ぶ場合はそのような前提はおけないので、構造体と malloc+free で学ぶことになるでしょう。

Comments

[Zuishin]

次に要素が追加されたときに空き要素を再利用というところで少し引っ掛かりました。それは配列 vs 構造体の構図ではなく、配列を使ったメモリ管理というレイヤーの上で構造体を使う、つまり両方使わなければできないことではありませんか？ 構造体を使わないのであれば、その配列とは別に管理領域が必要になると思いますし、そこでやはり構造体を使う必要が出てくると思います。
つまり、malloc の再実装を下敷きにした回答だと思いますが、そこまで低レベルな実装の話は求めていないんじゃないでしょうか。

[mit0223]

Zuishinさん、コメントありがとうございます。質問文では「構造体」VS「配列」となってますが、拡大解釈して「構造体をmalloc で確保してポインタでリンクする方法」VS「配列上に要素をとってその配列の添字でリンクする方法」と解釈しました。たとえば、後者でリストを作るのであれば int values[100]; int next_index[100];のように構造体メンバとなるものごとに配列を作れば、構造体定義は不要ですよね。
質問者の意図に沿ってるかどうかわかりませんが、C言語でプログラミングしている際にスタック・キューとリスト・二分木をを適材適所で使い分けるためには malloc, free にコストがかかることを知っておく必要があると思って、このような回答になりました。ちょっと深読みし過ぎかもしれませんが、teratailなのでそういうのもありかなと思いました。