サーチのアルゴリズムを学ぶ

性能

　このプログラムの性能については、線形探索と同じことはわかるでしょう。データの個数が増えれば増えただけ探索時間も増えます。

　そこで高速化のために、データをソートしておいて二分探索はできないでしょうか？

　残念ながら、この構造では二分探索ができません。おわかりと思いますが、探索する区間を半分に分けるなどということができません。各要素のアクセスするためにはリンクを順にたどるしかないのです。

　そこで、リンクによるリスト構造でありながら、二分探索と同じ性能が出るものを考えますが、それは次回に譲って、その前に要素を削除することを考えましょう。

要素の削除

　図3-1を見てください。この状態で「C」の要素を削除することを考えます。削除した後は図3-2のようになるでしょう。

　ここでちょっと気をつけなければいけないことがあります。「C」を切り離す際に必要なことは、「C」の要素の内容（next）を書き換えることではなくて、ひとつ前の要素のnextを書き換えることです。図3-2では要素「A」のnextを書き換えることになります。

　さらにややこしいことに、もし「A」の要素を切り離すとしたらどうなるでしょう？

　その場合は図3-3のanchorの値を書き換えることになります。

　リンクトリストを扱う際、要素を切り離すのが一番ややこしいところです。この切り離しのための関数delete()は図3-4のようになるでしょう。

　このプログラムでは、切り離す要素がアンカーから直接つながっている場合と、そうでない場合とを区別しています。PHPでは、関数への引数を参照渡し（call by reference）で渡す場合のほかは、ポインタという概念が明確ではありません。それでこのように場合分けをしましたが、この部分は図3-5のように書くこともできます。

　図3-6のようにCで書いた例を見ればその意味がはっきりするでしょう。

　これでリンクトリストの追加と削除ができるようになりました。もちろん、探索もできます。

　ポインタの扱いはややこしいと思いましたか？でも、このように絵を見れば、どこを操作すればよいかわかったと思いますが、いかがでしたでしょうか？

　リンクトリストはデータの伸び縮みに対応できます。ただ、検索速度が遅いのが難点です。そこで次回は、リンクトリストとおなじようなポインタによってつながっている構造であっても、二分探索と同様のスピードが出る構造を考えてみましょう。

　なお、本稿の執筆にあたって、以下を参考にしました。

Robert Sedgewick『Algorithms』Addison-Wesley（発行年：1983）