コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > ウェブフロントエンド > jsチュートリアル > 本文

JavaScript のリンク リストの詳細な紹介

不言
リリース： 2019-01-02 09:58:23
転載
5942 人が閲覧しました

この記事では、JavaScript のリンク リストについて詳しく説明します。必要な方は参考にしていただければ幸いです。

リンクされたリストと配列

誰もが js で配列を使用したことがあります。配列は、実際には一連のアドレスを使用する線形テーブルの順次記憶構造です。連続したメモリセルはデータ要素を次々に保存します。たとえば、配列を削除または挿入するときに、多数の要素を移動する必要がある場合など、その特性によっても欠点が生じます。

これは、配列の挿入操作の大まかなシミュレーションです: 

    insert(arr, index, data){
        for(let i = index + 1; i <p>上記のコードから、配列の挿入と削除は O(n) 操作であることがわかります。 。これにより、リンク リストのデータ構造は、論理的に隣接する要素が物理的な位置で隣接する必要がないため、シーケンシャル ストレージ構造の欠点がなくなり、もちろんランダム性も失われます。連続空間内の配列にアクセスする利点。 </p>#一方向リンク リスト<h3></h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="JavaScript のリンク リストの詳細な紹介"></span>#一方向リンク リストの特徴:</p><h4></h4>#1 つを使用します データ要素を格納するために任意のメモリ空間を配置します (ここでのメモリ空間は連続的または不連続な場合があります)
ログイン後にコピー

  • 各ノード (ノード) はデータ自体と後続のデータへのポインタで構成されますノードは

  • # で構成されます。リンク リスト全体へのアクセスは、最初のノードを指す先頭ポインタから開始する必要があります。

  • #最後のノードノード ポインタは null (NULL) を指しています。

  • #リンクされたリスト内のいくつかの主要な操作

ノードの作成

  • ノードの挿入

  • 検索/トラバース ノード

  • ノードの削除

  • マージ

  • #ノードの初期化

##ポインタは null を指しています

    ##ストレージ データ

  • ##

        class Node {
        constructor(key) {
            this.next = null;
            this.key = key;
        }
    }
    ログイン後にコピー
    一方向リンク リストの初期化

  • 各リンク リストには最初のノードを指すヘッド ポインタがあり、ノードがない場合は NULL を指します

    class List {
        constructor() {
            this.head = null;
        }
    }
ログイン後にコピー

Create Node
        static createNode(key) {
        return new createNode(key);
    }
    ログイン後にコピー
  • ここで説明しますが、ノードを挿入操作に直接カプセル化するのではなく、静的メソッドを公開してノードを作成しました。ロジックはより正確になります。リンク リストを作成します -> ノードを作成します -> リンク リストにノードを挿入します。データの一部をパラメータとして直接使用して挿入操作を呼び出し、挿入内にノードを作成する方法を紹介する記事がいくつかあるかもしれません。

    ノードの挿入 (ヘッド ノードへの挿入後)
    • 挿入操作では、ノードのポインターを調整するだけで済みます。

    # という 2 つの状況があります。 ##Head が存在しません 任意のノードを指します。現在挿入されているノードが最初のノードであることを示します

    ##head は新しいノードを指します

    • #新しいノードのポインタは NULL を指します

      • head はノードを指します

      • head はポイントを指します新しいノードへ

    • 新しいノードのポインタは、元のヘッドが指すノードを指します

      • #
        insert(node) {
        // 如果head有指向的节点
        if(this.head){
           node.next = this.head;
        }else {
           node.next = null;
        }
        this.head = node;
    }
    ログイン後にコピー
      ノード

      • 先頭から検索

      • ノード内のキーが検索したいキーと等しいことが判明した場合、ノードを返します。 

        find(key) {
        let node = this.head;
        while(node !== null && node.key !== key){
            node = node.next;
        }
        return node;
    }
    ログイン後にコピー

    ノードの削除
    • ここには 3 つの部分があります。この状況:

    • 削除されるノードはたまたま最初のノードは、head が指すノードです。

    head を削除するノードを指します。ノードの次のノード (node.next) を削除します。

      削除するノードは最後のノードです

        • Find 削除するノードの前のノード (prevNode) に移動します削除されました

      • #prevNode のポインタを NULL にポイントします

    • #リストの中央にある特定のノードを削除しますNodes

      • #削除するノードの前のノード (prevNode) を検索します

        • ##prevNode 内のポインタを削除する現在のノードにポイントします。このノードのノード

        delete(node) {
        // 第一种情况
        if(node === this.head){
            this.head = node.next;
            return;
        }
        
        // 查找所要删除节点的上一个节点
        let prevNode = this.head;
        while (prevNode.next !== node) {
            prevNode = prevNode.next;
        }
        
        // 第二种情况
        if(node.next === null) {
            prevNode.next = null;
        }
        
        // 第三种情况
        if(node.next) {
            prevNode.next = node.next;
        }
    }
    ログイン後にコピー
    一方向リンク リストの全体コード
  • class ListNode {
  constructor(key) {
    this.next = null;
    this.key = key;
  }
}

class List {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  // 往头部插入数据
  insert(node) {
    // 如果head后面有指向的节点
    if (this.head) {
      node.next = this.head;
    } else {
      node.next = null;
    }
    this.head = node;
    this.length++;
  }

  find(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    if (this.length === 0) {
      throw 'node is undefined';
    }

    if (node === this.head) {
      this.head = node.next;
      this.length--;
      return;
    }

    let prevNode = this.head;

    while (prevNode.next !== node) {
      prevNode = prevNode.next;
    }

    if (node.next === null) {
      prevNode.next = null;
    }
    if (node.next) {
      prevNode.next = node.next;
    }
    this.length--;
  }
}
    ログイン後にコピー

    二重リンク リスト

    • 上記の導入では、一方向リストについてはすでに理解しているので、ここで紹介する双方向リストも実際には同様です。

    上の図から、二重リンク リストと単一リンク リストの違いがはっきりとわかります。 。二重リンクリストには、前のノードを指す追加のポインターがあります。

    ノードの初期化

    前のノードへのポインタ

  • 指向后一个节点的指针

  • 节点数据

    •     class ListNode {
        this.prev = null;
        this.next = null;
        this.key = key;
    }
    ログイン後にコピー

    初始化双向链表

    • 头指针指向NULL

        class List {
        constructor(){
            this.head = null;
        }
    }
    ログイン後にコピー

    创建节点

        static createNode(key){
        return new ListNode(key);
    }
    ログイン後にコピー

    插入节点（（插入到头节点之后）

    • 看上图中head后面的第一个节点可以知道，该节点的prev指向NULL

    • 节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点

    • 如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)

    • 最后将head指向新的节点

        insert(node) {
        node.prev = null;
        node.next = this.head;
        if(this.head){
            this.head.prev = node;
        }
        this.head = node;
    }
    ログイン後にコピー

    搜索节点

    这里和单向节点一样，就直接贴代码了

      search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }
    ログイン後にコピー

    删除节点

    和之前单向链表一样，分三种情况去看：

    • 删除的是第一个节点

      • head指向所要删除节点的下一个节点

      • 下一个节点的prev指针指向所要删除节点的上一个节点

    • 删除的是中间的某个节点

      • 所要删除的前一个节点的next指向所要删除的下一个节点

      • 所要删除的下一个节点的prev指向所要删除的前一个节点

    • 删除的是最后一个节点

      • 要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）

    JavaScript のリンク リストの詳細な紹介

        delete(node) {
        const {prev,next} = node;
        delete node.prev;
        delete node.next;
        if(node === this.head){
            this.head = next;
        }
        if(next){
            next.prev = prev;
        }
        if(prev){
            prev.next = next;
        }
    }
    ログイン後にコピー

    双向链表整体代码

        class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;

    if (node === this.head) {
      this.head = next;
    }

    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}
    ログイン後にコピー

    总结

    这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。


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

    関連ラベル：
    javascript node.js データ構造
    ソース：segmentfault.com
    前の記事：nodejs設定ファイルの処理方法の紹介 次の記事：NodejsでWebサーバーを構築する方法
    このウェブサイトの声明
    この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
    著者別の最新記事
    最新の問題
    URL パラメータから取得した PHP 配列が期待どおりに動作しない カテゴリ ID を含む URL パラメータがあり、それを次のような配列として扱いたいと考えています: http://example.com?cat[]=3,9,13 PHP では、...
    から 2024-04-06 22:09:02
    0
    1
    1428
    クラスのプライベート メンバーをコンストラクター パラメーターとして設定する classFoo{#one#two#three#four#five#six#seven#eight#nine#ten#eleven#twelve#thirteen#fourteen...
    から 2024-04-06 21:48:47
    0
    1
    637
    単語と一致する正規表現 新しいジョブ名をデータベース内の既存のジョブ名と照合しようとするスクリプトがあります。 SELECTa.titleASJobTitle,j.DescriptionASMatched...
    から 2024-04-06 21:24:04
    0
    1
    606
    3 レベル階層のカスタム分類を使用して woocommerce 関連製品を選択します 「スポーツ」というカスタム分類を持つ woocommerce ストアがあります。分類には、親、子、子という 3 つのレベルがあります。たとえば、屋内スポーツ > アリーナ ス...
    から 2024-04-06 20:05:30
    0
    1
    544
    MySQL SQLクエリを使用して別のテーブルのフィールドの合計を計算する 次のようなスキーマがあります。 属性「user_id」と「username」を持つユーザーテーブルと、属性「customer_id」（user_idのFK）と「finalPrice...
    から 2024-04-06 19:39:29
    0
    1
    441
    関連トピック
    詳細>
    人気のおすすめ
    人気のチュートリアル
    詳細>
    関連するチュートリアル
    人気のおすすめ
    最新のコース
    最新のダウンロード
    詳細>
    ウェブエフェクト
    公式サイト
    サイト素材
    フロントエンドテンプレート