アルゴリズムは問題を解決するための手順や方法論（料理のレシピ）、データ構造はデータを効率的に整理・格納する形式（食材の保管方法）を指し、これらはプログラミングの基礎であり、適切な組み合わせでプログラムの性能（速度や効率）を大幅に向上させるために不可欠です。データ構造（配列、リスト、木など）は「何を（データ）」、アルゴリズム（探索、ソートなど）は「どうする（手順）」を決め、両者は密接に連携し、効率的なソフトウェア開発と問題解決の鍵となります。
画像参照：https://mo-gu-mo-gu.com/about-datastructure-algorithm/
リスト（線形リスト）
線形リストとは、データを「ノード（節）」と呼ばれる箱に入れ、その箱が「ポインタ（参照情報）」で数珠つなぎに連結されたデータ構造で、配列と違いメモリ上で連続している必要がなく、要素の挿入・削除が容易なのが特徴です。各ノードはデータ本体と「次のノード」へのポインタを持ち、先頭からたどっていくことで順にデータにアクセスします。
特徴と仕組み
- ノード（セル）:データを格納する部分と、次のノードを指し示すポインタ（アドレス情報）を持つ構造体のようなものです。
- ポインタ（リンク）:次の要素のメモリ上の位置（アドレス）を指し示し、要素同士を繋ぎます。
- ヘッド（先頭ポインタ）:リストの開始点（最初のノード）を指すポインタです。
- NULL（終端）:リストの最後のノードのポインタは、何も指さない特別な値（NULL）になります。
- 線形（直線的）:要素が一直線に連なっている状態を指します。
種類
画像参照：https://algo-logic.info/linked-list/
- 単方向リスト（片方向リスト）:「次」の要素へのポインタのみを持ち、先頭から末尾へ一方向にしかたどれません。
- 双方向リスト:「次」と「前」の両方の要素へのポインタを持ち、双方向にたどれます。
- 循環リスト:末尾のノードが先頭のノードを指し、円環状に連結されています。先頭や末尾が存在しないとも言えます。
配列との違いとメリット・デメリット
- 配列:メモリ上に連続して配置され、ランダムアクセス（任意の位置へのアクセス）は速いですが、途中に要素を挿入・削除する際に大量のデータ移動（コピー）が必要になります。
- 線形リスト:メモリは連続でなくてもよく、ポインタの付け替えだけで要素の挿入・削除ができるため、動的なデータ管理（頻繁な追加・削除）に向いています。しかし、特定の要素を見つけるための検索（探索）は先頭から順にたどる必要があるため、配列より遅くなることがあります。
主な用途
- スタックやキューといった基本的なデータ構造の実装。
- ファイルのディレクトリ構造（フォルダ内のファイル一覧など）。
- データの順序を保持しつつ、動的な追加・削除が頻繁に発生する場面。
スタック
スタックは、データを「後入れ先出し（LIFO）」のルールで出し入れするデータ構造で、積み重ねた皿や本のように最後に入れたものが最初に取り出されるのが特徴です。データを「プッシュ（PUSH）」で追加し、「ポップ（POP）」で一番上（最後に入れたもの）から取り出し、「戻るボタン」や「関数呼び出しの管理」などに使われます。
特徴と操作
- LIFO : 後から入れたデータが先に出てくる方式。
- プッシュ（PUSH） : スタックの「一番上（トップ）」にデータを追加する操作。
- ポップ（POP）: スタックの「一番上（トップ）」からデータを一つ取り出す操作。
身近な例え
- 積み重ねた皿: 一番上から取り出す。
- エレベーター: 後に乗った人が先に降りる。
- Webブラウザの戻るボタン: 直前のページ（最後に追加された履歴）に戻る。
応用例
- 関数呼び出し（コールスタック）: 関数が呼び出された順序で処理（一時データの退避や戻りアドレスの管理）を行う。
- テキストエディタの「元に戻す」機能: 変更履歴をスタックに積んで、逆順に解除する。
- 数式の逆ポーランド記法の評価。
キュー
キューは、先入れ先出し（FIFO）の原則に基づいてデータを管理する、基本的なデータ構造です。人が窓口で並ぶ待ち行列のように、最初に入れたデータが最初に取り出され、新しいデータは必ず末尾に追加され、取り出しは常に先頭から行われます。プログラミングでは、タスクの処理待ち（プリンタ、CPUなど）やメッセージの管理などに利用されます。
キューの基本動作
- エンキュー : キューの末尾（後ろ）にデータを追加します。
- デキュー : キューの先頭（前）からデータを取り出します。
特徴と例
- FIFO : 先に入ったものが先に出るという原則。
- 待ち行列: スーパーのレジ、銀行の窓口、電話の問い合わせ窓口などが例えられます。
- コンピュータでの利用:
- 印刷ジョブの管理: 印刷要求を順番に処理。
- タスクスケジューリング: CPUが処理するタスクの待ち行列。
- イベント処理: ウィンドウシステムでのメッセージ処理。
実装方法
- 配列: メモリ効率が良い反面、操作（特に削除時）でデータ移動が必要になり、効率が悪い場合があります。
- 連結リスト: データ量の変動に柔軟に対応でき、メモリ効率が高いですが、ポインタ操作で設計が複雑になることがあります
コメント