Java で一般的に使用されるデータ構造は何ですか?

Java データ構造には次のものが含まれます: 1. 配列、2. 再帰的データ構造であるリンク リスト、3. 「後入れ先出し」および「先入れ後」の原則に従ってデータを格納するスタックout"; 4. キュー; 5. n (n>0) 個の限定されたノードで構成される階層関係のコレクションであるツリー; 6. ヒープ; 7. グラフ; 8. ハッシュ テーブル。

#このチュートリアルの動作環境: Windows7 システム、Java8 バージョン、DELL G3 コンピューター。

一般的な Java データ構造

これら 8 つのデータ構造の違いは何ですか?

①、配列

利点:

• インデックスによる要素のクエリは非常に高速です。

##インデックスによって配列を走査することも非常に便利です。

• #欠点:

#配列のサイズは作成後に決定され、拡張できません;

• 配列は 1 つのタイプのデータのみを保存できます;

• 要素の追加と削除の操作は、他の要素を移動する必要があるため時間がかかります。

②. リンク リスト

書籍「アルゴリズム (第 4 版)」では、リンク リストを次のように定義しています。

• リンク リストは再帰的なデータ構造です。空 (null) か、ノードへの参照 (ノード) です。ノードには要素と、別のリンク リストへのポインタもあります。 。

  Java の LinkedList クラスは、リンク リストの構造をコードの形式で非常に鮮明に表現できます。

  public class LinkedList<E> {
      transient Node<E> first;
      transient Node<E> last;
  
      private static class Node<E> {
          E item;
          Node<E> next;
          Node<E> prev;
  
          Node(Node<E> prev, E element, Node<E> next) {
              this.item = element;
              this.next = next;
              this.prev = prev;
          }
      }
  }

これは、これは二重リンク リストです。現在の要素項目には prev と next の両方がありますが、最初の prev は null で、last の next は null です。一方向リンクリストの場合、次のみが存在し、前は存在しません。

リンク リストは順次に格納する必要がないため、リンク リストの挿入時および挿入時に O(1) の時間計算量を達成できます。削除 (再実行する必要があります。参照をポイントするだけで、配列などの他の要素を移動する必要はありません)。さらに、リンク リストは、データ サイズを事前に知っておく必要があるという配列の欠点も克服し、柔軟な動的なメモリ管理を可能にします。

利点:

容量を初期化する必要がない;

• 任意の要素を追加できる;

• 挿入および削除時に更新する必要があるのは参照のみです。

• #欠点:

には多数の参照が含まれており、大量のメモリ領域を占有します。

• 検索 要素はリンク リスト全体を検索する必要があり、時間がかかります。

③、スタック

スタックはバケツのようなもので、底部は密閉されており、上部は開いています。水缶は出入りできます。バケツを使ったことのある友人なら、この原理を理解しているはずです。最初に入る水はバケツの底にあり、後から入る水はバケツの上部にあり、最後に入る水が最初に注ぎ出されます。そして最初に入った水は最後に注ぎ出されます。 同様に、スタックは「後入れ先出し」と「先入れ後出し」の原則に従ってデータを保存します。最初に挿入されたデータはスタックの一番下にプッシュされ、その後、挿入されたデータがスタックの最後に挿入されます。データはスタックの先頭にあり、スタックの先頭から順に読み出されます。

④、キュー

キューは、両端が開いた水道管の一部のようなものです。 . 水は一方の端から入り、もう一方の端から出ます。先に入った水が先に出て、最後に入った水が最後に出ます。 水道管とは少し異なり、キューは 2 つの端を定義します。一方の端はキューの先頭と呼ばれ、もう一方の端はキューの末尾と呼ばれます。キューの先頭では削除操作 (デキュー) のみが許可され、キューの末尾では挿入操作 (エンキュー) のみが許可されます。

⑤. ツリー

ツリーは典型的な非線形構造であり、n A で構成されます。 (n>0) 個の限定されたノードで構成される階層関係のセット。

これが「ツリー」と呼ばれる理由は、このデータ構造が根が上にあり、葉が下にあることを除いて、逆さまの木のように見えるためです。ボトム。ツリー データ構造には次の特徴があります:

各ノードには限られた子ノードしかないか、子ノードがありません;

• 親ノードがありませんこのノードはルート ノードと呼ばれます。

• ルート以外の各ノードには親ノードが 1 つだけあります。

• ルート ノードは除きます。 、各子ノードは、複数の互いに素なサブツリーに分割できます。

• 次の図は、ツリーに関するいくつかの用語を示しています。

  

  

  

  

  

  

  バイナリ検索ツリーの特性に基づくと、他のデータ構造に対する利点は、検索と挿入の時間計算量が O(logn) と低いことです。上の図から 5 つの要素を見つけたい場合は、ルート ノード 7 から開始します。5 が見つかった場合、それは 7 の左側にある必要があります。4 が見つかった場合、5 は 4 の右側にある必要があります。 6 が見つかった場合、5 は 6 の左側にある必要があります。横、見つかりました。

  理想的には、BST を通じてノードを見つけることで、チェックする必要があるノードの数を半分に減らすことができます。

  バランス二分木: 任意のノードの 2 つのサブツリー間の高さの差が 1 以下の場合に限り、二分木になります。 1962 年に旧ソ連の数学者アデルセ・ヴェルスキルとランディスによって提案された高度にバランスの取れた二分木は、科学者の英語名に従って AVL 木とも呼ばれます。

  バランス二分木は本質的には二分探索木ですが、左右のサブツリー間の高さの差を制限し、線形構造に向かって進化する傾向にある傾いたツリーなどの状況を回避するために、それぞれの二分探索木はノードの左右の部分木が制限されており、左右の部分木の高さの差をバランス係数と呼び、ツリー内の各ノードのバランス係数の絶対値は 1 以下です。

  バイナリ ツリーのバランスをとる際の難しさは、ノードが削除または追加されたときに、左右の回転によって左右のバランスをどのように維持するかということです。

  Java で最も一般的なバランスのとれた二分木は赤黒ツリーです。ノードは赤または黒です。二分木のバランスは色の制約によって維持されます:

  1) 各ノード赤または黒のみ可能です。

  2) ルート ノードは黒です。

  3) 各リーフ ノード (NIL ノード、空のノード) は黒です。

  4) ノードが赤の場合、その子ノードは両方とも黒です。つまり、隣接する 2 つの赤いノードはパス上に表示できません。

  5) 任意のノードからその各リーフへのすべてのパスには、同じ数の黒いノードが含まれます。

  

  ⑥、ヒープ

  ヒープは、ツリーの配列オブジェクトとみなすことができます。次の特性:

  • ヒープ内のノードの値は、常にその親ノードの値よりも大きくも小さくもありません。

  • ヒープは常に完全なバイナリ ツリーです。
  最大のルート ノードを持つヒープは最大ヒープまたは大ルート ヒープと呼ばれ、最小のルート ノードを持つヒープは最小ヒープまたは小ルート ヒープと呼ばれます。

  

  線形構造では、データ要素と各データ要素 (最初と最後を除く) の間に一意の線形関係が満たされます。それぞれには、固有の「先行者」と「後続者」;
  ツリー構造では、データ要素間に明らかな階層関係があり、各データ要素は前の層 (親ノード) の 1 つの要素にのみ関連しており、複数の要素に関連付けられています。次の層の要素 (子ノード) は関連しています;
  グラフ構造では、ノード間の関係は任意であり、グラフ内の任意の 2 つのデータ要素が関連している可能性があります。

  ⑧、ハッシュ テーブル

  ハッシュ テーブルは、ハッシュ テーブルとも呼ばれ、キー コード値 (キー) を渡すことができるハッシュ テーブルの一種です。 -value) 直接アクセスできるデータ構造であり、その最大の特徴は、検索、挿入、削除を迅速に実装できることです。
  配列の最大の特徴は、検索は簡単ですが、挿入や削除が難しいことですが、逆に、リンクリストは、検索は難しいが、挿入や削除が簡単であることです。ハッシュ テーブルは両方の利点を完璧に組み合わせており、Java の HashMap はこれに基づいてツリーの利点も追加します。

  

  ハッシュ関数は、ハッシュ テーブルで非常に重要な役割を果たし、任意の長さの入力を固定長の出力に変換できます。ハッシュ値。ハッシュ関数を使用すると、データ シーケンスへのアクセス プロセスがより高速かつ効率的になり、データ要素を迅速に見つけることができます。

  キーワードが k の場合、その値は hash(k)

  の保存場所に保存されます。したがって、k に対応する値はトラバーサルなしで直接取得できます。 ###

  2 つの異なるデータ ブロックにおいて、同じハッシュ値を持つ可能性は非常に小さい、つまり、特定のデータ ブロックについて、同じハッシュ値を持つデータ ブロックを見つけることは非常に困難です。さらに、データ ブロックの場合、その 1 ビットが変更されただけでも、ハッシュ値の変化は非常に大きくなります。これがハッシュの値です。

  可能性は非常に低いですが、それでも発生します。ハッシュの競合が発生した場合、Java の HashMap は配列内の同じ位置にリンク リストを追加します。リンク リストの長さが 8 を超える場合は、 、赤と黒に変換されます ツリーが処理されます - これはいわゆるジッパーメソッド (配列リンクリスト) です。

  プログラミング関連の知識について詳しくは、プログラミング ビデオをご覧ください。 ！

以上がJava で一般的に使用されるデータ構造は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。