データ構造が驚くほど分かる！配列と連結リストの違いを「本棚と宝探し」で徹底解説【初心者向け】

応用情報技術者試験など、情報処理技術者試験の学習を始めると、必ず「データ構造」という壁にぶつかります。特に「配列」と「連結リスト」は、その代表格です。

「ポインタが…」「アドレスが…」という専門用語に、苦手意識を持っている方も多いのではないでしょうか？

この記事では、そんな難しいイメージのあるデータ構造を、プログラミングを始めたばかりの方や、資格試験の概念をしっかり理解したい方のために、身近なもので喩えながら、その「なぜ？」を徹底的に解説します。

この記事を読み終える頃には、配列と連結リストの違いが、まるで物語のようにスッと頭に入っているはずです。

まずは基本の「配列」：「整理整頓された本棚」をイメージしよう

どのようなITシステムを開発する場合でも、最も頻繁にお世話になるデータ構造が「配列」です。
配列を理解するには、巻数順にきれいに並んだ本棚の全集を想像してみてください。

配列におけるデータ

この例では、データはそれぞれの本です。
つまり、1巻、2巻、3巻……と並んだ本がデータだと考えてください。

配列は探すのが得意

配列の特徴は、なんといっても「検索のしやすさ」です。
たとえば、「5巻を読みたい」と思ったら、本棚の5番目の場所に行けばすぐに取れます。これが、配列が「ランダムアクセスが速い」と言われる理由です。

配列は追加・削除が苦手

配列はデータの追加や削除が苦手です。
もし「2巻と3巻の間に、新しい『2.5巻』を差し込みたい」と思ったらどうでしょう？ 3巻以降のすべての本を一度本棚から出し、一つずつズラしてから差し込む必要があります。本が多ければ多いほど、大変な大仕事になります。これが「要素の挿入・削除が遅い」と言われる理由です。

配列は、このようにデータがメモリ上で物理的に隣り合って並んでいるため、場所（インデックス）さえ分かればすぐにアクセスできる反面、途中に何かを加えたり抜いたりする際には、大規模な「引っ越し作業」が必要になるのです。

本日の主役「連結リスト」：「宝探しのメモ」で物語を追いかけよう

一方、試験でよく問われる「連結リスト」は、配列とは全く異なる発想で作られています。
連結リストは、図書館のあちこちに散らばった物語のページを「次のページはこちら」というメモを頼りに読み進める「宝探し」に似ています。

連結リストにおけるデータとポインタ

この例では、データは物語が書かれた1枚1枚のページです。
各ページの最後には、「次のページのありか」を記したメモが残されています。このメモこそが「ポインタ」です。

連結リストはデータの追加・削除が得意

連結リストの長所は、データの追加・削除が得意であることです。
連結リストのデータであるページは、図書館の好きな場所に置けます（つまり、メモリの空いている場所にデータを置けるということです）。

こうしたルールの中で、「2ページ目と3ページ目の間に、新しいページを追加したい」場合はどうでしょう？

その場合、以下の手順でページを追加していきます。

これだけです！
3ページ目以降のページを一切動かす必要がありません。これが「要素の挿入・削除が速い」理由です。

「先頭ポインタ」とは「宝の地図の出発点」のこと

さて、ここで連結リストを学ぶ上で必ず出てくる「先頭ポインタ」というキーワードが登場します。

この「宝探し」を始めるためには、何が絶対に必要でしょうか？
そうです、「最初の1ページ目がどこにあるか」という情報です。

この宝の地図の出発点、つまり「最初の1ページ目のありかだけを記録した特別なメモ」こそが、先頭ポインタです。

先頭ポインタは、物語のページ（データ）そのものではありません。それは、「ここから物語が始まるよ」という場所を指し示しているだけの、非常に重要な住所情報です。

もし、この「出発点のメモ」をなくしてしまったら、たとえ図書館の中に物語の全ページが存在していても、もう二度と物語を読み始めることはできなくなってしまいます。
先頭ポインタは、連結リストという宝探しを始めるための、たった一つの、そして最も重要な手がかりなのです。

連結リストは探すのが苦手

配列と比較すると、連結リストはデータを探すのが苦手です。
たとえば、「5ページ目を読みたい」と思っても、いきなり5ページ目には行けません。
必ず1ページ目からスタートし、「次のページは…」というメモ（ポインタ）を頼りに、順番にたどっていく必要があります。
これが「ランダムアクセスが遅い」理由です。

まとめ：結局、どっちを使えばいいの？

今回は、データ構造の基本である「配列」と「連結リスト」を、身近なもので喩えて解説しました。

	配列（本棚）	連結リスト（宝探し）
データの置き方	隣同士にきれいに並べる	バラバラでOK
繋がり方	物理的な順番	メモ（ポインタ）で繋ぐ
得意なこと	5番目、10番目など、指定した場所のデータをすぐに取ること	途中にデータを追加したり、削除したりすること
苦手なこと	途中にデータを追加・削除すること（全部ズラす必要がある）	指定した場所のデータをすぐに取ること（最初からたどる必要がある）
最初の場所	本棚の「1番目」	先頭ポインタ（出発点のメモ）

Web開発など、現場によっては高機能な配列が用意されているため、連結リストを自ら実装する機会は少ないということもあります。
しかし、その仕組みを理解していることは、システムのパフォーマンスを考える上で非常に重要です。

例えば、データベースがなぜ高速にデータを検索できるのか、その裏側では連結リストの考え方を応用した「B-tree」という技術が活躍しています。

試験で問われるこれらの知識は、単なる暗記ではなく、コンピュータがどのように効率よくデータを扱っているのかを理解するための本質です。この「宝探し」のイメージが、あなたの学習の助けになれば幸いです。