JavaScriptを使用したデータ構造：単独でリンクされたリストと二重リンクリスト

この記事では、コンピューターサイエンスにおける2つの基本的なデータ構造、単独で二重にリンクされたリストについて説明します。しばしば誤解されていますが、これらの構造は、親しみやすい類推で最もよく理解されています：スカベンジャーハント。

単独でリンクされたリストを理解する

単独でリンクされたリストは、相互接続されたノードのシーケンスです。各ノードは、シーケンスの次のノードを参照するデータとポインターを保持します。これはスカベンジャーハントを反映しています。各手がかり（ノード）には、次の手がかりにつながるメッセージ（データ）と指示（ポインター）が含まれています。手がかりのシーケンス全体が完全な狩りを形成します。

単独でリンクされたリスト操作

NodeとSinglyList （または、この場合はDoublyList ）コンストラクターの両方の操作を調べます。

• ノード：データを含む基本的なビルディングブロック。
• DoublyList：
  • _length ：ノードの数を追跡します。
  • head ：最初のノードを指します。
  • tail ：最後のノードを指します（単独でリンクされたリストとの重要な違い）。
  • add(value) ：新しいノードを追加します。
  • searchNodeAt(position) ：特定のインデックスでノードを見つけます。
  • remove(position) ：特定のインデックスでノードを削除します。

二重にリンクされたリストの実装

JavaScriptにDoublyListを実装しましょう。

まず、 Nodeコンストラクター：

クラスノード{
  Constructor（value）{
    this.data = value;
    this.previous = null; //前のノードへのポインター
    this.next = null; //次のノードへのポインター
  }
}

DoublyListコンストラクター：

クラスdoublyList {
  constructor（）{
    this._length = 0;
    this.head = null;
    this.tail = null;
  }
}

二重にリンクされたリストメソッド

双方向トラバーサルのために変更されたadd(value) 、 searchNodeAt(position) 、およびremove(position)の実装があります。

add(value) ：

 add（value）{
  const node = new Node（value）;
  if（this._length）{
    this.tail.next = node;
    node.previous = this.tail;
    this.tail = node;
  } それ以外 {
    this.head = node;
    this.tail = node;
  }
  this._length;
  ノードを返す;
}

searchNodeAt(position) ：（単独でリンクされたリストバージョンと同じ）

 SearchNodeat（position）{
  // ...（実装は同じままです）...
}

remove(position) ：

削除（位置）{
  // ...（実装はより複雑で、4つのケースの処理：無効な位置、頭の削除、尾の取り外し、中間ノードの削除。詳細な実装については、元の記事を参照してください。）...
}

結論

この記事は、スカベンジャーハントの類推を使用して、単独で二重にリンクされたリストの明確な説明を提供しました。提供されたJavaScriptコードは、二重にリンクされたリストの実装を実証し、単独でリンクされたリストと比較して重要な違いと複雑さを強調しています。あなたの理解を固めるために、コードを試してみてください。

以上がJavaScriptを使用したデータ構造：単独でリンクされたリストと二重リンクリストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。