「アルゴリズムとデータ構造」JavaScript のリンク リスト

「アルゴリズムとデータ構造」JavaScript のリンク リスト

[[378875]]

この記事はWeChatの公開アカウント「Unorthodox Front-end」から転載したもので、著者はisboyjcです。この記事を転載する場合は、不適切なフロントエンド公開アカウントにご連絡ください。

序文

この記事では、まずリンク リストとは何か、JavaScript でどのように機能するかについて説明します。次に、JavaScript を使用してさまざまなリンク リストの設計を実装します。最後に、よくある質問をいくつか取り上げ、さまざまな側面から回答します。つまり、リンク リストを完全にマスターすることが目的です。

概念を理解したら、リンクリストの分類に進み、難易度に応じて完了することができます。リンクリストの問題は比較的簡単です。この記事のリンクリストの設計を読んでいれば、少なくとも20問は簡単に終わらせることができます。同時に、リンクリストの問題の数は比較的少なく、合計で約50問ですが、メンバーシップが必要な問題が10問あります。つまり、40問を終えると、リンクリストのデータ構造を予備的に習得できます。問題の順序がわからなければ、私のGitHubアルゴリズムウェアハウスライブラリで問題を順番に練習することができます。問題や概念がわからない場合は、私が書いた解決策を読むことができます。同時に、ビデオも録画しました。記事の最後にリンクがあります。それでは、リンクリストの学習を始めましょう。GO！

リンクリストとは何か

通常、プログラムには複数の要素を格納したいものです。配列は最もよく使用されるデータ構造かもしれません。配列は非常に便利なデータ構造です。配列は、[] 構文を使用して非常に簡単な方法で要素にアクセスすることもできます。

リンク リストも順序付けられた要素のセットを格納しますが、配列とは異なり、リンク リスト内の要素はメモリ内で連続していません。各要素は、要素自体を格納するノードと、次の要素への参照 (ポインタとも呼ばれます) で構成されます。

配列データ構造を見てみましょう。ほとんどの言語では配列のサイズが固定されているという欠点があります。次の図に示すように、配列の先頭または途中に項目を挿入したり削除したりするには、要素を移動する必要があるため、非常にコストがかかります。

上の図では、配列からインデックス 2 と値 3 の要素を削除します。したがって、最初に要素 3 を削除する必要があります。インデックス 2 と値 3 の要素を削除すると、インデックス 2 は空になるためです。したがって、次に、インデックス 3 (要素 4) を 1 つ前方に移動する必要があります。同時に、次の要素 5 も 1 つ前方に移動する必要があります。配列に要素を挿入する場合も同様です。配列の位置が 1 つ少ないか 1 つ多い限り、次の要素を順番に 1 つ前方または後方に移動する必要があります。したがって、配列の長さが非常に大きい場合、挿入と削除の効率が徐々に低下することが考えられます。

リンクリストをもう一度見てみましょう

要素 3 を削除するには、値 3 のノードを反復処理し、ノード 2 をノード 4 にポイントするだけです。ノード 3 は参照関係がないため、ガベージ コレクション メカニズムによってガベージ コレクションされます。ノードが多数ある場合でも、参照関係を変更するだけで要素を削除できます。要素を挿入するには、その逆を行う必要があります。つまり、挿入位置の両側の要素を切断し、前の要素が挿入された要素を指し、挿入された要素が次の要素を指すようにします。要素の数が多いほど、配列の効率が高くなります。

従来の配列と比較すると、リンク リストの利点の 1 つは、要素を追加または削除するときに他の要素を移動する必要がないことです。ただし、配列では任意の位置の任意の要素に直接アクセスできますが、リンク リストではこれは不可能です。リンク リスト内の各ノードは次のノードへの参照のみを持っているためです。そのため、リンク リストの途中の要素にアクセスする場合は、開始点 (リンク リストのヘッド ノード) から必要な要素が見つかるまでリンク リストを反復処理する必要があります。この点に注意する必要があります。

JavaScript のリンクリスト

上記で通常のリンク リストの概念を簡単に紹介しましたが、JavaScript でリンク リストをどのように表現するのでしょうか。

JS には組み込みの連結リストデータ構造がないため、オブジェクトを使用して連結リストをシミュレートする必要があります。上で紹介した連結リストは、実際には一方向の連結リストです。また、双方向の連結リストや循環連結リストなども存在します。これらを一つずつ紹介し、JavaScript を使用して実装していきます。

単連結リスト

まず、基本的なシングルネックレスリストを見てみましょう。一方向リンクリストの各要素は、以下に示すように、要素自体を格納するノードと次の要素へのポインタで構成されています。

リンク リストのデータ構造を実現するには、ヘッド要素 (リンク リストの先頭要素) と各要素の次のポインターを保存することが重要です。この 2 つの部分を使用すると、リンク リストを簡単にトラバースしてすべての要素を操作できます。リンク リストを鉄の鎖として想像できます。鉄の鎖の各ノードは互いに接続されています。鉄の鎖の先頭を見つけることができれば、鉄の鎖全体を見つけることができます。では、JS で一方向リンク リストをシミュレートするにはどうすればよいでしょうか。ステップごとに実行してみましょう。

まず、クラスを作成する必要があります。このクラスの機能は、リンクリストのノードを記述することです。これは非常にシンプルで、必要なのは2つの属性だけです。1つはこのノードの値を保存するためのもので、もう1つは次のノードへのポインタを保存するためのものです。

  1.  /**
  2.  * @description: リンクテーブルノードクラスを作成する
  3.  * @param {*} val ノード値
  4.  * @戻る{*}
  5.  */
  6. 関数ListNode(val) {
  7.   this.val = val
  8.   this.next = null  
  9.  }

次に、リンク リスト クラスを記述する必要があります。ここで、length 属性はリンク リストの長さを表し、head 属性はリンク リストのヘッド ノードを表します。

  1.  /**
  2.  * @description: リンクリストクラスを作成する
  3.  * @パラメータ {*}
  4.  * @戻る{*}
  5.  */
  6. 関数LinkedList() {
  7.   この長さ = 0
  8.   this.head = null  
  9.  }

考えてみましょう。リンク リスト クラスをシミュレートしているので、このクラスにすべての可能な機能を入れる必要があります。たとえば、配列には push/splice/indexOf/... などの便利なメソッドがあり、リンク リストにもこれらが必要です。リンク リストに追加する実用的な機能やメソッドを慎重に検討し、まず基本的な骨組みを構築しましょう。ここにはそれらの多くをリストしました。1 つずつ実装してみましょう。追加してもかまいません。

  1.  // リンクリストにノードを追加する
  2. LinkedList.prototype.append =関数(val) { } 
  3.  
  4.  //リンクリストの指定された位置にノードを挿入します
  5. LinkedList.prototype.insert =関数(インデックス, val ) { } 
  6.  
  7.  // リンクリスト内の指定された位置にある要素を削除し、この要素の値を返します
  8. LinkedList.prototype.removeAt =関数(インデックス) { } 
  9.  
  10.  // リンクリスト内の対応する要素を削除します
  11. LinkedList.prototype.remove =関数(val) { } 
  12.  
  13.  // リンクリスト内の指定された要素のインデックスを取得します
  14. LinkedList.prototype.indexOf =関数(val) { } 
  15.  
  16.  // リンクリスト内のノードを取得する
  17. LinkedList.prototype.find =関数(val) { } 
  18.  
  19.  // リンクリスト内のインデックスに対応する要素を取得します
  20. LinkedList.prototype.getElementAt =関数(インデックス) { } 
  21.  
  22.  // リンクリストが空かどうか確認する
  23. LinkedList.prototype.isEmpty =関数() { } 
  24.  
  25.  // リンクリストの長さを取得する
  26. LinkedList.prototype.size =関数() { } 
  27.  
  28.  // リンクリストの先頭要素を取得する
  29. LinkedList.prototype.getHead =関数() { } 
  30.  
  31.  // リンクリストをクリアする
  32. LinkedList.prototype.clear =関数() { } 
  33.  
  34.  //リンクリストをシリアル化する
  35. LinkedList.prototype.join =関数(文字列) { }

getElementAt(インデックス)

まず、リンク リスト内のインデックスに対応する要素を取得する getElementAt メソッドと、ノード値を通じてリンク リストの要素を取得する find メソッドを実装しましょう。これらは後で何度も使用するため、まず getElementAt メソッドについて説明します。上で、要素を検索する場合は最初から反復処理する必要があると述べましたが、渡されたインデックスに従って反復処理するだけで済みます。

まず、パラメータ インデックスの境界値を決定します。値がインデックスの範囲を超える場合 (0 未満または length - 1 より大きい)、null を返します。リンク リストのヘッド ノードから開始し、対応するインデックス位置のノードが見つかるまでリンク リスト全体をトラバースしてから、このノードを返します。簡単ではありませんか? すべての順序付きデータ セットと同様に、リンク リストのインデックスも 0 から始まります。リンク リストのヘッド ノードがある限り、トラバースしてインデックス位置の要素を見つけることができます。そのため、コンストラクター、つまり LinkedList クラスにヘッド値を保存します。

  1.  // リンクリスト内のインデックスに対応する要素を取得します
  2. LinkedList.prototype.getElementAt =関数(インデックス) {
  3.   if (インデックス< 0 ||インデックス>= this.length)戻り値 ヌル  
  4.  
  5.   cur = this.head とします。
  6.   while (インデックス--) {  
  7.     cur = cur.next  
  8.   }
  9. 戻る​
  10. }

find(値)

find メソッドは getElementAt メソッドに似ています。1 つはインデックスで要素を検索し、もう 1 つはノード値で要素を検索するので、反復して比較するだけです。

  1.  // リンクリスト内のノードを取得する
  2. LinkedList.prototype.find =関数(val) {
  3.   cur = this.head とします。
  4.   （現在）{
  5.     (cur.val == val) の場合、 curを返す
  6.     cur = cur.next  
  7.   }
  8. 戻る ヌル 
  9.  }

追加(値)

getElementAt メソッドを使用すると、リンク リストの末尾に要素を追加するために使用される append メソッドを簡単に実装できます。

このメソッドは値を渡します。上記の ListNode コンストラクターを使用して新しいノードを作成できます。

次に、リンク リストのヘッドが null の場合、リンク リストが空であることを意味するため、ヘッド ノードを新しく追加された要素にポイントして、ヘッド ノードが格納されていることを確認する必要があります。空でない場合は、getElementAt メソッドを使用して、リンク リストの最後のノードを検索します。最後のノードのインデックスは、コンストラクターに格納されているリンク リストの長さ属性から 1 を引いた値であり、最後のノードの次のポインターを新しく追加された要素にポイントします。

新しく追加された要素の次のポインタはデフォルトでnullになり、リンクリストの最後の要素の次の値もnullになります。さらに、リンクリストにノードを掛けた後、長さ属性がリンクリストの長さと等しくなるように、リンクリストの長さに1を加算する必要があります。

  1.  // リンクリストにノードを追加する
  2. LinkedList.prototype.append =関数(val) {
  3.   ノード = 新しいListNode(val) 
  4.  
  5.   if (!this.head) {
  6.     this.head = ノード
  7.   }それ以外{
  8.     cur = this.getElementAt(this.length - 1) とします。
  9.     cur.next = ノード
  10.   }
  11.   this.length++
  12.  }

挿入(インデックス、値)

次に、リンク リスト内の任意の位置にノードを追加する挿入メソッドを実装する必要があります。

指定された位置に要素を挿入するには、まず渡されたインデックスが範囲外であるかどうかを判断する必要があります。

次に、2つの状況を考えてみましょう

インデックスの値が0の場合、リンクリストの先頭に新しいノードが挿入されることを意味します。新しく挿入されたノードの次のポインタは現在の先頭を指し、次の図に示すように、先頭の値は新しく挿入されたノードに更新されます。

インデックスの値が 0 でない場合、つまり挿入されたノードがリンク リストの中央または末尾にある場合、まず挿入する位置の前のノード prevNode を見つけ、次に新しいノード newNode の次のポインタを prevNode の次のノードに対応するノードにポイントし、次に prevNode の次のポインタを newNode にポイントして、新しいノードをリンク リストに挿入します。この方法は、次の図に示すように、挿入されたノードがリンク リストの末尾にある場合にも適用できます。

最後に、ノードを挿入し、リンクリストの長さを1増やす必要があります。コードは次のとおりです。

  1.  //リンクリストの指定された位置にノードを挿入します
  2. LinkedList.prototype.insert =関数(インデックス, val ) {
  3.   if (インデックス< 0 ||インデックス> this.length)戻り値 間違い  
  4.  
  5.   ノード = 新しいListNode(val) 
  6.  
  7.   if (インデックス=== 0 ) {
  8.     ノード.next = this.head
  9.     this.head = ノード
  10.   }それ以外{
  11.     prev = this.getElementAt(インデックス- 1 )とします。
  12.     ノード.next =前へ.次へ 
  13.     前へ.次へ= ノード
  14.   } 
  15.  
  16.   this.length++
  17. 戻る 真実 
  18.  }

削除(インデックス)

同様に、リンク リスト内の指定された位置にあるノードを削除する removeAt メソッドを簡単に記述できます。

それでも、まず渡されたインデックスが境界を超えているかどうかを判断します。

2つの状況がある

削除するノードがリンクリストの先頭である場合は、先頭を次のノードに移動するだけです。現在のリンクリストにノードが 1 つしかない場合、次のノードは null です。このとき、先頭を次のノードに向けることは、先頭を null に設定することと同じです。削除後、リンクリストは空になります。

削除するノードがリンク リストの途中にある場合は、インデックス位置にある前のノードを見つけて、その次のポインタをインデックス位置にある次のノードにポイントする必要があります。つまり、ノードを削除するには、対応するノードのポインタを変更し、削除された位置に隣接するノードを切断してから再接続するだけで済みます。

画像-20201227180444604

削除されたノードには参照関係がないため、JavaScript のガベージ コレクション メカニズムがそれを処理します。ガベージ コレクション メカニズムもこの記事の範囲外です。ノード要素を削除するには、リンク リストの長さを 1 減らす必要があることに注意してください。最終的なコードは次のとおりです。

  1.  // リンクリスト内の指定された位置にある要素を削除し、この要素の値を返します
  2. LinkedList.prototype.removeAt =関数(インデックス) {
  3.   if (インデックス< 0 ||インデックス>= this.length)戻り値 ヌル  
  4.  
  5.   cur = this.head とします。 
  6.  
  7.   if (インデックス=== 0 ) {
  8.     this.head = cur.next  
  9.   }それ以外{
  10.     prev = this.getElementAt(インデックス- 1 )とします。
  11.     cur =前へ.次へ 
  12.     前へ 次へ=次へ 
  13.   } 
  14.  
  15.   this.length --  
  16.  cur.valを返す
  17. }

インデックスOf(値)

リンク リスト内の特定の要素のインデックスを取得します。これは比較的簡単です。直接反復するだけです。一致するものが見つかった場合は、対応するインデックスが返されます。一致するものが見つからない場合は、-1 が返されます。

  1.  // リンクリスト内の指定された要素のインデックスを取得します
  2. LinkedList.prototype.indexOf =関数(val) {
  3.   cur = this.head とします。 
  4.  
  5.  ( i = 0 とします; i < this.length; i++) {
  6.     (cur.val === val)の場合、 iを返す
  7.     cur = cur.next  
  8.   } 
  9.  
  10.  -1を返す
  11. }

削除(値)

リンクリスト内の対応する要素を削除します。前の準備があれば、ここでは比較的簡単です。indexOf メソッドを使用して対応するインデックスを直接取得し、removeAt メソッドを使用してノードを削除できます。

  1.  // リンクリスト内の対応する要素を削除します
  2. LinkedList.prototype.remove =関数(val) {
  3.   インデックス= this.indexOf(val)とします。
  4.  this.removeAt(インデックス)を返します
  5. }

空です()

リンク リストが空かどうかを判断するには、リンク リストの長さが 0 に等しいかどうかを判断するだけです。

  1.  // リンクリストが空かどうか確認する
  2. LinkedList.prototype.isEmpty =関数() {
  3.  !this.lengthを返す
  4. }

サイズ（）

リンクリストの長さを取得するには、その長さを取得するだけです

  1. // リンクリストの長さを取得する
  2. LinkedList.prototype.size =関数() {
  3.  this.lengthを返す
  4. }

getHead()

リンクリストの先頭要素を取得するには、head属性を返すだけです。

  1.  // リンクリストの先頭要素を取得する
  2. LinkedList.prototype.getHead =関数() {
  3.  this.headを返す
  4. }

クリア（）

リンク リストをクリアするには、ヘッドを 0 に設定し、長さを 0 に設定して、ガベージ コレクション メカニズムが参照されていない放棄されたリンク リストをリサイクルするのを待つだけです。

  1.  // リンクリストをクリアする
  2. LinkedList.prototype.clear =関数() {
  3.   this.head = null  
  4.   この長さ = 0
  5.  }

結合(文字列)

リンク リストをシリアル化するということは、配列の join メソッドと同様に、指定された形式でリンク リストを出力することを意味します。これは、テストを容易にすることを目的としています。

  1.  //リンクリストをシリアル化する
  2. LinkedList.prototype.join =関数(文字列) {
  3.   cur = this.head とします。
  4.   str = ''とする 
  5.   （現在）{
  6.     str += カーソル値
  7.  
  8.     if ( cur.next ) str += 文字列
  9.  
  10.     cur = cur.next  
  11.   }
  12. 文字列を返す
  13. }

ここまでで、一方向リンクリストクラスが設計されました。テストしてみましょう。テスト用に次のコードを入力します。

  1. リンクリストを新しいリンクリスト（）にします
  2. リンクリストに追加(10)
  3. リンクリストに追加(20)
  4. リンクリストに追加(30) 
  5.  
  6.  console.log( linkedList.join ( "--" )) 
  7.  
  8. リンクリストを挿入(0, 5)
  9. リンクリストの挿入(2, 15)
  10. リンクリストを挿入(4, 25)
  11.  console.log( linkedList.join ( "--" )) 
  12.  
  13. コンソールログ(linkedList.removeAt(0))
  14. コンソールログ(linkedList.removeAt(1))
  15. コンソールログ(linkedList.removeAt(2))
  16.  console.log( linkedList.join ( "--" )) 
  17.  
  18. コンソールログ(linkedList.indexOf(20)) 
  19.  
  20. リンクリストを削除(20) 
  21.  
  22.  console.log( linkedList.join ( "--" )) 
  23.  
  24. コンソール.log(linkedList.find(10)) 
  25.  
  26. リンクリストをクリアする()
  27.  console.log(リンクリスト.size ())

最終的な出力は次のようになります

  1. // 10 --20--30  
  2.  // 5 --10--15--20--25--30  
  3.  // 5
  4.  // 15
  5.  // 25
  6.  // 10 --20--30  
  7.  // 1
  8.  // 10 --30  
  9.  // リストノード { val: 10, next : リストノード { val: 30, next : null } }
  10.  // 0

上記のコードにはパラメータチェックが欠けている部分もありますが、学習するには十分です。完成したコードの最後にリンクが添付されています。

二重リンクリスト

上では一方向リンクリストについて説明しました。次に、双方向リンクリストについて説明しましょう。では、双方向リンクリストとは何でしょうか? 実際、名前からわかるとおりです。一方向リンクリストの各要素には、次のノードを指すために使用される次のポインタが 1 つだけあります。リンクリスト全体をトラバースできるのは、リンクリストの先頭からのみです。どのノードも、次のノードしか見つけることができず、前のノードを見つけることはできません。双方向リンクリストの各要素には、次のノード用と前のノード用の 2 つのポインタがあります。双方向リンクリストでは、一方向リンクリストのように先頭からトラバースするだけでなく、以下に示すように末尾からもトラバースできます。

一方向リンクリストと同様に、最初にリンクリストノードクラスを作成します。違いは、前のノードを指すために追加のprev属性が必要であることです。

  1.  /**
  2.  * @description: 双方向リンクテーブルノードクラスを作成する
  3.  * @param {*} val ノード値
  4.  * @戻る{*}
  5.  */
  6. 関数ListNode(val) {
  7.   this.val = val
  8.   this.next = null  
  9.   this.prev = null  
  10.  }

双方向リンク リストは、末尾ノードが追加された単方向リンク リストに似ています。

  1.  /**
  2.  * @description: 二重リンクリストクラスを作成する
  3.  * @パラメータ {*}
  4.  * @戻る{*}
  5.  */
  6. 関数DoubleLinkedList() {
  7.   この長さ = 0
  8.   this.head = null  
  9.   this.tail = null  
  10.  }

次に、二重連結リストのプロトタイプメソッドを実装しましょう。

getElementAt(インデックス)

まず最初に、二重リンク リスト内のインデックスに対応する要素を取得します。二重リンク リストは両方向に反復処理できるため、ここで getElementAt メソッドを最適化できます。インデックスがリンク リストの長さ (length/2) より大きい場合は後ろから前へ検索し、そうでない場合は前から後ろへ検索して、ノード要素をより速く見つけることができます。

  1.  // 二重リンクリスト内のインデックスに対応する要素を取得します
  2. DoubleLinkedList.prototype.getElementAt =関数(インデックス) {
  3.   if (インデックス< 0 ||インデックス>= this.length)戻り値 ヌル  
  4.   
  5.   cur = nullとする 
  6.   if(インデックス> Math.floor(this.length / 2)){
  7.     // 後ろから前へ
  8.     cur = this.tail
  9.     i = this.length - 1 とします。
  10.     i >インデックスの場合
  11.       cur = cur.prev
  12.       私  -  
  13.     }
  14.   }それ以外{
  15.     // 前から後ろへ
  16.     cur = this.head
  17.     while (インデックス--) {  
  18.       cur = cur.next  
  19.     }
  20.   }
  21. 戻る​
  22. }

find(値)

find メソッドは getElementAt メソッドと似ています。getElementAt メソッドは最適化できるので、find も双方向リンクリストになった後に最適化できます。双方向に反復できるので、両側を同時に反復した方が速いのではないでしょうか。双方向反復の場合は、見つからない場合にのみリンクリスト全体を反復するので、より効率的です。

  1.  // 二重リンクリスト内のノードを取得する
  2. DoubleLinkedList.prototype.find =関数(val) {
  3.  curHead = this.head とします。
  4.   curTail = this.tail とします。
  5.   (curHead) の間 {
  6.     if (curHead.val == val) の場合、 curHead を返す
  7.     curHead = curHead.next   
  8.  
  9.     if (curTail.val == val) の場合、 curTailを返す
  10.     curTail = curTail.prev
  11.   }
  12. 戻る ヌル 
  13.  }

追加(値)

次に、追加のノード要素について説明します。双方向リンク リストの追加と一方向リンク リストの追加にはいくつかの違いがあります。

リンク リストが空の場合、ヘッドが現在追加されているノードを指すだけでなく、テールも現在追加されているノードを指す必要があります。

リンク リストが空でない場合は、現在追加するノードに tail の next を直接ポイントし、次にノードの prev を古い tail を指すように変更し、最後に tail を新しく追加されたノードに変更します。

二重リンクリストに追加する場合、最初からリンクリスト全体をトラバースする必要はありません。tail を介してリンクリストの末尾を直接見つけることができます。これは、単方向リンクリストの操作よりも便利です。最後に、長さの値に 1 を追加して、リンクリストの長さを変更します。

  1.  // 二重リンクリストにノードを追加します
  2. DoubleLinkedList.prototype.append =関数(val) {
  3.   ノード = 新しいListNode(val) 
  4.  
  5.   this.head がnullの場合
  6.     // リンクリストは空で、先頭と末尾の両方が現在追加されているノードを指しています
  7.     this.head = ノード
  8.     this.tail = ノード
  9.   }
  10. それ以外{
  11.     // リンクリストが空でない場合は、現在のノードをリンクリストの末尾に追加します
  12.     this.tail.next = ノード
  13.     ノード.prev = this.tail
  14.     this.tail = ノード
  15.   } 
  16.  
  17.   this.length++
  18.  }

挿入(インデックス、値)

次はノード要素を挿入する方法です。考え方は同じで難しくありません。tail ポインタと prev ポインタに注目し、個別に説明します。挿入後、長さが 1 増加します。

  1.  // 二重リンクリストの指定された位置にノードを挿入します
  2. DoubleLinkedList.prototype.insert =関数(インデックス, val ) {
  3.   if (インデックス< 0 ||インデックス> this.length)戻り値 間違い  
  4.  
  5.   // 末尾に挿入
  6.   if (インデックス=== this.length ) {
  7.     this.append(val)
  8.   }それ以外{
  9.     ノード = 新しいListNode(val) 
  10.  
  11.     if ( index === 0) { // 先頭に挿入
  12.       this.head がnullの場合
  13.         this.head = ノード
  14.         this.tail = ノード
  15.       }それ以外{
  16.         ノード.next = this.head
  17.         this.head.prev = ノード
  18.         this.head = ノード
  19.       }
  20.     } else { // 中央の位置に挿入
  21.       curNode = this.getElementAt(インデックス)とします。
  22.       prevNode = curNode.prev とします。
  23.       ノード.next = curNode
  24.       node.prev = 前のノード
  25.       prevNode.next = ノード
  26.       curNode.prev = ノード
  27.     }
  28.     this.length++
  29.   }
  30. 戻る 真実 
  31.  }

削除(インデックス)

二重リンクリスト内の指定された位置にある要素を削除します。また、末尾と前のポインターにも注意してください。最後に、削除後の長さは 1 減少します。

  1.  // 二重リンクリスト内の指定された位置にある要素を削除し、この要素の値を返します
  2. DoubleLinkedList.prototype.removeAt =関数(インデックス) {
  3.   if (インデックス< 0 ||インデックス>= this.length)戻り値 ヌル  
  4.  
  5.   現在の値を this.head にします。
  6.   前のノード
  7.  
  8.   if ( index === 0) { // ヘッダー要素を削除する
  9.     this.head =現在の.次の 
  10.     this.head.prev = null  
  11.     this.length === 1 の場合、 this.tail = null  
  12.   } else if ( index === this.length - 1) { // 最後の要素を削除する
  13. 現在の= this.tail
  14.     this.tail =現在の.前の
  15.     this.tail.next = null  
  16.   } else { // 中央の要素を削除する
  17. 現在の= this.getElementAt(インデックス)
  18.     prevNode =現在の.prev
  19.     prevNode.next = current.next  
  20. 現在の.次の. 前 = prevNode
  21.   } 
  22.  
  23.   this.length --  
  24. 戻る 現在の.val
  25.  }

インデックスOf(値)

二重リンクリスト内の要素のインデックスを見つけるのは、上記の find メソッドを使用すると簡単です。考え方は同じです。

  1.  // 二重リンクリスト内の指定された要素のインデックスを取得します
  2. DoubleLinkedList.prototype.indexOf =関数(val) {
  3.   curHead = this.head とします。
  4.   curTail = this.tail とします。
  5.   idx = 0 とする
  6.   (curHead !== curTail) の間 {
  7.     if (curHead.val == val) idxを返す
  8.     curHead = curHead.next   
  9.  
  10.     if (curTail.val == val) の場合、this.length - 1 - idxを返します。
  11.     curTail = curTail.prev 
  12.  
  13.     idx++
  14.   }
  15.  -1を返す
  16. }

結合文字列)

シリアル化されたリンク リストは、上記の一方向リンク リストと一致しています。

  1.  // 二重リンクリストをシリアル化する
  2. DoubleLinkedList.prototype.join =関数(文字列) {
  3.   cur = this.head とします。
  4.   str = ''とする 
  5.   （現在）{
  6.     str += カーソル値
  7.  
  8.     if ( cur.next ) str += 文字列
  9.  
  10.     cur = cur.next  
  11.   }
  12. 文字列を返す
  13. }

双方向リンク リストについて説明すべきことは以上です。残りのメソッドは比較的単純なので、詳細には触れません。完全なコードは、この記事の最後にある双方向リンク リストの例にあります。

同様に、

  1.  doubleLinkedList = 新しい DoubleLinkedList() を作成します。
  2. ダブルリンクリスト.append(10)
  3. ダブルリンクリスト.append(15)
  4. ダブルリンクリスト.append(20)
  5. ダブルリンクリスト.append(25)
  6.  console.log( doubleLinkedList.join ( "<->" )) 
  7.  
  8. コンソールログ(doubleLinkedList.getElementAt(0).val)
  9. コンソールログ(doubleLinkedList.getElementAt(1).val)
  10. コンソールログ(doubleLinkedList.getElementAt(5)) 
  11.  
  12.  console.log( doubleLinkedList.join ( "<->" ))
  13. コンソールログ(doubleLinkedList.indexOf(10))
  14. コンソールログ(doubleLinkedList.indexOf(25))
  15. コンソールログ(doubleLinkedList.indexOf(50)) 
  16.  
  17. ダブルリンクリストを挿入 (0, 5)
  18. ダブルリンクリスト挿入(3, 18)
  19. ダブルリンクリストを挿入(6, 30)
  20.  console.log( doubleLinkedList.join ( "<->" )) 
  21.  
  22. コンソールログ(doubleLinkedList.find(10).val)
  23. コンソールログ(doubleLinkedList.removeAt(0))
  24. コンソールログ(doubleLinkedList.removeAt(1))
  25. コンソールログ(doubleLinkedList.removeAt(5))
  26. コンソールログ(doubleLinkedList.remove(10))
  27. コンソールログ(doubleLinkedList.remove(100)) 
  28.  
  29.  console.log( doubleLinkedList.join ( "<->" ))

上記のコードの出力は次のようになります

  1. // 10<->15<->20<->25
  2.  // 10
  3.  // 15
  4.  //ヌル 
  5.  // 10<->15<->20<->25
  6.  // 0
  7.  // 3
  8.  // -1
  9.  // 5<->10<->15<->18<->20<->25<->30
  10.  // 10
  11.  // 5
  12.  // 15
  13.  //ヌル 
  14.  // 10
  15.  //ヌル 
  16.  // 18<->20<->25<->30

まあ、間違いはありません。単純な比較で正しいことがわかります。問題ありません

循環リンクリスト

別の種類のリンク リストである循環リンク リストを見てみましょう。名前が示すように、循環リンク リストの末尾ノードは、自身の先頭ノードを指します。

以下に示すように、単方向循環リンクリストと双方向循環リンクリストがあります。

ここでは、単一および二重の循環リンク リストを 1 つずつ記述することはしません。自分で記述してみてください。上記の循環リンク リストと比較すると、ヘッド ノードを指す末尾ノードのみに注意する必要があります。

リンク リストが JavaScript に組み込まれていないのはなぜですか?

上で述べたことに基づくと、リンク リストには多くの利点がありますが、JavaScript 言語にはなぜリンク リストのデータ構造が組み込まれていないのでしょうか。

実は、JS では配列が連結リストのほぼすべての機能を実装しているので、わざわざ苦労する必要はありません。 これを聞くと戸惑うかもしれません。 上で、配列は状況によっては連結リストより劣る (先頭挿入など) と書いていませんでしたか?

事実を使って話してみましょう。次に、上記で完成した LinkedList クラスを使用して、ネイティブ配列で簡単な時間テストを実行してみましょう。

  1. リンクリストを新しいリンクリスト（）にします
  2. arr = [] とします
  3.  
  4.  // テスト、「合計数 100、挿入ノード 50」/「合計数 100000、挿入ノード 50000」を試してください
  5. カウントを100にする
  6. 挿入インデックスを 50 にします
  7. // count = 100000とします
  8. // insertIndex = 50000 とします
  9.  
  10.  console.time ( 'リンクリストのプッシュ操作' )
  11.  ( i = 0 とします; i < count ; i++) {
  12.   リンクリストに追加(i)
  13.  }
  14.  console.timeEnd( 'リンクリストのプッシュ操作' ) 
  15.  
  16.  console.time ( '配列プッシュ操作' )
  17.  ( i = 0 とします; i < count ; i++) {
  18.   arr.push(i)
  19.  }
  20.  console.timeEnd( '配列プッシュ操作' ) 
  21.  
  22.  
  23.  console.time ( 'リンクリスト挿入操作' )
  24.  linkedList.insert ( 'テストノード' 、 insertIndex)
  25.  console.timeEnd( 'リンクリスト挿入操作' ) 
  26.  
  27.  console.time ( '配列挿入操作' )
  28.  arr.splice(insertIndex, 0, 'テストノード' )
  29.  console.timeEnd( '配列挿入操作' ) 
  30.  
  31.  
  32.  console.time ( 'リンクリスト削除操作' )
  33.  linkedList.removeAt(挿入インデックス)
  34.  console.timeEnd( 'リンクリスト削除操作' ) 
  35.  
  36.  console.time ( '配列削除操作' )
  37.  arr.splice(挿入インデックス、1)
  38.  console.timeEnd( '配列削除操作' )

結果を見てみましょう

100個のデータを追加し、インデックス50に要素を挿入し、挿入した要素を削除します。

100,000 のデータを追加し、インデックス 50,000 に要素を挿入し、挿入した要素を削除します。

何？？？？？？

テスト結果から、カーディナリティが 100 という小さいオーダーであっても、100000 という大きいオーダーであっても、ネイティブ配列のパフォーマンスは依然としてリンク リストを圧倒していることがわかります。

つまり、リンク リストの方が配列よりも効率的であるという格言は、実際には JS には存在しません。長さが 1 億の配列と長さが 10 の別の配列を作成し、2 つの配列の中央に要素を追加した場合でも、console.time を使用すると、かかる時間は配列の長さとは関係がないことがわかります。これは、JS 配列がリンク リストの効率要件を満たしていることを示しています。

配列内の特定の位置に要素を追加したり削除したりするには、splice() メソッドを使用することもできます。テストの結果、所要時間も配列の長さに依存せず、リンク リストの要件を満たすことができました。配列の添え字は、リンク リストの head、tail、next、prev などのメソッドを完全に置き換えることができ、ほとんどの場合、より便利です。また、仕事でリンク リストを使用するシナリオはそれほど多くないため、JS の配列はリンク リストよりもはるかに優れていると言えます。

もちろん、これは JavaScript 言語に限定されています。これは、JS 内の配列実装メカニズムに関連しています。実際、JS の配列は単に配列と呼ばれています。これは、従来の言語の配列の概念とは異なります。したがって、配列の概念とその内部実装は、この章での議論の範囲外です。まずは質問を残しておきます。数日後に時間ができたら、JS 配列に関連する別の記事を書きます。実際、答えは自分で見つけるのが最善です。JS は解釈型の高級言語であると言われています。その基礎となる実装は、見た目ほど単純で従来的なものではありません。少し型破りです。

この時点で、ようやくこの記事を読み終えたのに、役に立たないと文句を言う人がいるかもしれません。 。 。心配しないで、腐った卵はそのままにしておいてください

リンクリストは JavaScript では役に立たないのでしょうか?

上で述べたように、JavaScript のリンク リストは役に立たないというのは本当でしょうか?

実はそうではありません。例えば、3つの魔法の武器の1つであるReactのFiberアーキテクチャは、リンクリストデータ構造を使用しています。

Fiber は英語で繊維化、つまり洗練を意味します。時間のかかるタスクを多くの小さな部分に分割します。各小さな部分の実行時間は短くなります。合計時間はまだ長いですが、各小さな部分が実行された後、他のタスクに実行の機会が与えられます。このようにして、唯一のスレッドが独占されることはなく、他のタスクにも実行の機会が与えられます。React の Fiber は、VDOM 更新プロセス全体を断片化します。

これまで、React の render() メソッドは、仮想 DOM がレンダリングされた後、仮想 DOM オブジェクトと実際のコンテナ DOM をマウント ノードとして受け取りました。その主な機能は、仮想 DOM を実際の DOM にレンダリングし、コンテナの下にマウントすることでした。このメソッドは更新時に再帰的です。更新プロセス中に大量のノードを更新する必要がある場合、JS メインスレッドが長時間占有され、再帰プロセス全体を中断することはできません。JS スレッドと GUI スレッドは相互に排他的であるため (JS の動作メカニズムを一度に理解するには、👉「ハードコア JS」を参照してください)、大量のノードを更新するときにインターフェイスに多少の遅延が見られる場合があります。

Fiber アーキテクチャは、実際には 2 つの問題を解決します。1 つは、ブラウザがアイドル状態のときにタスクが実行されるようにすること、もう 1 つはタスクを断片化することです。次に、Fiber について簡単に説明します。

JS には、コールバック関数を渡すことができる requestIdleCallback(callback) という実験的なメソッドがあります。コールバック関数は、deadline オブジェクトを受け取ることができます。オブジェクトの timeRemaining() メソッドを使用して、現在のブラウザのアイドル時間を取得できます。アイドル時間がある場合は、短いタスクを実行できます。時間が不十分な場合は、requestIdleCallback が続行され、ブラウザに再びアイドル時間があるときにタスクを実行できます。このようにして、ブラウザがアイドル状態のときにタスクを実行できます。

しかし、仮想DOMは、タスクを中断する場合、新しいデータ構造、つまり、リンクされたリストには、繊維のnodeにfiberのnodeに及ぶリンクリストが含まれています次のノードを簡単に見つけることができるように、タスクの実行を再開できます。

この単純な段落は、有名な繊維アーキテクチャです。

実際、通常のニーズのために、JSでリンクされたリストを使用する必要はありませんが、リンクリストには要するに、リンクされたリストに依存しています。

やっと

記事のケースの完全なコードアドレスは次のとおりです👇

シングルおよびダブルリンクリストデモ[1]

この記事では、リンクされたリストの質問を練習する前に、リンクされたリスト、データ構造の1つを紹介します。

職場では逃げるよりも、アルゴリズムを練習することができます。

Githubは、アルゴリズムの質問/テキスト/ビデオソリューションをゼロから提供して、Github Portal [2]を使用するアルゴリズムリポジトリを構築しました。

この記事のビデオバージョンについては、👉Bステーションリンク[3]にアクセスしてください

これを見て、トリプルコネクトをしてみましょう。間違いがあれば、修正してください。また、公開アカウント「Unorthodox Front-end」をフォローして、アルゴリズムグループの友達とチームを組んで、効率を高めるためにアルゴリズムを磨くことも歓迎します。

参照

[1]シングルおよびダブルリンクリストデモ：

https://github.com/isboyjc/dailyalgorithms/tree/master/demo/algorithm [2] github portal：

https://github.com/isboyjc/dailyalgorithms [3] bilibiliポータル：

https://www.bilibili.com/video/bv1av411q7wf

<<:  米国の委員会は「道徳的義務」を理由にAI兵器の開発を禁止すべきではないと勧告した。

>>:  「ソースコード解析」仮想DOMアルゴリズムの実装方法

ブログ    
ブログ    
ブログ    
ブログ    

推薦する

ロボットはサービス業界に参入できるのか？事実が教えてくれる

有名なアニメーション会社ディズニーは、近々人工知能とロボット工学の分野に参入すると発表しました。ディ...

ウルトラマンが解雇されるのは今回が初めてではない！ YCを去った人物は「創設者から去るように言われた」

ウルトラマンニウフルが「追い出される」のは初めてではないでしょうか？ ? ！予想外にも、OpenAI...

汎用人工知能 (AGI) までどれくらい遠いのでしょうか?

人工知能 (AI) は、今日のテクノロジーにおいて最も注目され、最も影響力のあるトピックの 1 つで...

ステッカーでAIから見えなくなったら、AIにとんでもないバグが発生した

研究により、印刷されたステッカーだけで AI システムを「騙す」ことができ、検出システムが目の前にい...

テンセントが論文を提出しました！とても誇りに思う

執筆者 | Mo Yan & Yun Zhao 「国家チーム」テンセント渾源モデルがついに本...

2024年の世界モデルによって自動運転ラベリング業界は混乱するでしょうか？

この記事は、Heart of Autonomous Driving の公開アカウントから許可を得て転...

ソフトウェア開発は最終的に時代遅れになるのでしょうか?

[[283217]] [51CTO.com クイック翻訳] 著名なベンチャーキャピタリスト、マーク...

マイクロソフト、物議を醸す顔認識機能を廃止へ

マイクロソフトは、動画や写真から対象者の感情を識別できると主張するツールを含む、人工知能による顔分析...

AIが銀行業務をどう変えるか

今日、人工知能 (AI) は多くの業界に多くの資産と利点をもたらし、チャットボットから Siri や...

...

MoEトレーニングの効率とパフォーマンスのボトルネックを打破し、Huawei Panguの新しいスパース大規模モデルアーキテクチャLocMoEがリリースされました

2023年12月、初のオープンソースMoE大規模モデルMixtral 8×7Bがリリースされました。...

2020年に人工知能を変える8つのトレンド

人工知能は長い間、架空の物語、SF、さらには映画にも登場してきました。人々の目には、これは技術的な魔...

Yann LeCun 氏は衝撃的な発言をしました。「ディープラーニングは死んだ、微分可能プログラミング万歳！」

ディープラーニングの分野で最も有名な学者の一人であるヤン・ルカン氏が本日、自身のFacebookに投...

マスク氏の Grok 大型モデルがプレイ可能になりました!彼の口は彼自身と同じくらい悪い。

友達に大きなサプライズ！マスク氏は突然、Grokの大型モデルを大量の有料ユーザーに開放すると発表した...

認知AIの台頭：2025年にAIは質的に飛躍する

[[441939]] AIの概念が初めて提唱されたのは1956年なので、60年以上の歴史があります。...