※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃03:リスト
このチャプターでは、リストについて学習します。
配列では、要素を追加・削除する際、整合性を保つためにデータの移動が必要。
要素数が非常に多い場合、非常に多くのデータを移動する必要があり、時間がかかる。
リストを使用することで、要素の追加や削除を効率的におこなうことができる。
リストは、要素をポインタでつなげて格納する。
データとポインタを組み合わせた "ノード" という構造を使用する。
要素の追加や削除をおこなう際にはデータの移動は必要なく、ポインタの変更だけで済む。
一方、リストの要素を参照する際には、ポインタを順番にたどる必要がある。
ポインタが 1 つの方向にしかつながっていないリスト。
最も単純なリストの形態。
末尾のノードに頻繁にアクセスする場合、毎回先頭から順番にポインタをたどっていく必要があり、アクセス速度が遅くなる。
各ノードが前後両方のノードへのポインタを持つリスト。
前後にポインタを持つため、効率的に要素の走査が可能となる。
リストの末尾から先頭に戻るようにポインタがつながっているリスト。
環状リストにも単方向環状リストと双方向環状リストがある。
単にリストといった場合には、上述している線形リストを指すことが多い。
ぐるっと回っているような構造になっているため、先頭や末尾といった概念がない。
どのノードからはじめても同じように走査することができるが、処理をおこなう際には何周も走査しないように注意が必要。
新・アルゴリズムとデータ構造入門 Java編11: 連結リスト
https://paiza.jp/works/algorithm-java/new-primer/algorithm-java-new-primer-11