Zenn
👌

【保存版】データ構造の基本：各データ構造の特徴と用途を徹底解説

2024/05/28に公開
データ構造
アルゴリズム
コード
コーディング
tech

はじめに

データ構造について学び始めています。今回はデータ構造の基本的なものについて解説します。

配列（Array）

配列は、最も基本的なデータ構造の一つです。要素を連続してメモリ上に配置します。固定サイズで、要素へのアクセスが速いのが特徴です。

  • 得意なこと
    • 列の何番目の要素であるかを指定するとO(1)の計算時間で即座にその要素を取り出すことができる。
  • 苦手なこと
    • 途中の要素へ挿入や削除を行う場合、後ろ全てをずらす必要がある。
    • 固定長なのでサイズの変更ができない。

リスト（List）

リストは、動的に要素を追加・削除できるデータ構造です。配列とは異なり、要素数を事前に決める必要がありません。それぞれの要素がノードとして扱われ、それぞれが次の要素へのポインタを持っています。

  • 得意なこと
    • 要素の挿入・削除がポインタを付け替えるだけで良いので速い。O(1)で操作可能。
  • 苦手なこと
    • 任意の位置へのアクセスが前から順に要素をたどらなければならないため遅い。O(n)の計算時間が必要。

スタック

スタックは「LIFO（Last In, First Out）」の原則に基づいたデータ構造です。後から入れたデータが先に出てくる、つまり後入れ先出しです。例えるなら、積み上げたお皿を取るイメージ・エレベーターのイメージです。

使用場面

  • 関数の呼び出し管理：プログラムが関数を呼び出すたびにスタックに情報を積み、関数が終了するたびにスタックから情報を取り出します。
  • 戻り先を保持する：例えば、ブラウザの「戻る」ボタンの履歴管理もスタックで実現されています。

スタックの使い方

スタックの基本操作は「プッシュ（push）」と「ポップ（pop）」です。

  • プッシュ：データをスタックに積む操作
  • ポップ：データをスタックから取り出す操作
// C#でのスタックの例
using System;
using System.Collections.Generic;

public class StackExample
{
    public static void Main()
    {
        Stack<string> stack = new Stack<string>();
        stack.Push("A");  // プッシュ
        stack.Push("B");  // プッシュ
        Console.WriteLine(stack.Pop());  // ポップ: 出力 'B'
        Console.WriteLine(stack.Pop());  // ポップ: 出力 'A'
    }
}

キュー

キューは「FIFO（First In, First Out）」の原則に基づいたデータ構造です。先に入れたデータが先に出てくる、つまり先入れ先出しです。例えるなら、列に並んで順番を待つイメージ・レジのイメージです。

使用場面

  • プリントキュー：プリンターがドキュメントを印刷する順序を管理します。
  • タスクスケジューリング：コンピュータのプロセス管理やジョブスケジューリングで使用されます。

キューの使い方

キューの基本操作は「エンキュー（enqueue）」と「デキュー（dequeue）」です。

  • エンキュー：データをキューに追加する操作
  • デキュー：データをキューから取り出す操作
// C#でのキューの例
using System;
using System.Collections.Generic;

public class QueueExample
{
    public static void Main()
    {
        Queue<string> queue = new Queue<string>();
        queue.Enqueue("A");  // エンキュー
        queue.Enqueue("B");  // エンキュー
        Console.WriteLine(queue.Dequeue());  // デキュー: 出力 'A'
        Console.WriteLine(queue.Dequeue());  // デキュー: 出力 'B'
    }
}

木

木は、データベースやファイルシステムでよく使われる木構造です。ノードが複数の子を持つことができます。根幹となる部分は根と呼び、その根に子ノードがぶら下がる形になっている。子を持たない末端のノードは葉と呼ばれます。

// C#での木の例
using System;
public class Node
{
    Ofject data;
    List children;
}

グラフ

グラフは、頂点とそれらを結ぶエッジで構成されるデータ構造です。ネットワークや関係性の表現に使われます。

得意なこと
複雑な関係性のモデル化。様々なアルゴリズムが使用可能。
苦手なこと
実装と操作が複雑になることが多い。

参考書籍

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/4bniLp4

Discussion