連結リスト（Linked List）は、各要素（ノード）が「データ」と「次のノードを指す情報（ポインタ）」を持ち、鎖のようにつながったデータ構造です。
| 操作 | 連結リスト | 配列（配列） |
|---|---|---|
| 途中の挿入・削除 | 速い（つなぎ替えだけ） | 遅い（要素をずらす） |
| 番号でのアクセス | 遅い（先頭からたどる） | 速い |
挿入・削除は、前後のつながり（ポインタ）を付け替えるだけなので高速です。一方、n 番目を取り出すには先頭から順にたどる必要があり遅くなります。次のノードだけを指す単方向、前後を指す双方向などの種類があります。
試験では 連結リスト（挿入・削除が速い／番号アクセスが遅い）と配列（その逆）の対比が頻出です。ポインタでつながる仕組みを押さえましょう。
