知っておく必要のあるJavaの上位のデータ構造とアルゴリズム

ソフトウェア開発で最も重要なトピックを1つ選ぶとしたら、それはデータ構造とアルゴリズムです。これは、すべてのコンピュータープログラマーが利用できる基本的なツールと考えることができます。プログラミング中は、 データ構造 データを保存および整理し、 アルゴリズム それらの構造のデータを操作します。この記事には、のすべての一般的なデータ構造とアルゴリズムの詳細なレビューが含まれています 読者が十分に装備できるようにするため。

以下にリストされているのは、この記事で説明されているトピックです。

• Javaのデータ構造
  • 線形データ構造
  • 階層データ構造
• Javaのアルゴリズム
  • ソートアルゴリズム
  • 検索アルゴリズム

Javaのデータ構造

データ構造は、データを効率的に使用できるように、コンピューターにデータを格納および整理する方法です。大量のデータを効率的に管理する手段を提供します。また、効率的なデータ構造は、効率的なアルゴリズムを設計するための鍵です。

にこの「Javaのデータ構造とアルゴリズム」の記事では、次のような基本的なデータ構造について説明します。

• 線形データ構造
  • リンクリスト
  • スタック
  • キュー

• 階層データ構造
  • 二分木
  • ヒープ
  • ハッシュテーブル

それぞれをチェックしてみましょう。

Javaの線形データ構造

の線形データ構造 要素が連続していて、次のように順序付けられている要素です。1つしかない 最初の要素 1つしかありません 次の要素 、1つだけです 最後の要素 1つしかありません 前の要素 、他のすべての要素には 次 と 前 素子。

配列

アン アレイ 線形データ構造ですインデックスによってアクセスされる、類似した要素のグループを表します。データを格納する前に、配列のサイズを指定する必要があります。以下にリストされているのは、配列のプロパティです。

• 配列内の各要素は同じデータ型であり、同じサイズです
• 配列の要素は連続したメモリ位置に格納され、最初の要素は最小のメモリ位置から始まります
• 配列の要素にはランダムにアクセスできます
• 配列データ構造は完全に動的ではありません

例えば 、ビデオゲームでそのゲームのトップ10スコアを追跡したい場合があります。 10種類を使用するのではなく 変数 このタスクでは、グループ全体に1つの名前を使用し、インデックス番号を使用してそのグループのハイスコアを参照できます。

リンクリスト

に は、複数のノードのコレクションを持つ線形データ構造です。ここで、e各要素は、独自のデータと次の要素の場所へのポインタを格納します。リンクリストの最後のリンクはnullを指し、チェーンの終わりを示します。リンクリストの要素は、 ノード 。最初のノードは 頭 。最後のノードが呼び出されますインクルード 尾 。

リンクリストの種類

単一リンクリスト（一方向）

二重リンクリスト（双方向）

循環リンクリスト

簡単な例を次に示します。 一緒にリンクされているペーパークリップのチェーンのようなリンクリストを想像してみてください。上部または下部に別のペーパークリップを簡単に追加できます。真ん中に挿入するのも簡単です。あなたがしなければならないのは、真ん中のチェーンを外し、新しいペーパークリップを追加して、残りの半分を再接続することだけです。リンクリストも同様です。

スタック

スタック、 抽象データ構造は、のコレクションです オブジェクト に従って挿入および削除されます 後入れ先出し（LIFO） 原理。オブジェクトはいつでもスタックに挿入できますが、いつでも削除できるのは最後に挿入された（つまり「最後の」）オブジェクトだけです。以下にリストされているのは、スタックのプロパティです。

• 注文リストです。挿入と削除は、と呼ばれる一方の端でのみ実行できます。 上
• 最上位要素へのポインタを持つ再帰的データ構造
• 続く 後入れ先出し（LIFO） 原理
• 2つの最も基本的な方法をサポートします
  • push（e）：要素eをスタックの一番上に挿入します
  • pop（）：スタックの一番上の要素を削除して返します

スタックの実用的な例には、単語を逆にする場合が含まれます、の正しさを確認する 括弧シーケンス、ブラウザなどにバック機能を実装します。

キュー

別のタイプの抽象データ構造でもあります。スタックとは異なり、キューは、に従って挿入および削除されるオブジェクトのコレクションです。 先入れ先出し（FIFO） 原理。つまり、要素はいつでも挿入できますが、キューに最も長く存在する要素のみをいつでも削除できます。以下にリストされているのは、キューのプロパティです。

c ++ java python

• 多くの場合、 先入先出 リスト
• 2つの最も基本的な方法をサポートします
  • enqueue（e）：要素eを リア キューの
  • dequeue（）：要素を削除してから返します フロント キューの

キューはで使用されます2つのプロセス間でのデータの非同期転送、CPUスケジューリング、ディスクスケジューリング、およびリソースが複数のユーザー間で共有され、先着順で提供されるその他の状況。次の「Javaのデータ構造とアルゴリズム」の記事では、階層的なデータ構造があります。

Javaの階層データ構造

二分木

二分木は階層ツリーデータ構造 各ノードには最大2つの子があります 、と呼ばれる 左の子供 そしてその 右の子 。各バイナリツリーには、次のノードグループがあります。

• ルートノード：これは最上位のノードであり、メインノードと呼ばれることもあります。ルートから他のすべてのノードに到達できるため
• 二分木でもある左サブツリー
• 二分木でもある右サブツリー

以下にリストされているのは、バイナリツリーのプロパティです。

• 二分木は2つの方法でトラバースできます。
  • 深さ優先探索 ：インオーダー（Left-Root-Right）、プレオーダー（Root-Left-Right）、ポストオーダー（Left-Right-Root）
  • 幅優先探索 ：レベルオーダートラバーサル
• ツリートラバーサルの時間計算量：O（n）
• レベル「l」のノードの最大数= 2^l-1。

二分木のアプリケーションは次のとおりです。

• データが絶えず出入りする多くの検索アプリケーションで使用されます
• 視覚効果のためにデジタル画像を合成するためのワークフローとして
• ルーターテーブルを保存するために、ほぼすべての高帯域幅ルーターで使用されます
• ワイヤレスネットワークおよびメモリ割り当てでも使用されます
• 圧縮アルゴリズムなどで使用されます

バイナリヒープ

バイナリヒープは完全です二分木、ヒーププロパティに応答します。簡単に言えばそれ次のプロパティを持つ二分木のバリエーションです。

• ヒープは完全な二分木です。 おそらく最も深いものを除いて、すべてのレベルが完了している場合、ツリーは完了していると言われます。 TBinary Heapの彼の特性により、 。
• ヒーププロパティに従います： バイナリヒープは、 最小ヒープ または 最大ヒープ 。
  • 最小バイナリヒープ：Fまたはヒープ内のすべてのノード、ノードの値は 以下 子供の価値観
  • 最大バイナリヒープ：Fまたはヒープ内のすべてのノードの場合、ノードの値は 以上 子供の価値観

バイナリヒープの一般的なアプリケーションは次のとおりです。効率的な優先度付きキューを実装し、配列内のk個の最小（または最大）要素などを効率的に検索します。

ハッシュテーブル

あなたが持っていると想像してください オブジェクト それにキーを割り当てて、検索を非常に簡単にします。そのキーと値のペアを格納するには、データ構造のような単純な配列を使用できます。この配列では、キー（整数）をインデックスとして直接使用して、データ値を格納できます。ただし、キーが大きすぎてインデックスとして直接使用できない場合は、ハッシュと呼ばれる手法が使用されます。

ハッシュでは、を使用して大きなキーを小さなキーに変換します ハッシュ関数 。次に、値はと呼ばれるデータ構造に格納されます。に ハッシュ表。 ハッシュテーブルは、一意のキーを値にマップできる構造である辞書ADTを実装するデータ構造です。

一般に、ハッシュテーブルには2つの主要なコンポーネントがあります。

1. バケット配列： ハッシュテーブルのバケット配列は、サイズNの配列Aであり、Aの各セルは「バケット」、つまりキーと値のペアのコレクションと見なされます。整数Nは、配列の容量を定義します。
2. ハッシュ関数： これは、マップ内の各キーkを[0、N＆マイナス1]の範囲の整数にマップする任意の関数です。ここで、Nはこのテーブルのバケット配列の容量です。

オブジェクトをハッシュテーブルに入れると、異なるオブジェクトが同じハッシュコードを持つ可能性があります。これはと呼ばれます 衝突 。衝突に対処するために、連鎖やオープンアドレス法などの手法があります。

したがって、これらはJavaで最も基本的で最も頻繁に使用されるデータ構造です。これらのそれぞれに気付いたので、次の場所に実装を開始できます。 。これで、この「Javaのデータ構造とアルゴリズム」の記事の最初の部分が完了しました。次のパートでは、基本的なアルゴリズムと、並べ替えと検索、分割統治、欲張りアルゴリズム、動的計画法などの実用的なアプリケーションでそれらを使用する方法。

Javaのアルゴリズム

複雑な数学的計算を解くためのツールとして歴史的に使用されてきたアルゴリズムは、コンピューターサイエンス、特にデータ構造と深く関係しています。 アルゴリズムは 有限の期間で特定の問題を解決する方法を説明する一連の指示。 それらは2つの方法で表されます。

• フローチャート - それはアルゴリズムの制御フローの視覚的表現
• 擬似コード - それ最終的なソースコードを近似するアルゴリズムのテキスト表現です

注意： アルゴリズムのパフォーマンスは、時間の複雑さと空間の複雑さに基づいて測定されます。ほとんどの場合、アルゴリズムの複雑さは、問題とアルゴリズム自体に依存します。

Javaのアルゴリズムの2つの主要なカテゴリである次のことを調べてみましょう。

• Javaでのソートアルゴリズム
• Javaでのアルゴリズムの検索

Javaでのソートアルゴリズム

並べ替えアルゴリズムは、リストの要素を特定の順序で配置するアルゴリズムです。最も一般的に使用される順序は、番号順と辞書式順序です。この「データ構造とアルゴリズム」の記事では、いくつかの並べ替えアルゴリズムについて説明します。

Javaでのバブルソート

多くの場合、シンクソートと呼ばれるバブルソートは、最も単純なソートアルゴリズムです。並べ替えるリストを繰り返しステップ実行し、隣接する要素の各ペアを比較して、順序が間違っている場合はそれらを交換します。バブルソートは、水に浮かぶバブルのように、配列の一番上にある要素を除外するため、その名前が付けられています。

これがバブルソートアルゴリズムを表す擬似コード（昇順のソートコンテキスト）。

a []はサイズNの配列です。開始BubbleSort（a []）は整数iを宣言します。i= 0からN-1の場合はj = 0からN-i-1の場合はa [j]> a [j +1の場合]次に、a [j]、a [j + 1] endをスワップして、endを返します。BubbleSort

このコードは、N個のデータ項目の1次元配列を昇順で並べ替えます。外側のループにより、N-1がアレイを通過します。各パスは内部ループを使用してデータ項目を交換し、次に小さいデータ項目が配列の先頭に向かって「バブル」するようにします。しかし、問題は、リストがソートされていることを知るために、アルゴリズムがスワップなしで1つのパス全体を必要とすることです。

最悪および平均のケース時間の複雑さ： O（n * n）。最悪の場合は、配列が逆ソートされたときに発生します。

ベストケースの時間計算量： オン）。配列がすでにソートされている場合に最適なケースが発生します。

Javaでの選択ソート

選択ソートは、検索とソートの両方を組み合わせたものです。アルゴリズムは、ソートされていない部分から最小要素（昇順を考慮）を繰り返し見つけて配列内の適切な位置に配置することにより、配列をソートします。

これは、選択ソートアルゴリズム（昇順のソートコンテキスト）を表す擬似コードです。

a []はサイズNの配列ですbeginSelectionSort（a []）for i = 0 to n-1 / *現在の要素を最小値として設定* / min = i / *最小要素を見つける* / for j = i + 1 list [j]の場合はnに
コードから理解できるように、並べ替えが配列を通過する回数は、配列内のアイテムの数より1回少なくなります。内側のループは次に小さい値を見つけ、外側のループはその値を適切な場所に配置します。選択ソートは、O（n）を超えるスワップを行うことはなく、メモリ書き込みがコストのかかる操作である場合に役立ちます。
 時間計算量： オン2）ネストされたループが2つあるため。
 補助スペース： または（1）。
 Javaでの挿入ソート 
挿入ソートは、一度に1つの入力要素を使用してリストを反復処理し、最終的にソートされた配列を作成する単純なソートアルゴリズムです。これは非常に単純で、小さなデータセットでより効果的です。安定したインプレースソート技術です。
これは、挿入ソートアルゴリズム（昇順のソートコンテキスト）を表す擬似コードです。
a []はサイズNの配列です。i= 1からNの場合はInsertionSort（a []）を開始しますkey = a [i] j = i --1 while（j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j-1終了、a [j + 1] =終了のキー終了InsertionSort
コードからわかるように、挿入ソートアルゴリズム入力データから1つの要素を削除し、ソートされたリスト内でその要素が属する場所を見つけて、そこに挿入します。入力要素がソートされないままになるまで繰り返されます。
 最良の場合： 最良のケースは、入力がすでにソートされている配列である場合です。この場合、挿入ソートの実行時間は線形です（つまり、＆Theta（n））。
 最悪の場合：  最も単純な最悪の場合の入力は、逆の順序でソートされた配列です。
 Javaのクイックソート 
クイックソートアルゴリズムは、分割統治法によって機能する、高速で再帰的な非安定のソートアルゴリズムです。要素をピボットとして選択し、選択したピボットの周囲に指定された配列を分割します。
 クイックソートを実装する手順：  
 
適切な「ピボットポイント」を選択します。
リストを2つのリストに分割しますこのピボット要素に基づいています。ピボット要素よりも小さい要素はすべて左側のリストに配置され、大きい要素はすべて右側のリストに配置されます。要素がピボット要素と等しい場合、その要素は任意のリストに入れることができます。 これは、パーティション操作と呼ばれます。
小さいリストをそれぞれ再帰的に並べ替えます。 
クイックソートアルゴリズムを表す擬似コードは次のとおりです。
QuickSort（A as array、low as int、high as int）{if（low
上記の擬似コードでは、 パーティション（） 関数はパーティション操作を実行し、 クイックソート（） 関数は、生成された小さなリストごとにパーティション関数を繰り返し呼び出します。平均的な場合のクイックソートの複雑さは＆Theta（n log（n））であり、最悪の場合は＆Theta（n2）です。
 Javaでのマージソート 
マージソートは、分割統治法でも機能する、高速で再帰的な安定したソートアルゴリズムです。クイックソートと同様に、マージソートは要素のリストを2つのリストに分割します。これらのリストは個別にソートされてから結合されます。リストの組み合わせ中に、要素はリストの適切な場所に挿入（またはマージ）されます。
マージソートアルゴリズムを表す擬似コードは次のとおりです。
プロシージャMergeSort（a as array）if（n == 1）return a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] .. .. a [n] l1 = mergesort（l1）l2 = mergesort（l2）return merge（l1、l2）end procedure procedure merge（a as array、b as array）var c as array while（a and b has element）if（ a [0]> b [0]）b [0]をcの末尾に追加b [0]をbから削除elsea [0]をcの末尾に追加a [0]を末尾から削除ifend while while （aには要素があります）a [0]をcの末尾に追加しますa [0]を末尾から削除しますwhile（bには要素があります）b [0]をcの末尾に追加しますb [0]をbの末尾から削除しますc手順の終了
 マージソート（） 関数はリストを2つに分割し、呼び出します マージソート（） これらのリストで個別に処理し、merge（）関数のパラメーターとして送信して結合します。アルゴリズムの複雑さはO（n log（n））であり、幅広いアプリケーションがあります。
 Javaでのヒープソート 
ヒープソートは、比較ベースのソートアルゴリズムです二分ヒープのデータ構造。あなたはそれを改善されたバージョンf選択ソートと考えることができます。入力をソートされた領域とソートされていない領域に分割し、最大の要素を抽出してそれをソートされた領域に移動することにより、ソートされていない領域を繰り返し縮小します。
 クイックソートを実装する手順（昇順）： 
並べ替え配列を使用して最大ヒープを構築する
このポインでt、最大のアイテムはヒープのルートに格納されます。ヒープの最後の項目に置き換えて、ヒープのサイズを1つ減らします。最後に、ツリーのルートをヒープ化します。
ヒープのサイズが1より大きくなるまで、上記の手順を繰り返します。
これは、ヒープソートアルゴリズムを表す擬似コードです。
Heapsort（a as array）for（i = n / 2-1）to i> = 0 heapify（a、n、i）for i = n-1 to 0 swap（a [0]、a [i]）heapify （a、i、0）heapifyのend for end（a as array、n as int、i as int）maximum = i //最大をルートとして初期化intl eft = 2 * i + 1 // left = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 if（left a [largest]）largest = left if（right a [largest]）largest = right if（largest！= i）swap（ a [i]、A [最大]）Heapify（a、n、最大）end heapify
これらとは別に、イントロソート、カウントソートなど、あまり知られていない他のソートアルゴリズムがあります。この「データ構造とアルゴリズム」の記事の次のアルゴリズムセットに移り、検索アルゴリズムについて見ていきましょう。
 Javaでのアルゴリズムの検索 
検索は、通常のビジネスアプリケーションで最も一般的で頻繁に実行されるアクションの1つです。検索アルゴリズムは、アイテムのコレクションから指定されたプロパティを持つアイテムを見つけるためのアルゴリズムです。最も一般的に使用される2つの検索アルゴリズムを見てみましょう。
 Javaの線形検索アルゴリズム 
線形検索または順次検索は、最も単純な検索アルゴリズムです。これには、要素が見つかるか、構造の終わりに到達するまで、指定されたデータ構造内の要素を順次検索することが含まれます。要素が見つかった場合はアイテムの場所が返され、見つからなかった場合はアルゴリズムがNULLを返します。
Javaで線形検索を表す擬似コードは次のとおりです。
プロシージャlinear_search（a []、value）for i = 0 to n-1 if a [i] = value then print'Found 'return i end if print'Not found' end for end linear_search
それはブルートフォースアルゴリズム。確かに最も単純ですが、非効率的であるため、最も一般的ではありません。線形探索の時間計算量は オン） 。
 Javaでの二分探索アルゴリズム 
二分探索は、対数探索とも呼ばれ、すでに並べ替えられた配列内のターゲット値の位置を見つける検索アルゴリズムです。入力コレクションを半分に分割し、アイテムをリストの中央の要素と比較します。要素が見つかった場合、検索はそこで終了します。それ以外の場合は、ターゲット要素が中央の要素よりも小さいか大きいかに基づいて、配列の適切なパーティションを分割して選択することにより、要素を探し続けます。
Javaでのバイナリ検索を表す擬似コードは次のとおりです。
プロシージャbinary_searchソートされた配列nサイズの配列x検索対象の値lowerBound = 1 upperBound = n、upperBoundの場合はxが見つかりません
upperBound（ポインタ）がlowerBound（最後の要素）を超えると、検索は終了します。これは、配列全体を検索したが、要素が存在しないことを意味します。これは、主に検索時間が短いため、最も一般的に使用される検索アルゴリズムです。二分探索の時間計算量は オン） これは、 オン） 線形探索の時間計算量。
これで、この「Javaのデータ構造とアルゴリズム」の記事は終わりです。 Javaの最も基本的で重要なトピックの1つを取り上げました。この記事であなたと共有されているすべてのことを明確にしてください。
  できるだけ練習し、経験を元に戻してください。   
 チェックしてください    25万人以上の満足した学習者のネットワークを持つ信頼できるオンライン学習会社であるEdurekaが世界中に広がっています。私たちはあなたの旅のすべてのステップであなたを助けるためにここにいます、このJavaインタビューの質問に加えてなるために、私たちはJava開発者になりたい学生と専門家のために設計されたカリキュラムを考え出します。 
 質問がありますか？この「Javaのデータ構造とアルゴリズム」のコメントセクションで言及してください  記事と私たちはできるだけ早くあなたに返信します。