知っておくべき10種類のデータ構造+ビデオと演習

Netologyブログ専用のフリーランスのエディターであるEkaterina Malakhovaは、データ構造の主要なタイプに関するBeau Carnesの記事を修正しました。

「悪いプログラマーはコードについて考えます。 優れたプログラマーは、データ構造とそれらの関係について考えます。

データ構造はソフトウェア開発プロセスで重要な役割を果たし、開発者へのインタビューでよく質問されます。 良いニュースは、本質的に、データを整理および保存するための特別な形式にすぎないことです。



この記事では、最も一般的な10個のデータ構造を示します。 それぞれについて、ビデオとJavaScriptでの実装の例を示します。 練習できるように、新しいfreeCodeCampカリキュラムのベータ版からいくつかの演習も追加しました。



一部のデータ構造には、Big O表記の時間的な複雑さが含まれていることに注意してください。 時間の複雑さは実装によって異なる場合があるため、これはそれらすべてに適用されるわけではありません。 Big O表記について詳しく知りたい場合は、 Briana Marieによるこのビデオをご覧ください。



記事では、これらのデータ構造のJavaScriptでの実装例を示します。Cなどの低レベル言語を使用する場合にも役立ちます。JavaScriptを含む多くの高レベル言語には、既に説明するほとんどのデータ構造の実装が既にあります。 ただし、こうした知識は、仕事を探す際に大きな利点となり、高性能なコードを書く際に役立ちます。

リンクリスト

リンクリストは、基本的なデータ構造の1つです。 多くの場合、配列またはリンクリストを使用して他の多くの構造を実装できるため、配列と比較されます。 これら2つのタイプには長所と短所があります。





これがリンクリストの仕組みです。



リンクリストは、一緒にシーケンスを形成するノードのグループで構成されます。 各ノードには2つの要素が含まれます。その中に格納される実際のデータ（任意のタイプのデータ）と、シーケンス内の次のノードへのポインター（またはリンク）です。 二重にリンクされたリストもあります。各ノードには、リスト内の次の要素と前の要素へのポインタがあります。



リンクリストの基本操作には、リスト内のアイテムの追加、削除、検索が含まれます。



JavaScriptの実装例

    ╔═══════════╦═════════════════╦═══════════════╗ ║  ║  ║   ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

スタック

スタックは、要素の追加または削除を開始時にのみ可能にする基本的なデータ構造です。 書籍のスタックのように見えます。スタックの真ん中にある本を見たい場合は、最初に本を削除する必要があります。



スタックはLIFOの原則に従って構成されています（後入れ先出し、「後入れ先出し」）。 これは、スタックに最後に追加したアイテムが最初にスタックを終了することを意味します。





これがスタックの仕組みです



スタックでは、要素の追加（プッシュ）、要素の削除（ポップ）、およびスタックの内容の表示（ピップ）の3つの操作を実行できます。



JavaScriptの実装例

    ╔═══════════╦═════════════════╦═══════════════╗ ║  ║  ║   ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

キュー

この構造は、食料品店のキューとして表すことができます。 最初に来た人に奉仕する最初の人-すべてが人生のようです。





これはキューです



キューは、FIFOの原則（先入れ先出し、「先着順」）に従って配置されます。 これは、以前に追加されたすべてのアイテムが削除された後にのみアイテムを削除できることを意味します。



キューを使用すると、2つの基本操作を実行できます。キューの最後に要素を追加（ enqueue ）および最初の要素を削除（ dequeue ）します。



JavaScriptの実装例

    ╔═══════════╦═════════════════╦═══════════════╗ ║  ║  ║   ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

多くの

それはたくさんのように見えます



多くの場合、データ値を繰り返すことなく特定の順序で保存しません。 要素の追加と削除だけでなく、2つのセットに同時に適用できるさらに重要な機能がいくつかあります。

• ユニオンは、2つの異なるセットのすべての要素を結合し、それらを1つに（重複なしで）変換します。
• 交差点は2つのセットを分析し、両方の初期セットに存在する要素の1つを作成します。
• 違いは、あるセットにはあるが別のセットにはない要素のリストを表示します。
• サブセットは、あるセットに別のセットのすべての要素が含まれているかどうかを示すブール値を返します。

JavaScriptの実装例

FreeCodeCamp演習

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

地図

マップは、キーと値のペアでデータを保存する構造です。各キーは一意です。 連想配列または辞書とも呼ばれることがあります。 マップは、データをすばやく見つけるためによく使用されます。 次のことを実行できます。

• コレクションにペアを追加します。
• コレクションからペアを削除します。
• 既存のペアを変更します。
• 特定のキーに関連付けられた値を検索します。

これはマップの構造です



JavaScriptの実装例

FreeCodeCamp演習

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

ハッシュテーブル

これがハッシュテーブルとハッシュ関数の仕組みです



ハッシュテーブルは、キーと値のペアを含むマップのような構造です。 ハッシュ関数を使用して、データブロックの配列のインデックスを計算し、目的の値を見つけます。



通常、ハッシュ関数は入力として文字列を受け取り、数値を出力します。 同じ入力に対して、ハッシュ関数は同じ数を返さなければなりません。 2つの異なる入力が同じ結果でハッシュされると、衝突が発生します。 目標は、このような場合を最小限にすることです。



したがって、キーと値のペアをハッシュテーブルに入力すると、キーはハッシュ関数を通過して数値になります。 将来、この番号は実際のキーとして使用され、特定の値に対応します。 同じキーを再度入力すると、ハッシュ関数がそれを処理し、同じ数値結果を返します。 この結果は、関連する値を見つけるために使用されます。 このアプローチにより、平均検索時間が大幅に短縮されます。



JavaScriptの実装例

   - ╔═══════════╦═════════════════╦═══════════════╗ ║  ║  ║   ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(1) ║ O(n) ║ ║ Insert ║ O(1) ║ O(n) ║ ║ Delete ║ O(1) ║ O(n) ║ ╚═══════════╩═════════════════╩═══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

バイナリ検索ツリー

バイナリ検索ツリー



ツリーは、ノードで構成されるデータ構造です。 次のプロパティが固有です。

• 各ツリーにはルートノードがあります（上部）。
• ルートノードには0個以上の子ノードがあります。
• 各子ノードには、0個以上の子ノードがあります。

バイナリ検索ツリーには、2つの追加のプロパティがあります。

• 各ノードには、最大2つの子ノード（子孫）があります。
• 各ノードは、右側の子孫よりも小さく、左側の子孫はそれ自体よりも小さくなっています。

バイナリ検索ツリーを使用すると、アイテムをすばやく検索、追加、削除できます。 これらは、各操作の時間がツリー内の要素の総数の対数に比例するように配置されます。



JavaScriptの実装例

      ╔═══════════╦═════════════════╦══════════════╗ ║  ║  ║  ║ ╠═══════════╬═════════════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Delete ║ O(log n) ║ O(n) ║ ╚═══════════╩═════════════════╩══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

プレフィックスツリー

プレフィックス（ロード済み）ツリーは、検索ツリーの一種です。 データはラベルに保存され、各ラベルはツリー内のノードを表します。 このような構造は、たとえば、オートコンプリート機能などのために、単語を保存し、それらをすばやく検索するためによく使用されます。







これがプレフィックスツリーの仕組みです



言語接頭辞ツリーの各ノードには、単語の1文字が含まれます。 単語を作成するには、一度に1文字ずつ、木の枝をたどる必要があります。 ツリーは、文字の順序が他の単語と異なる場合、または単語が終了する場合に分岐し始めます。 各ノードには、文字（データ）と、単語の最後かどうかを示すブール値が含まれます。



イラストを見て、言葉を構成してみてください。 常に最上位のルートノードから開始し、下に移動します。 このツリーには、ボール、バット、人形、do、dork、dorm、send、senseの単語が含まれています。



JavaScriptの実装例

FreeCodeCamp演習

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

バイナリヒープ

バイナリヒープは別のツリーのようなデータ構造です。 その中で、各ノードには2つ以下の子孫しかありません。 これは完全なツリーでもあります。つまり、その中のすべてのレベルはデータで完全に占有され、最後のレベルは左から右に埋められます。





したがって、最小および最大ヒープが配置されます



バイナリヒープは最小または最大にできます。 最大ヒープでは、ノードのキーは常にその子孫のキー以上です。 最小限のヒープでは、すべてが逆になります。ノードのキーは、その子孫のキー以下です。



同じレベルのノードの順序とは対照的に、バイナリヒープ内のレベルの順序は重要です。 この図は、3番目のレベルの最小ヒープでは、値が順不同になることを示しています（10、6、および12）。



JavaScriptの実装例

     ╔═══════════╦══════════════════╦═══════════════╗ ║  ║   ║   ║ ╠═══════════╬══════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(log n) ║ ║ Delete ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═══════════╩══════════════════╩═══════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

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

カウント

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



ソーシャルネットワークはこの原則に従って編成されます。ノードは人であり、エッジはそれらの関係です。







グラフは、指向型と非指向型の2つの主なタイプに分けられます。 無向グラフの場合、ノード間のエッジには方向がありませんが、指向グラフのエッジには方向があります。



ほとんどの場合、グラフは2つの形式のいずれかで表されます。それは、隣接リストまたは隣接行列のいずれかです。





隣接行列グラフ



隣接リストは、1つのノードが左側にあり、他のすべてのノードが接続されている右側の要素のリストとして表すことができます。



隣接行列は、数字のあるグリッドで、各行または列はグラフ内の個別のノードに対応します。 行と列の交点には、接続の存在を示す番号があります。 ゼロは、それが存在しないことを意味します。 ユニット-接続があること。 各結合の重みを示すために、1より大きい数値が使用されます。



グラフ内のエッジと頂点を表示するための特別なアルゴリズム、いわゆるトラバーサルアルゴリズムがあります。 主なタイプには、 幅優先検索と深さ 優先検索が含まれます 。 あるいは、グラフの1つまたは別の頂点がルートノードにどれだけ近いかを判断するために使用できます。 以下のビデオは、JavaScriptで幅優先検索を行う方法を示しています。



JavaScriptの実装例

     () ╔═══════════════╦════════════╗ ║  ║  ║ ╠═══════════════╬════════════╣ ║ Storage ║ O(|V|+|E|) ║ ║ Add Vertex ║ O(1) ║ ║ Add Edge ║ O(1) ║ ║ Remove Vertex ║ O(|V|+|E|) ║ ║ Remove Edge ║ O(|E|) ║ ║ Query ║ O(|V|) ║ ╚═══════════════╩════════════╝
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FreeCodeCamp演習

• グラフの概要
• 隣接リスト
• 隣接行列
• 発生率マトリックス
• 幅優先検索
• 深さ優先検索

さらに詳しく

以前にアルゴリズムやデータ構造に出会ったことがなく、ITのバックグラウンドがない場合、Grokking Algorithmsは最高の本です。 この記事では、この記事で取り上げたデータ構造の一部を含め、楽しいイラスト（著者はEtsyの主要な開発者）を使用して提示されています。

Netologyの編集者から

ビッグデータコースのNetologyリクルート：



1. プログラム「ビッグデータ：大規模なデータセットの操作の基本」



誰のために：エンジニア、プログラマー、アナリスト、マーケティング担当者-ビッグデータテクノロジーを掘り下げ始めたばかりの人。

• 技術の歴史と基礎の紹介。
• ビッグデータを収集する方法。
• データ型;
• 基本的および高度なビッグデータ分析方法。
• 大規模なデータアレイを操作するためのプログラミング、ストレージ、および処理アーキテクチャの基礎。

クラス形式：オンライン。



参照による詳細→ http://netolo.gy/dJd



2. プログラム「データサイエンティスト」



誰のために：ビッグデータで働いている、またはそれをしようとしているスペシャリスト、およびデータサイエンスの分野でキャリアを積むことを計画している人。 トレーニングには、少なくとも1つのプログラミング言語（できればPython）を知っていて、高校の数学（できれば大学）でプログラムを覚えておく必要があります。



コーストピック：

• 基本的なツール、Hadoop、クラスターコンピューティングでトレーニングを表現します。
• 決定木、k最近傍法、ロジスティック回帰、クラスタリング。
• データの次元削減、分解方法、スペースの修正。
• 推奨システムの紹介。
• 画像認識、マシンビジョン、ニューラルネットワーク;
• ワープロ、配信セマンティクス、チャットボット。
• 時系列、ARMA / ARIMAモデル、複雑な予測モデル。

クラス形式：オフライン、モスクワ、デジタル10月センター。 Yandex Data Factory、Rostelecom、Sberbank-Technology、Microsoft、OWOX、Clever DATA、MTSの専門家が教えています。



リンクの詳細。