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

この記事では、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所指的地址）

    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 サイトの他の関連記事を参照してください。