(79)双方向リスト2019年10月2日リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。シーケンシャルアクセス・ランダムアクセスもう1つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。単純リストから双方向リストへここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。処理であり時間がかかる処理。すればよいのか?この場合、一つ前のデータの場所を覚えているポインタがあれば良い。list)と呼ばれる。簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。要素とするリストを、ナマで記述していた。要素とするデータを挿入せよ。この手のリスト処理のプログラムでは、命令の順序が重要となる。書いていくと間違いが少ない。正しく動くだろうか?こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。list)と呼ばれる。この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。リストとはどのようなデータ構造か図を示しながら説明せよ。双方向リストの利点と欠点はなにか?番兵を用いる利点を説明せよ。