アルゴリズムとデータ構造~リスト(list)~
リストとは
配列が苦手な挿入と削除を効率よく行えるデータ構造。参照が苦手。データが入った箱をポインタでつないだもの。図のように箱の中に要素を入れる場所と、次の箱の場所を示すポインタのセット。一番最後の場所は次の箱へのポインタがないのでNULLを入れる。番地をデータとして扱っているので、ランダムアクセスが不可能。データの個数が更新できるので、柔軟にプログラム設計可能。
様子
以下の図のようにイメージしていただければ大丈夫です。
変数としてよく使うのがlistheadです。これはリストの先頭を指し示すポインタです。この先頭からポインタをたどることにより、参照したいデータにたどり着かなければならないので、リストの数をnとすれば、計算量はO(n)になります。しかし、挿入と削除はかなり簡単です。
挿入はこんな感じですが、先頭に挿入する際には少し工夫が必要です。計算量はO(1)。
削除もO(1)です。消したいものをつながないようにするだけです。
こんな感じです。削除したい箱を飛び越えるように繋ぎ変えればよいのです。こうして飛ばされたデータはのちに開放する必要があります。
