ホームページ >ウェブフロントエンド >jsチュートリアル >JavaScript は二重リンクリストを実装します (コード例)

JavaScript は二重リンクリストを実装します (コード例)

藏色散人
藏色散人オリジナル
2019-04-12 10:50:032045ブラウズ

この記事では、JavaScript で双方向リンク リストを実装する方法を紹介します。困っている友人のお役に立てれば幸いです。

二重リンク リストとは何ですか?

二重リンク リストでは、各ノードは前のノードと次のノードへの参照を持ちます。前後の開始ノードと終了ノードは null を指す必要があります。

JavaScript は二重リンクリストを実装します (コード例)

二重リンクリストの実装

es6 クラスを使用しています。次のコードでは、補助クラス Node を作成します。これには、prev、next の 3 つの属性データが含まれます。

class Node {

  constructor(data){
    this.data = data; // data
    this.prev = null; // 引用prev节点
    this.next = null; // 引用next节点
  }}

data: ノードに追加する必要があるデータ。

prev: 前のノードを参照します。

next: 次のノードを参照します。

メイン アルゴリズムの開始

class DoublyLinkedList{

   constructor(){
        this.head = null;
        this.tail = null;
        this.length = null;
  }}

上記のコードでは、head、tail、length の 3 つのプロパティを持つ DoublyLinkedList クラスを作成しました。

head: リストの最初のノードです。

tail: リストの最後のノード。

length: リストにはノードがいくつありますか?

これらの関数を二重リンク リストに追加しましょう

プッシュ メソッド

Push メソッドは、リンク リストの最後に新しいノードを追加するのに役立ちます。

push(data){

    const node = new Node(data);

    if(!this.head){
      this.head = node;
      this.tail = node;
    }else{
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;

    }

    this.length++;
  }

1. 上記のコードでは、まず新しい変数を宣言し、ノード コンストラクターを呼び出します。

2. this.head がない場合は、this.head と this.tail が手順 1 で作成した新しいノードになります。

3. すでにノードがある場合

新しいnode.prev属性はthis.tail

this.tail.nextとなる必要があります新しいノード

末尾を更新します。

4. 長さを 1 増やします。

pop メソッド

は、リストから最後のノードを削除するのに役立ちます。

二重リンクリストでは、tail 属性に前のノードへの参照があるため、リストから最後のノードを簡単に削除できます。

pop(){

    if(!this.head) return null

    // tail是最后一个节点,因此我们从tail中提取prev属性
    const prevNode = this.tail.prev    
    if(prevNode){
       prevNode.next = null;
       this.tail = prevNode; // 更新tail
    }else{
      // 如果prev属性为null,则表示只有一个节点
      this.head = null;
      this.tail = null;
    }
     this.length--; 
  }

1. 上記のコードでは、まず新しい変数を宣言し、tail の前の属性を保存します。

2. 前のノードが見つかった場合。

最後のノードを削除します

末尾を更新します。

3. 前のノードが空の場合は、ノード

が 1 つだけあることを意味し、this.head と this.tail は null でなければなりません。

4. 長さを 1 減らします。

insertBeginning

insertBeginning メソッドは、リストの先頭に新しいノードを挿入するのに役立ちます。

insertBeginning(data){

    // 创建新节点
    const node = new Node(data);

    // 如果没有节点
    if(!this.head) {
      this.head = node;
      this.tail = node;
    }else{
      this.head.prev = node
      node.next = this.head;
      this.head = node;
    }
    // 增加长度
    this.length++;

  }

removeFirst メソッド

removeFirst メソッドは、リンク リストから最初のノードを削除するのに役立ちます。

removeFirst(){

    if(!this.head) return null

    // 存储第二个节点
    const node = this.head.next;

    if(node){
     // 删除前一个节点
      node.prev = null
     // 更新head
      this.head = node    
      }else{
      // 只有一个节点,所以我们将head和tail更新为null
      this.head = null
      this.tail = null
    }
     this.length--;

  }

関連する推奨事項:「JavaScript チュートリアル

以上がJavaScript は二重リンクリストを実装します (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。