JavaScriptでチェーンを実現します.

6584 ワード

フロントノート javascript

1.チェーンは何ですか?
シングルチェーンテーブルは、一連のノードを表すデータ構造であり、各ノードは、チェーンテーブルの次のノードを指す.対照的に、双方向チェーンは前後の要素を指すノードを有する.
配列と違って、チェーンテーブルはチェーンテーブルの特定のインデックスへのアクセスを提供しません.したがって、チェーンテーブルの第3の要素が必要であれば、第1のノードと第2のノードにアクセスしなければならない.
チェーンの利点の一つは、固定時間にチェーンの先頭と最後から項目を追加し、削除することです.
2.ノード
チェーンは一連のノードだけです.
一つのノードには二つの情報があります.
a.チェーンテーブルの次のポインタまたは参照を指します.
b.ノードの値
私たちのノードについては、1つの値を受け入れ、上記2つの情報を持つオブジェクトを返す関数を作成する必要があります.次のノードを指すポインタとノードの値です.
3.ノードチェーン表
ノードチェーンは5つの方法を含みます.
1 push(value):チェーンの最後に値を追加します.
2 pop():イジェクトチェーンの最後の値
3 get(index):与えられた索引の値を返します.
4 delete(index):与えられた索引から項目を削除します.
5 isEmpty():チェーンテーブルが空かどうかを示すブール値を指定します.
6.printList():チェーンの生産方法ではなく、我々のチェーンを印刷して、主にデバッグに使います.
4.コンストラクタ
コンストラクタには3つの情報が必要です.
1 head:チェーンの先頭ノードへの参照
2 tail: チェーンの末尾の結点に対する参照
3 リンク表にはいくつのノードがありますか?
5.isempty
isEmpty()方法はヘルプ関数です.チェーンが空なら、trueに戻ります.

 isEmpty(){
        return this.length===0;
    }

6.print List
このユーティリティ方法は、チェーンテーブル内のノードを印刷するために使用され、デバッグ目的のみに使用されます.

printList(){
            const nodes=[];
            let current=this.head;
            while(current){
                nodes.push(current.value);
                current=current.next;
            }
            return nodes.join('->');
        }

7.Push:チェーンの最後に値を追加します.
新しい接合を追加する前に、プッシュ方法はチェーンが空かどうかを確認する必要があります.二種類を使います方法で判断する
1. isEmpty()方法はtrueに戻ります.チェーンの長さはゼロです.
2. ヘッドポインタが空です
私たちはheadを使って空かどうかを判断します.
チェーンに項目がない場合は、簡単にheadポインタとtailポインタを新しい接合点に設定してチェーンの長さを更新できます.

if(this.head===null){
            this.head=node;
            this.tail=node;
            this.length;
            return node;
        }

チェーンが空いていると言わないなら、次のような操作をしなければなりません.
1.tail.nextを新しい結点に向ける
2.tailを新しい接合点に向ける
3.チェーンの長さを更新する
以下は完全なプッシュ方法です.

 push(value){
            const node=Node(value);
            if(this.head===null){
                this.head=node;
                this.tail=node;
                this.length++;
                return node;
            }
            this.tail.next=node;
            this.tail=node;
            this.length;
        }

8 pop():イジェクトチェーンの最後の値
チェーンテーブルの最後の項目を削除する前に、私達のpop方法は以下の二つの内容を確認する必要があります.
1. チェーンが空かどうかをチェックします.
2. チェーンの中に一つだけあるかどうかを確認します.

isEmpty方法でチェーンが空かどうかを確認できます.

 if(this.isEmpty()){
      return null;
  }

チェーンの中にはノードが一つしかないとどうやって分かりますか?もしheadとtailが同じノードを指すならば、唯一のノードを削除して意外にも私達は実際にチェーンを再設定します.

 if(this.head===this.tail){
         this.head=null;
         this.tail=null;
         this.length--;
         return nodeToRemove;
     }

チェーンに複数の要素がある場合、以下の操作ができます.
チェーンテーブルにノードがある場合、チェーンテーブルの次のノードがtaiであれば、tailを更新して現在のノードを指し、現在のノードがnullに設定され、チェーンテーブルの長さを更新して、前のtail要素に戻ります.

let currentNode=this.head;
     let secondToLastNode;

     //                   
     while(currentNode){
         if(currentNode.next===this.tail){
             //                  
             secondToLastNode=currentNode;
             break;

         }
         currentNode=currentNode.next;
     }
     //     
     secondToLastNode.next=null;
     // tail          
     this.tail=secondToLastNode;
     this.length--;
     //   this.tail
     return nodeToRemove;

チェーンテーブルの次のノードが最後の項目である場合、この現在のプロジェクトは新しいtailであり、その参照を保存する必要があることを隠します.

if(currentNode.next===this.tail){
      secondToLastNode=currentNode;
  }

以下は完全なpop方法です.

 pop(){
      if(this.isEmpty()){
          return null;
      }
      const nodeToRemove=this.tail;
      if(this.head===this.tail){
          this.head=null;
          this.tail=null;
          this.length--;
          return nodeToRemove;
      }
      let currentNode=this.head;
      let secondLastNode;
      while(currentNode){
          if(currentNode.next===this.tail){
              secondLastNode=currentNode;
              break;
          }
          currentNode=currentNode.next;
      }
      secondLastNode.next=null;
      this.tail=secondLastNode;
      this.length--;
      return nodeToRemove
  }

9.Get
get方法は3つの状況を確認しなければならない.
1.インデックスがチェーンの範囲を超えているかどうか
2.チェーンは空ですか?
3.最初の要素を問い合わせる
チェーンに要求の索引が存在しない場合は、nullに戻ります.

if(index<0 || index>this.length){
            return null;
        }

チェーンが空なら、nullに戻ります.

 if(this.isEmpty()){
            return null;
        }

もし私たちが最初の要素を要求したら、headに戻ります.

if(index===0){
           return this.head;
       }

そうでなければ、私たちはチェーンを通して検索するインデックスを見つけるまでです.

 let current=this.head;
       let iterator=0;
       while(iterator

 get(index){
          if(index<0 || index>this.length){
              return null;
          }
          if(this.isEmpty()){
              return null;
          }
          if(index===0){
              return this.head;
          }
          let current=this.head;
          let iterator=0;
          while(iterator

10.Delete
delete方法は三つのところに配慮が必要です.
1.削除されたインデックスはチェーンの範囲を超えています.
2.チェーンは空ですか?
3.私たちはheadを削除したいです.
チェーンに削除するインデックスが存在しない場合は、nullに戻ります.

 if(index<0 || index>this.length){
         return null;
     }

もし私達がheadを削除したいなら、headをチェーンテーブルの次の値に設定して、長さを減らして、削除したばかりの値を返します.

if(index===0){
        const nodeToDelete=this.head;
        this.head=this.head.next;
        this.length--;
        return nodeToDelete;
    }

以上が全部でない場合、ノードを削除するロジックは以下の通りです.
検索中のインデックスを巡回して、インデックス値を増加し、前と現在のポインタを上に移動し、現在を削除対象として保存しているノードを更新し、少年宮のノードのポインタを次のノードに向けて更新します.もし次の値が‘null’であれば、tailを新しい最後のノードに設定し、チェーンテーブルの長さを更新し、削除されたノードに戻ります.
以下は完全なdelete方法です.

 delete(index){
        if(index<0 || index>this.length-1){
            return null;
        }
        if(this.isEmpty()){
            return null;
        }
        if(index===0){
            const nodeToDetele=this.head;
            this.head=this.head.next;
            this.length--;
            return nodeToDetele;
        }
        let current=this.head;
        let pervious;
        let iterator=0;
        while(iterator

UFLDL教程の答え(2):Exercise:Vectorization