前回、③に戻り、学習４週目を振り返りました。今回は、もう一つの代表的なデータ構造「連結リスト」を整理します。
連結リストとは
連結リストは、複数のデータを、それぞれ「次のデータの場所」を指し示す形でつなげていくデータ構造です。以前整理した配列とは違い、データが必ずしもメモリ上に連続して並んでいるとは限りません。
連結リストの各要素は「ノード」と呼ばれ、ノードには「データそのもの」と「次のノードの場所を示す情報(ポインタ)」の２つが含まれています。
配列との違い
配列は、要素が順番に並んでいるため、添字を指定すればすぐに目的の値にアクセスできます。一方、連結リストは、先頭のノードから、ポインタをたどって順番に進んでいかないと、目的のデータにたどり着けません。
その代わり、連結リストには、途中にデータを追加したり、途中のデータを削除したりする作業を、配列よりも少ない手間で行えるという利点があります。配列の場合、途中に要素を追加すると、後ろの要素をすべてずらす必要がありますが、連結リストでは、ポインタのつなぎ替えだけで済みます。
ノードの追加・削除のイメージ
連結リストへのノードの追加は、次のような手順になります。
- 新しいノードを用意する
- 追加したい位置の前のノードが指しているポインタを、新しいノードに向ける
- 新しいノードのポインタを、もともとつながっていた次のノードに向ける
削除の場合は、削除したいノードを指していたポインタを、削除したいノードの次のノードに向け直すことで、間のノードを飛ばして、つながりを作り直します。
トレースするときの注意点
連結リストのトレース問題では、「今、どのノードが、どのノードを指しているか」を、矢印を使って書き出しながら追うようにしています。
配列のように添字だけで管理できないぶん、頭の中だけで追おうとすると、途中でどのノードの話をしているのか分からなくなりやすいと感じました。ノードを丸で描き、矢印でつなぎながら、ポインタの向きが変わるたびに書き直す練習が、いちばん効果的でした。
学習してみた感想
連結リストは、これまでの配列の感覚のままイメージしようとすると、うまく理解できませんでした。「データが連続して並んでいるとは限らない」という前提を受け入れ、矢印でつながりを描くことを徹底したことで、少しずつ動作が見えるようになってきました。
次回は、科目Bのデータ構造の続きとして、二分木・木構造の探索方法を整理します。
