ビデオと演習で説明される10の一般的なデータ構造

「悪いプログラマーはコードを心配しています。優れたプログラマーは、データ構造とその関係を心配しています。」— Linuxの作成者、Linus Torvalds
**更新**アルゴリズムに関する私のビデオコースが公開されました! Manning Publicationsの「動いているアルゴリズム」をご覧ください。 「39carnes」というコードを使用して、コースを39%オフにしてください!または、「vlcarnes2」というコードを使用して、Deep Learning in Motionコースの50%を割引できます。

データ構造はソフトウェア開発の重要な部分であり、開発者の就職面接に関する質問の最も一般的なトピックの1つです。

幸いなことに、これらは基本的にデータの整理と保存のための特別な形式にすぎません。

この短い記事では、最も一般的な10のデータ構造について説明します。

これらのデータ構造ごとに作成したビデオを埋め込みました。また、それぞれのコード例にリンクしており、JavaScriptでこれらを実装する方法を示しています。

また、練習のために、freeCodeCampカリキュラムの課題にリンクしました。

これらのデータ構造には、Big O表記の時間の複雑さが含まれていることに注意してください。時間の複雑さは実装方法に基づいている場合があるため、これはすべてのユーザーに含まれているわけではありません。 Big O Notationについて詳しく知りたい場合は、それについての私の記事またはBriana Marieによるこのビデオをご覧ください。

また、JavaScriptでこれらのデータ構造を実装する方法を示していますが、Cのような低レベル言語を使用していない限り、ほとんどの場合、自分で実装する必要はありません。

JavaScript(ほとんどの高級言語と同様)には、これらのデータ構造の多くの組み込み実装があります。

それでも、これらのデータ構造を実装する方法を知っていると、開発者の求人検索で大きな優位性が得られます。また、高性能なコードを作成しようとする場合に役立ちます。

リンクリスト

リンクリストは、最も基本的なデータ構造の1つです。他の多くのデータ構造が配列またはリンクリストのいずれかで実装できるため、多くの場合、配列と比較されます。それぞれに長所と短所があります。

リンクリスト表現

リンクリストは、シーケンスを一緒に表すノードのグループで構成されます。各ノードには、格納される実際のデータ(基本的に任意のタイプのデータ)と、シーケンス内の次のノードへのポインター(またはリンク)の2つが含まれます。また、各ノードにリスト内の次のアイテムと前のアイテムの両方へのポインターがある二重リンクリストもあります。

リンクリストの最も基本的な操作は、リストへのアイテムの追加、リストからのアイテムの削除、およびアイテムのリストの検索です。

JavaScriptのリンクリストのコードはこちらをご覧ください。

リンクリストの時間の複雑さ
╔===========╦=========╦===========╗
║アルゴリズム║平均║最悪の場合║
╠===========╬=========╬===========╣
║スペース║O(n)║O(n)║
║検索║O(n)║O(n)║
║挿入║O(1)║O(1)║
║削除║O(1)║O(1)║
╚===========╩=========╩===========╝

freeCodeCampの課題

  • リンクリスト内のノードを操作する
  • リンクリストクラスを作成する
  • リンクリストから要素を削除する
  • リンクリスト内を検索する
  • インデックスによるリンクリストからの要素の削除
  • リンクリストの特定のインデックスに要素を追加する
  • 二重リンクリストを作成する
  • 二重リンクリストを逆にする

スタック

スタックは、スタックの最上部にあるアイテムのみを挿入または削除できる基本的なデータ構造です。書籍の山に似ています。スタックの真ん中にある本を見たい場合は、最初にその上の本をすべて取り去らなければなりません。

スタックはLIFO(Last In First Out)と見なされます。つまり、スタックに最後に入れたアイテムは、スタックから出てくる最初のアイテムです

スタック表現

スタックで実行できる主な操作は3つあります:アイテムをスタックに挿入する(「プッシュ」と呼ばれる)、スタックからアイテムを削除する(「ポップ」と呼ばれる)、スタックの内容を表示する(「ピップ」と呼ばれることもあります) ')。

JavaScriptのスタックのコードはこちらをご覧ください。

スタック時間の複雑さ
╔===========╦=========╦===========╗
║アルゴリズム║平均║最悪の場合║
╠===========╬=========╬===========╣
║スペース║O(n)║O(n)║
║検索║O(n)║O(n)║
║挿入║O(1)║O(1)║
║削除║O(1)║O(1)║
╚===========╩=========╩===========╝

freeCodeCampの課題

  • スタックの仕組みを学ぶ
  • スタッククラスを作成する

キュー

キューは食料品店の人々の列と考えることができます。行の最初のものが最初に提供されます。キューのように。

キュー表現

キューは、データへのアクセス方法を示すためにFIFO(先入れ先出し)と見なされます。これは、新しい要素が追加されたら、新しい要素を削除する前に、以前に追加されたすべての要素を削除する必要があることを意味します。

キューには、エンキューとデキューの2つの主要な操作のみがあります。エンキューはアイテムをキューの後ろに挿入することを意味し、デキューは前のアイテムを削除することを意味します。

JavaScriptのキューのコードはこちらをご覧ください。

キュー時間の複雑さ
╔===========╦=========╦===========╗
║アルゴリズム║平均║最悪の場合║
╠===========╬=========╬===========╣
║スペース║O(n)║O(n)║
║検索║O(n)║O(n)║
║挿入║O(1)║O(1)║
║削除║O(1)║O(1)║
╚===========╩=========╩===========╝

freeCodeCampの課題

  • キュークラスを作成する
  • 優先度キュークラスを作成する
  • 循環キューを作成する

セット

表現を設定する

設定されたデータ構造は、特定の順序や値の繰り返しなしで値を保存します。セットに要素を追加および削除できることに加えて、同時に2つのセットで機能するいくつかの他の重要なセット関数があります。

  • Union — 2つの異なるセットのすべてのアイテムを結合し、これを新しいセット(重複なし)として返します。
  • Intersection — 2つのセットが与えられると、この関数は両方のセットの一部であるすべてのアイテムを持つ別のセットを返します。
  • 差—これは、1つのセットにあるが異なるセットにはないアイテムのリストを返します。
  • サブセット—これは、あるセットのすべての要素が別のセットに含まれているかどうかを示すブール値を返します。

ここでJavaScriptでセットを実装するコードを表示します。

freeCodeCampの課題

  • セットクラスを作成する
  • セットから削除する
  • セットのサイズ
  • 2つのセットでユニオンを実行する
  • 2つのデータセットで交差を実行する
  • 2つのデータセットで違いを実行する
  • 2つのデータセットでサブセットチェックを実行する
  • ES6でセットを作成して追加する
  • ES6のセットからアイテムを削除する
  • ES6セットで.hasおよび.sizeを使用する
  • ES5 Set()統合にスプレッドとノートを使用する

地図

マップは、すべてのキーが一意であるキー/値のペアでデータを保存するデータ構造です。マップは、連想配列または辞書と呼ばれることもあります。多くの場合、データの高速検索に使用されます。マップでは次のことができます。

地図表現
  • コレクションへのペアの追加
  • コレクションからのペアの削除
  • 既存のペアの変更
  • 特定のキーに関連付けられた値の検索

ここでJavaScriptでマップを実装するコードを表示します。

freeCodeCampの課題

  • 地図データ構造を作成する
  • ES6 JavaScriptマップを作成する

ハッシュテーブル

ハッシュテーブルとハッシュ関数の表現

ハッシュテーブルは、キーと値のペアを含むマップデータ構造です。ハッシュ関数を使用して、バケットまたはスロットの配列へのインデックスを計算し、そこから目的の値を見つけることができます。

ハッシュ関数は通常、文字列を入力として受け取り、数値を出力します。ハッシュ関数は、同じ入力に対して常に同じ出力番号を与える必要があります。 2つの入力が同じ数値出力にハッシュするとき、これは衝突と呼ばれます。目標は衝突を少なくすることです。

そのため、キー/値のペアをハッシュテーブルに入力すると、キーはハッシュ関数を介して実行され、数値に変換されます。この数値は、値が保存される実際のキーとして使用されます。同じキーに再度アクセスしようとすると、ハッシュ関数がキーを処理し、同じ数値結果を返します。番号は、関連する値を検索するために使用されます。これにより、平均して非常に効率的なO(1)ルックアップ時間が提供されます。

ここでハッシュテーブルのコードを表示します。

ハッシュテーブルの時間の複雑さ
╔===========╦=========╦===========╗
║アルゴリズム║平均║最悪の場合║
╠===========╬=========╬===========╣
║スペース║O(n)║O(n)║
║検索║O(1)║O(n)║
║挿入║O(1)║O(n)║
║削除║O(1)║O(n)║
╚===========╩=========╩===========╝

freeCodeCampの課題

  • ハッシュテーブルを作成する

バイナリ検索ツリー

バイナリ検索ツリー

ツリーは、ノードで構成されるデータ構造であり、次の特性があります。

  1. 各ツリーには(最上部に)ルートノードがあります。
  2. ルートノードには0個以上の子ノードがあります。
  3. 各子ノードには、0個以上の子ノードがあります。

バイナリ検索ツリーは、次の2つの特性を追加します。

  1. 各ノードには最大2つの子があります。
  2. 各ノードについて、その左の子孫は現在のノードよりも小さく、右の子孫よりも小さいです。

バイナリ検索ツリーにより、アイテムの高速な検索、追加、削除が可能になります。それらの設定方法は、平均して、各比較でツリーの約半分をスキップできるため、各ルックアップ、挿入、または削除には、ツリーに格納されているアイテムの数の対数に比例した時間がかかることを意味します。

JavaScriptのバイナリ検索ツリーのコードはこちらからご覧ください。

バイナリ検索時間の複雑さ
╔===========╦======================╗
║アルゴリズム║平均║最悪の場合║
╠===========╬======================╣
║スペース║O(n)║O(n)║
║検索║O(log n)║O(n)║
║挿入║O(log n)║O(n)║
║削除║O(log n)║O(n)║
╚===========╩======================╝

freeCodeCampの課題

  • バイナリ検索ツリーで最小値と最大値を見つける
  • バイナリ検索ツリーに新しい要素を追加する
  • バイナリ検索ツリーに要素が存在するかどうかを確認します
  • バイナリ検索ツリーの最小および最大の高さを見つける
  • バイナリ検索ツリーで深さ優先検索を使用する
  • バイナリ検索ツリーで幅優先検索を使用する
  • バイナリ検索ツリーでリーフノードを削除する
  • バイナリ検索ツリーで1つの子を持つノードを削除する
  • バイナリ検索ツリーで2つの子を持つノードを削除する
  • バイナリツリーを反転する

トライ

トライ(「トライ」と発音)またはプレフィックスツリーは、一種の検索ツリーです。トライは、各ステップがトライのノードであるステップにデータを保存します。試行は、単語の自動補完機能など、迅速な検索のために単語を保存するためによく使用されます。

トライ表現

言語トライの各ノードには、単語の1文字が含まれています。トライの枝をたどって、一度に1文字ずつ単語を綴ります。文字の順序がトライの他の単語と異なる場合、または単語が終了する場合、ステップは分岐し始めます。各ノードには、文字(データ)と、ノードが単語の最後のノードであるかどうかを示すブール値が含まれています。

画像を見て、言葉を形作ることができます。常に最上部のルートノードから開始し、下に向かって作業します。ここに示されているトライには、ボール、コウモリ、人形、do、dork、dorm、send、senseという単語が含まれています。

ここでJavaScriptのトライのコードを表示します。

freeCodeCampの課題

  • トライ検索ツリーを作成する

バイナリヒープ

バイナリヒープは、ツリーデータ構造の別のタイプです。すべてのノードには、最大で2つの子があります。また、完全なツリーです。これは、最後のレベルまですべてのレベルが完全に満たされ、最後のレベルが左から右に満たされることを意味します。

最小および最大ヒープ表現

バイナリヒープは、最小ヒープまたは最大ヒープのいずれかです。最大ヒープでは、親ノードのキーは常に子のキー以上です。最小ヒープでは、親ノードのキーは子のキー以下です。

レベル間の順序は重要ですが、同じレベルのノードの順序は重要ではありません。この画像では、最小ヒープの3番目のレベルの値が10、6、および12であることがわかります。これらの数値は順序が正しくありません。

ここでJavaScriptのヒープのコードを表示します。

バイナリヒープ時間の複雑さ
╔===========╦======================╗
║アルゴリズム║平均║最悪の場合║
╠===========╬======================╣
║スペース║O(n)║O(n)║
║検索║O(n)║O(n)║
║挿入║O(1)║O(log n)║
║削除║O(log n)║O(log n)║
║ピーク║O(1)║O(1)║
╚===========╩======================╝

freeCodeCampの課題

  • 最大ヒープに要素を挿入する
  • 最大ヒープから要素を削除する
  • 最小ヒープでヒープソートを実装する

グラフ

グラフは、ノード(頂点とも呼ばれる)とそれらの間の接続(エッジと呼ばれる)のコレクションです。グラフはネットワークとも呼ばれます。

グラフの一例は、ソーシャルネットワークです。ノードは人であり、エッジは友情です。

グラフには、有向グラフと無向グラフの2つの主要なタイプがあります。無向グラフは、ノード間のエッジに方向のないグラフです。対照的に、有向グラフは、エッジに方向を持つグラフです。

グラフを表す2つの一般的な方法は、隣接リストと隣接マトリックスです。

隣接行列グラフ

隣接リストは、左側がノード、右側が接続されている他のすべてのノードのリストとして表されます。

隣接行列は数値のグリッドであり、各行または列はグラフ内の異なるノードを表します。行と列の交点には、関係を示す数字があります。ゼロは、エッジまたは関係がないことを意味します。関係があるということです。 1より大きい数値を使用して、異なる重みを表示できます。

トラバーサルアルゴリズムは、グラフ内のノードをトラバースまたは訪問するアルゴリズムです。トラバーサルアルゴリズムの主なタイプは、幅優先検索と深さ優先検索です。用途の1つは、ノードがルートノードにどれだけ近いかを判断することです。以下のビデオでJavaScriptで幅優先検索を実装する方法をご覧ください。

JavaScriptの隣接行列グラフの幅優先検索のコードを参照してください。

隣接リスト(グラフ)時間の複雑さ
╔===============╦===========╗
║アルゴリズム║時間║
╠===============╬===========╣
║ストレージ║O(| V | + | E |)║
Ver頂点を追加║O(1)║
Edgeエッジの追加║O(1)║
Ver頂点を削除║O(| V | + | E |)║
Edgeエッジを削除║O(| E |)║
║クエリ║O(| V |)║
╚===============╩===========╝

freeCodeCampの課題

  • 隣接リスト
  • 隣接行列
  • 発生率マトリックス
  • 幅優先検索
  • 深さ優先検索

もっと

Grokking Algorithmsという本は、データ構造/アルゴリズムに慣れておらず、コンピューターサイエンスの経験がない場合に、このトピックに関する最高の本です。この記事で取り上げられているデータ構造の一部を説明するために、わかりやすい説明と楽しい手描きのイラスト(Etsyの主任開発者である著者による)を使用しています。

または、その本に基づいて私のビデオコースをチェックアウトできます:Manning PublicationsのAlgorithms in Motion。 「39carnes」というコードを使用して、コースを39%オフにしてください!