JavaScriptのリンクリストとは何ですか

JavaScriptのリンクリストは、各ノードに次のノードへの参照が含まれるノードで構成される手動で実装されたデータ構造です。 1.クラスを使用して実装され、値と次のポインターを保持しているListNodeクラス、およびLinkedListクラスがヘッドと操作を管理します。 2.追加方法は、最後のノードに移動して新しいノードをリンクすることにより、ノードを最後に追加します。 3.印刷方法は頭から横断し、nullに到達するまで値を収集し、順番に出力します。 4。タイプには、単一リンク（次のポインターのみ）、二重リンク（次のポインターおよび以前のポインター）、および円形リンク（最後のノードがヘッドにポイント）が含まれます。 5.リンクされたリストは、頻繁な挿入/削除（開始時のO（1））および動的サイジングに有益ですが、ランダムアクセス（O（n）トラバーサル）がありません。 JavaScriptの配列の最適化にもかかわらず、リンクされたリストはアルゴリズムの問​​題解決や技術的なインタビューに役立ち、より複雑なデータ構造の基礎概念を形成します。

JavaScriptのリンクリストは、要素のコレクションを保存するために使用されるデータ構造であり、各要素（ノードと呼ばれる）は、シーケンスの次のノードへの値と参照（またはポインター）を保持します。配列とは異なり、リンクされたリストは、要素を連続したメモリの場所に保存しません。代わりに、ポインターを介してリンクされます。

JavaScriptには組み込みのリンクリストタイプがありませんが（配列の場合と同様）、オブジェクトまたはクラスを使用して1つを実装できます。

ノードの構造

リンクリストの各ノードには通常、2つの部分があります。

• value ：ノードが保持しているデータ（任意のタイプ（数字、文字列、オブジェクトなど）になります。
• next ：リスト内の次のノードへの参照（または最後のノードの場合はnull ）

 class listnode {
  Constructor（value）{
    this.value = value;
    this.next = null;
  }
}

シンプルなリンクリストを作成します

基本的なリンクリストを作成する方法は次のとおりです。

 class linkedlist {
  constructor（）{
    this.head = null;
    this.size = 0;
  }

  //最後に新しいノードを追加します
  append（value）{
    const newNode = new listNode（value）;
    if（！this.head）{
      this.head = newNode;
    } それ以外 {
      current = this.head;
      while（current.next）{
        current = current.next;
      }
      current.next = newNode;
    }
    this.size;
  }

  //リスト内のすべての値を印刷します
  print（）{
    const値= [];
    current = this.head;
    while（current）{
      values.push（current.value）;
      current = current.next;
    }
    console.log（values.join（ ' - >'））;
  }
}

//使用の例：
const list = new LinkedList（）;
list.append（10）;
list.append（20）;
list.append（30）;
list.print（）; //出力：10-> 20-> 30

リンクリストの種類

• 単独でリンクされたリスト：各ノードは次のノードのみを指します。
• 二重リンクリスト：各ノードには、次のノードと前のノードの両方へのポインターがあります。
• 循環リンクリスト：最後のノードは、最初のノード（またはヘッド）をポイントし、ループを形成します。

リンクリストを使用する理由

ArrayはJavaScriptでより一般的ですが、リンクリストは特定のシナリオで役立ちます。

• 頻繁に挿入と削除（特に最初または中間）が必要な場合、配列のような再インデックスを必要としないためです。
• メモリを再割り当てする必要なく動的に成長することができます。
• それらは、スタック、キュー、ツリーなどのより複雑なデータ構造を理解するための基礎です。

トレードオフ

• 長所：
  • スタートまたは中央での効率的な挿入/削除（ノードへの参照がある場合はO（1））。
  • 動的サイズ - スペースを事前に割り当てる必要はありません。
• 短所：
  • ランダムアクセスはありません - 特定のインデックス（O（n））に到達するには、頭から横断する必要があります。
  • 追加のメモリは、参照（ nextポインター）の保存に使用されます。
  • 非連続メモリによる配列と比較したキャッシュ性能が低い。

まとめ

JavaScriptのリンクリストは、オブジェクト参照を介してリンクされたノードで作られた手動で実装されたデータ構造です。 JavaScriptの最適化されたアレイメソッドのために、一般的に配列とは一般的に使用されていませんが、リンクリストを理解することは、特に技術的なインタビューでは、アルゴリズムの設計と問題解決に役立ちます。

基本的に、それぞれが次のオブジェクトを指しているオブジェクトのチェーンです。概念のシンプルで、実際には強力です。

以上がJavaScriptのリンクリストとは何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。