データ構造vol.2 リストの解説【動画＃20】

＜データ構造とは２　リストの解説＞

1. リストとは

データの削除や挿入に特化されて作られた構造

＜整理すると＞
配列　：データの削除や挿入の効率よりもアクセスの効率を重視
リスト：アクセスの効率よりもデータの削除や挿入の効率を重視

※リストの構造でアクセスする場合
任意のデータまで全てなめる必要がある。

2. リストの特徴

他の要素の格納場所を指し示すポインタと
データを組み合わせて格納している。

ポインタをたどっていくと全要素にたどり着くことができる。
最後のポインタをnullとすることで終わりを示すことができる。

3. リスト構造の削除の方法

　課題：35を削除

＜解説＞

① 35を削除すると同時にポインタも削除される
② １のデータとポインタのセットを次の要素として指し示す

4. リスト構造の挿入の方法

　課題：24と35の間に14を挿入

＜解説＞

① 24から14へのポインタが指し示される。
② 次に35のポインタとなる。

5. リストのデメリット・メリット

デメリット：
① アクセスする場合、全ての要素をなめる必要がある
②配列と比較してポインタを持つのでメモリ効率が悪い

メリット：
① 削除や挿入がポインタの付け替えによって可能とするため、計算時間が速い

6. 補足（両方向リスト）

双方向のポインタを持つ構造

用途によっては、
次だけでなく以前のポインタも記憶しておくと非常に役立つ場合がある

＜今回の総まとめ＞
リストの特徴と、配列との違いを捉えて、用途ごとに使い分けられるようにしよう。

次回、データ構造とは３　スタック/キューについて、簡単に整理する。