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

チェーンは何ですか
シングルチェーンテーブルは、一連のノードを表すデータ構造であり、各ノードは、チェーンテーブルの次のノードを指す.対照的に、双方向リンクは、その前後の要素を指すノードを有する.
配列と違って、チェーンテーブルはチェーンテーブルの特定のインデックスへのアクセスを提供しません.したがって、チェーンテーブルの第3の要素が必要であれば、第1のノードと第2のノードを経て、それを得ることができる.
チェーンの利点の一つは、固定時間内にチェーンの先頭と最後から項目を追加し、削除することができることです.
これらは技術面接でよく聞かれるデータ構造ですので、始めましょう.
また、チェーンを並べ替えることもできます.これは、各ノードがチェーンテーブルに追加されると、他のノードに対して適切な位置に配置されることを意味する.
ノード
チェーンは一連のノードだけですので、Nodeオブジェクトから始めましょう.
一つのノードには二つの情報があります.

は、チェーンテーブルの次の項目のポインタまたは参照を指す(シングルチェーンテーブルについて)

.

ノードの値

私たちのノードについては、一つの値を受け取り、次のノードを指すポインタとノードの値を返す関数を作成する必要があります.
注意してください.私たちは声明だけでいいです.valueではなく、value: value.これは変数名が同じ(ES 6文法)からです.
ノードチェーン
今、NodeList類を深く研究してみましょう.以下はノードチェーンの様子です.
ノードチェーンは5つの方法を含みます.

psh(value):チェーンの末尾

に値を追加します.

pop():イジェクトチェーンの最後の値

get(index):与えられた索引の項

を返します.

delete(index):与えられた索引から項目を削除する

isEmpty():ブール値を返し、チェーンテーブルが空かどうか

を示します.
printList():チェーンの生産方法ではなく、我々のチェーンを印刷して、主にデバッグに使います.
構造関数
コンストラクタには3つの情報が必要です.

head:チェーンの先頭ノードへの参照

tail:チェーンの終点ノードへの参照

length:チェーンにはいくつかのノード

がありますか?

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

IsEmptyisEmpty()方法は、リンクが空であればtrueに戻るヘルプ関数である.

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

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

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

Push
新しいノードを追加する前に、push方法は、チェーンテーブルが空かどうかを確認する必要がある.チェーンは空ですか?二つの方法:

isEmpty()方法は、trueに戻る(チェーンの長さはゼロ)

.

headポインタは空

である.
この例では、headを使って、nullであるかどうかを判断します.
チェーンテーブルにエントリがない場合、私たちは簡単にheadポインタとtailポインタを新しいノードに設定し、チェーンテーブルの長さを更新することができます.

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

もしチェーンが空ではないなら、次のような操作をしなければなりません.

は、tail.nextを新しいノード

に向ける.

は、tailを新しいノード

に向ける.

チェーン長

を更新します.
以下は完全なpush方法である.

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

Pop
チェーンテーブルの最後の項目を削除する前に、私達のpop方法は以下の2つの内容を確認する必要があります.

チェーンが空かどうかチェックします.

チェーンの中に一つだけあるかどうかチェックしてください.

isEmpty方法を用いて、リンクテーブルがノードを含むかどうかを確認することができる.

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

チェーンの中にはノードが一つしかないとどうやって分かりますか?headおよびtailが同じノードを指す場合.しかし、このような状況で私たちは何をするべきですか?唯一のノードを削除するということは、実際にチェーンテーブルを再設定することを意味します.

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

チェーンに複数の要素がある場合、以下の操作ができます.

        ，
              tail 
      tail       
           null，
          
         tail   

このように見えます.

    1  let currentNode = this.head;
    2  let secondToLastNode;
    3
    4  //                   
    5 
    6  while (currentNode) {
    7    if (currentNode.next === this.tail) {
    8      //                   
    9      secondToLastNode = currentNode;
   10      break;
   11    }
   12    currentNode = currentNode.next;
   13  }
   14  //      
   15  secondToLastNode.next = null;
   16  //   tail           
   17  this.tail = secondToLastNode;
   18  this.length--;
   19 
   20  //     this.tail
   21   return nodeToRemove;

もしあなたがそれを想像できないなら、それを見てみましょう.
第6-10行:もしチェーンテーブルの次のノードが最後の項目であれば、この現在のプロジェクトは新しいtailであるので、その参照を保存する必要があります.

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

第15行:secondToLastNodeをnullに更新し、これはチェーンテーブルから最後の要素をイジェクトする行為である.

secondToLastNode.next = null;

第17行:tailを更新して、secondToLastNodeを指す.

this.tail = secondToLastNode;

第18行:チェーンの長さを更新します.ノードを削除したばかりです.
第21行:イジェクトしたばかりのノードを返す.
以下は完全なpop方法である.

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const nodeToRemove = this.tail;
  // There's only one node!
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--;
    return nodeToRemove;
  }

  let currentNode = this.head;
  let secondToLastNode;

  // Start at the front and iterate until
  // we find the second to last node
  while (currentNode) {
    if (currentNode.next === this.tail) {
      // Move the pointer for the second to last node
      secondToLastNode = currentNode;
      break;
    }
    currentNode = currentNode.next;
  }
  // Pop off that node
  secondToLastNode.next = null;
  // Move the tail to the second to last node
  this.tail = secondToLastNode;
  this.length--;

  // Initialized to this.tail
  return nodeToRemove;
}

Getget方法は、3つの状況を確認しなければならない.

インデックスがチェーンの範囲を超えていますか?

チェーンは空ですか?

クエリの最初の要素

チェーンテーブルに要求されたインデックスが存在しない場合、nullに戻る.

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

チェーンが空の場合、nullに戻ります.これらのif文を組み合わせることができますが、明確に保つためにそれらを分離しました.

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

最初の要素が要求されたら、headに戻ります.

// We're at the head!
if (index === 0 )  {
  return this.head;
}

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

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

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;

以下は完全なget(index)方法である.

get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

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

// We're at the head!
if (index === 0 )  {
  return this.head;
}

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

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
}

Deletedelete方法は3つの場所を考慮する必要がある.

削除されたインデックスは、チェーンの範囲を超えています.

チェーンは空ですか?

私達はhead

を削除したいです.
私たちが削除するインデックスがチェーンに存在しない場合、nullに戻ります.

// Index is outside the bounds of the list
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`           

      

        

画像の可視化が必要な場合は、Pop部分のグラフを参照してください.
以下は完全なdelete方法である.

delete(index) {
   // Index is outside the bounds of the list
  if (index < 0 || index > this.length - 1) {
    return null;
  }

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

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

  let current = this.head;
  let previous;
  let iterator = 0;

  while (iterator < index) {
    iterator++;
    previous = current;
    current = current.next;
  }
  const nodeToDelete = current;
  // Re-direct pointer to skip the element we're deleting
  previous.next = current.next;

  // We're at the end
  if(previous.next === null) {
    this.tail = previous;
  }

  this.length--;

  return nodeToDelete;
}

あなたのポイントの称賛は私が良いものを共有し続ける原動力です.
フロントエンドの大家族にようこそ.中には常に技術資源を共有します.