リストとは（単方向リスト）

データが数珠のように繋がっている集まりをリストと呼びます。見た方が早いので以下の図をまず見てみましょう。

上記のリストでは食べ物のデータを集めたものです。そしてデータはそれぞれポインタと呼ばれる「次のデータの住所」を持っています。上記ではピザデータは1というポインタを持っておりやき肉のデータが次のデータですよということを表しています。最後のからあげのポインタは0で次がありませんよという意味になります。

データの挿入

リストにデータを挿入する時は以下のようになります。

やき肉のポインタを8に変えました。こうすることでやき肉とステーキの間にすしというデータを入れることができました。

データの削除

データを削除する際は以下のようにします。

やきにくのポインタをまた変えましたが今度は一つ後ろのデータを参照するように変えました。こうすると間のデータは削除されます。

単方向リスト

今回見てきたリストは単方向リストというもので後ろにどんどん繋がっていく形になり、最後はポインタが0として終了するものでした。他にも双方向リスト（ポインタが前にもある）や循環リスト（最後のポインタが最初のポインタを参照している）などもあるので興味のある方は調べてみましょう。

メリット

単方向リストは
「要素の挿入や削除が頻繁に行われる場合」
「要素数が動的に変化する場合」
に適しています。

注意点

単方向リストは配列にはない機能があるのでその辺りも押さえておくと理解が深まります。

インデックスは持っていない

通常の配列には固定でインデックス番号が割り振られていますが単方向リストは持っていません。次の要素の情報（ポインタ）を持つのみです。

要素を探すのに一つ一つたどる必要があり時間がかかる

連想配列ではkeyを指定すると１発で目的のデータを取得できたりしますが単方向リストはデータを順番に見ていく必要があります。これはシーケンシャルアクセスと呼ばれます。