Every Data Structure Simply Explained in 25 Minutes! - - YouTube動画の解説

Every Data Structure Simply Explained in 25 Minutes!

Codist 、Programio

メンバーになる

368,907回視聴 2026/04/18 #DataStructures #SystemDesign #CodingInterview

👉 Try InsForge for free: https://insforge.dev InsForge Github : https://github.com/InsForge/InsForge Learn Every Type of API :    • Every Type of API Simply Explained in 9 Mi...   Learn Every DevOps Software :    • Every DevOps Tools Explained in 8 Minutes!   Learn every essential data structure in one video — from the basics like arrays and linked lists all the way to advanced structures like Tries, Bloom Filters, and LRU Cache. ⏱️ Timestamps 00:00 — Array 02:24 — Linked List 04:32 — Stack 06:08 — Queue 07:39 — Deque 08:50 — Hash Map 10:54 — Hash Set 12:28 — Tree 13:46 — Ad 15:07 — Binary Search Tree 16:49 — Heap 19:04 — Graph 21:15 — Trie 22:54 — Disjoint Set (Union-Find) 24:34 — Bloom Filter 26:38 — LRU Cache #DataStructures #CodingInterview #Programming #SystemDesign

Codist explores essential data structures, from foundational arrays and linked lists to complex heaps and graphs. The explanation breaks down how these tools optimize memory usage, speed up search operations, and manage data flow in modern software development and backend infrastructure.

制作の裏側

オートダビング

いくつかの言語の音声トラックが自動生成されました。 詳細

動画「Every Data Structure Simply Explained in 25 Minutes!（すべてのデータ構造を25分でシンプルに解説！）」の構成（タイムスタンプ）に沿って、エンジニアやコンピューターサイエンス好きが思わずクスッと笑えるような雑学・歴史・開発現場のリアルな裏話を交えながら解説します。

1. 線形データ構造：配列・リスト・スタック・キュー (00:00 - 08:49)

「基本中の基本。しかしメモリ空間の物理的なリアルと常に戦う場所」

• Array（配列）

  • 現場のリアル: メモリ上に連続して並ぶため、CPUキャッシュ効率（Cache Locality）が最強です。そのため、高級言語でどれほどカッコいい抽象データ構造を作っても「結局内部では大きなArrayを1つ確保してぶん回すのが一番速い」という物理法則に行き着くことが多々あります。

• Linked List（連結リスト）

  • 雑学: 1955年にLISP言語の父ジョン・マッカーシーらが開発したIPL（Information Processing Language）で生まれました。ポインタを辿るためメモリ上のあちこちにデータが散らばり、CPUのキャッシュミスが多発するという弱点があります。「教科書では必ず習うけれど、現代の高速なCPU環境では意外と生のLinked Listを直書きする機会が少ない」データ構造の筆頭です。

• Stack / Queue / Deque

  • 開発あるある: Stack（後入れ先出し）といえば、エンジニアがお世話になりまくるサイト「Stack Overflow」の名前の由来です。関数の呼び出し履歴（コールスタック）が無限再帰などでメモリ上限を食い破る現象そのものを指します。一方、Queue（先入れ先出し）は、AWS SQSやRabbitMQなど、現代の分散システムやマイクロサービス間の非同期通信（メッセージキュー）の根幹を支えています。

2. 連想配列・集合：ハッシュマップ・ハッシュセット (08:50 - 12:27)

「$O(1)$ という魔法の代償とセキュリティの戦い」

• Hash Map / Hash Set

  • 歴史と裏話: キーから一瞬で値を引ける $O(1)$ の万能構造ですが、裏側では「ハッシュ衝突（Collision）」との泥臭い戦いがあります。

  • HashDoS攻撃の恐怖: かつて、悪意あるユーザーが「意図的にハッシュ値が同じになるキー」を大量に送りつけ、サーバーのHash Mapを $O(1)$ から $O(n)$ に劣化させてCPU使用率を100%に張り付かせる攻撃（HashDoS）が大流行しました。これを受けて、現代のRust（SipHash採用）やPythonなどは、言語レベルで起動ごとにランダムなシード値を使ってハッシュ化する防御策をとっています。

3. 木構造とヒープ：Tree・BST・Heap (12:28 - 18:59)

「階層構造を効率よく探索・管理する」

• Tree / Binary Search Tree (BST)

  • 雑学: 1960年にソビエト連邦の数学者アデルソン・ベルスキーとランディスが、初の自己平衡二分探索木である「AVL木」を発明しました。冷戦下のソ連で生まれたアルゴリズムが、現代のデータベースやファイルシステムの基礎（B木や赤黒木など）へ繋がっています。

• Heap（ヒープ）

  • 実務での出番: 「常に最大値（または最小値）を $O(1)$ で取り出したい」という優先度付きキュー（Priority Queue）の実装に使われます。身近なところでは、タスクの優先順位付けや、カーナビ・ゲームの経路探索で使われる「A*（エースター）アルゴリズム」のバックエンドで静かに巨大な貢献をしています。

4. ネットワークと関係性：Graph (19:04 - 21:14)

「現実世界のあらゆる関係性を抽象化する」

• Graph（グラフ）

  • 歴史: 1736年、大数学者レオンハルト・オイラーが「ケーニヒスベルクの橋渡し問題（7つの橋を2度通らずに全て渡れるか？）」を解いたことからグラフ理論が始まりました。

  • 現代の巨大応用: Googleの検索エンジンの根幹だった「PageRank」は、ウェブサイト同士のリンク関係を巨大な指向性グラフとして捉えたものです。また、FacebookやLinkedInの「友達の友達」を推薦するソーシャルグラフ、物流の最適化など、GAFAMの巨大サービスの多くがグラフ構造の上に乗っています。

5. 高度・応用データ構造 (21:15 - 28:00)

「システムデザイン・Webインフラの真骨頂」

• Trie（トライ木）

  • ネーミングの雑学: 英語の「Retrieval（検索・回収）」から命名されたため、本来の発音は「トリー」でしたが、「Tree（ツリー）」と混同しやすいため、業界ではあえて「トライ」と呼ぶのが定着しました。Googleの検索窓で文字を打つと出てくる「オートコンプリート（サジェスト機能）」や、スペルチェッカーの爆速化を支えています。

• Disjoint Set / Union-Find（素集合データ構造）

  • 競技プログラミングの相棒: グループの統合と「同じグループに属しているか？」の判定を、ほぼ定数時間（逆アッカーマン関数 $\alpha (n)$）で行える変態的な高速構造です。「ネットワーク内でサーバー同士がつながっているか」「画像認識でピクセル同士が同じ物体か」といった判定に一瞬で答えを出します。

• Bloom Filter（ブルームフィルタ）

  • 確率的データ構造の面白さ: 1970年にバートン・ブルームが考案した「“ない”ことは100%確実だが、“ある”ことは確率的にしかわからない」というユニークなデータ構造です。

  • 業界裏話: メモリ消費量が圧倒的に小さいため、Webブラウザ（Google Chrome）が「このURLは悪意あるサイトのブラックリストに含まれているか？」を判定する際や、NoSQLデータベース（CassandraやRocksDB）が「ディスクにデータを取りに行く前に、そもそも存在するか？」を確認する前処理フィルタとして大活躍しています。

• LRU Cache（Least Recently Used Cache）

  • システム設計面接（System Design）の王様: 「一番最近使われていないものを捨てる」キャッシュ機構です。内部構造としては 「Hash Map + 双方向連結リスト（Doubly Linked List）」 を組み合わせて作られており、参照も削除も $O(1)$ で行うスマートな設計です。WebサーバーやDBのメモリ管理、ブラウザのキャッシュなど、実務のあらゆるレイヤーで使われています。

この動画のハイライト

この動画の素晴らしい点は、単なる概念の説明にとどまらず、「実務やシステム設計（System Design）でどのデータ構造を選択すればメモリと計算コストを最小化できるか」というバックエンドエンジニア視点のロジックが一気通貫で学べる構成になっている点です。

以下は、元の構成をベースに、さらに「クスッと笑える／なるほど」系の雑学・歴史・開発現場のリアルな裏話を追加した解説です。エンジニアやCS好きが「あ、それあるある／知らなかったけど納得」となるポイントを意識しています。

1. 線形データ構造：配列・リスト・スタック・キュー

Array（配列）の続き キャッシュ効率の話は本当に重要で、現代のCPUは「メモリを連続で読めるか」で性能が激変します。実際、C++のstd::vectorやJavaのArrayListが内部で巨大な配列を確保して再配置を繰り返すのは、この物理法則に忠実だから。逆に「抽象化が美しいからLinked Listを多用する」と、キャッシュミスの嵐でベンチマークが悲惨な結果になることがよくあります。現場では「まず配列で書いて、本当に必要になったら他の構造に変える」が鉄則です。

Linked List（連結リスト）の続き 1955〜56年頃にLISPの原型であるIPLで生まれたというのは正しいですが、現代で生のLinked Listを直書きする機会が少ない理由はもう一つあります。ガベージコレクション付きの言語では、ポインタを辿るコストに加えて「オブジェクトヘッダのオーバーヘッド」が地味に効いてくるからです。結果として「教科書では必須、実務ではほぼstd::listやLinkedListを避けてvector/ArrayListを使う」という逆転現象が起きています。ただし、OSのカーネルや組み込み、特定のロックフリー構造では今でも現役です。

Stack / Queue / Dequeの続き 「Stack Overflow」の由来はご存知の通りですが、実は「Queue Overflow」という言葉はあまり使われません。なぜならキューは基本的に「溢れたら待たせる／捨てる」設計が多く、スタックのように「呼び出し履歴が爆発してプロセスが死ぬ」劇的な事故が起きにくいからです。一方でDeque（両端キュー）は、Pythonのcollections.dequeやC++のstd::dequeで「先頭と末尾の両方にO(1)で出し入れできる」便利屋として重宝されます。特にスライディングウィンドウ系の問題や、タスクの優先度調整で「後ろから入れて前から出す」みたいな使い方が現場でよく出ます。

2. 連想配列・集合：ハッシュマップ・ハッシュセット

Hash Map / Hash Setの続き HashDoS攻撃は2011年前後に本格的に問題化し、特にPHPやRuby、古いPythonの実装が狙われました。攻撃者は「同じハッシュ値になる文字列を大量に生成する」ツールを使い、サーバーをO(n²)の地獄に落とします。これを受けて、現代の言語は「起動時にランダムなシードを入れる」「SipHashのような暗号学的に強いハッシュをデフォルトにする」などの対策を取りました。RustがSipHashを採用したのもこの流れです。

もう一つ面白いのは「ロードファクター（Load Factor）」の話。ハッシュテーブルは通常、要素数が容量の70%前後を超えたらリサイズしますが、この「70%」という数字は「衝突が増えすぎて遅くならないギリギリのライン」として経験的に選ばれたものです。あまり高くすると衝突だらけ、低くするとメモリ浪費、というトレードオフがずっと続いています。

3. 木構造とヒープ：Tree・BST・Heap

Tree / Binary Search Tree (BST)の続き AVL木は1962年にソ連のAdelson-VelskyとLandisによって発表されました（1960年頃の研究が基）。冷戦下のソ連で生まれた自己平衡木が、後に赤黒木（1970年代）やB木（1970年、BoeingのBayerとMcCreight）へと発展し、現代のデータベースやファイルシステムの基盤になったのは皮肉でもあり面白い話です。実務では「素のBSTは偏ると線形探索並みに遅くなる」ので、ほぼ必ず平衡化バージョンを使います。

Heap（ヒープ）の続き 優先度付きキューの実装としてヒープが使われるのは常識ですが、実は「二項ヒープ」や「フィボナッチヒープ」といったバリエーションもあります。フィボナッチヒープは理論上償却計算量が優秀ですが、定数項が大きくて実務ではほぼ使われません。「理論上最速でも実装が複雑で遅い」典型例です。一方、ゲームや経路探索のA*では、シンプルな二分ヒープが今でも現役で、大量のノードを高速に処理しています。

4. ネットワークと関係性：Graph

Graph（グラフ）の続き オイラーの「ケーニヒスベルクの橋」は1736年の話で、これがグラフ理論の起源とされています。現代ではPageRankが有名ですが、実はPageRankの計算自体が「巨大な疎行列の固有ベクトルを求める」という線形代数の問題に帰着します。Google初期はこの計算を分散して回すためにMapReduceを発明した、というのも有名なエピソードです。

また、ソーシャルグラフでは「六次の隔たり」（どんな人も平均6人を介せば繋がる）という現象が有名で、これがFacebookやLinkedInの「友達の友達」推薦の理論的背景の一つになっています。実務では「グラフが巨大すぎてメモリに乗らない」問題が常につきまとい、隣接リストやCSR形式などの省メモリ表現が工夫されています。

5. 高度・応用データ構造

Trie（トライ木）の続き 発音が「トリー」から「トライ」に変わったのは本当で、混同を避けるための業界慣習です。オートコンプリート以外にも、IPルーティング（最長プレフィックスマッチ）や、辞書の高速検索、さらには「文字列の集合をコンパクトに保持する」用途で使われます。ただし、メモリ消費が激しいので、現代では「Radix Tree」や「Patricia Trie」といった圧縮版がよく使われます。

Disjoint Set / Union-Findの続き 「ほぼ定数時間（逆アッカーマン関数）」というのは正確で、アッカーマン関数が異常に速く増加するため、実用上は「定数とみなしていい」レベルです。競技プログラミングでは「経路圧縮＋ランクによる統合」の2大最適化を入れないとTLE（Time Limit Exceeded）になる定番です。画像処理の連結成分ラベリングや、ネットワークの連結性チェックで今でも現役です。

Bloom Filter（ブルームフィルタ）の続き 「ないことは100%確実、あることは確率的」という性質が面白いところです。偽陽性（ないのに「ある」と判定）は許すが、偽陰性（あるのに「ない」と判定）は絶対に許さない、という設計思想が、ChromeのセーフブラウジングやCassandraのSSTable存在チェックにぴったりハマっています。パラメータ（ハッシュ関数の数やビット配列のサイズ）を調整することで、偽陽性率を好きなだけ下げられるのも魅力です。

LRU Cacheの続き システム設計面接で「LRU Cacheを設計せよ」は定番中の定番です。Hash Map + 双方向連結リストの組み合わせは「O(1)で参照・更新・削除」を実現する美しい設計で、実際にRedisやMemcached、各種DBのバッファプールでも似た思想が使われています。ちなみに「LFU（Least Frequently Used）」や「ARC（Adaptive Replacement Cache）」など、より賢い置換アルゴリズムも存在しますが、実装のシンプルさと性能のバランスでLRUが今でも王者です。

全体を通じた「データ構造あるある」追加

• 「教科書と実務のギャップ」: 教科書ではLinked Listや素のBSTが詳しく出てきますが、実務では「配列とハッシュと木（平衡化済み）でほとんど事足りる」というのが本音です。特にキャッシュ効率を意識すると、ポインタを多用する構造は避けられがちです。
• 「定数時間が本当に定数か問題」: Union-Findの逆アッカーマンや、ハッシュの平均O(1)など、「理論上は定数でも最悪ケースや定数項が大きい」ものが結構あります。ベンチマークを取ると「あれ？」となることがよくあります。
• 「名前の由来が意外と適当」: Trieの発音変更や、Bloom Filterの「ないことは確実」という逆説的な性質など、命名や設計思想に人間味を感じるものが少なくありません。

この動画の良いところは、単なる定義の羅列ではなく、「どのデータ構造を選ぶとメモリと計算コストがどう変わるか」というシステム設計的な視点が一貫している点です。実務でも「この操作がボトルネックなら、この構造に変える」という引き出しを持っておくと、設計が一段上手くなります。