JavaScriptでデータ構造を深く理解する - 二重連結リスト

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// 新しいノードを作成します：
const newNode = new Node(10);
console.log(newNode);

/* newNode の出力：
Node {
  value: 10,
  next: null,
  prev: null,
}
*/

class DoublyLinkedList {
  constructor(value) {
    this.head = null;
    this.tail = null;
    this.length = 0;

    // スターター値があるかどうかで二重連結リストを作成するかどうかを選択する
    if (value) {
      this.append(value);
    }
  }
}

const doublyLinkedList = new DoublyLinkedList();
console.log(doublyLinkedList);

/* doublyLinkedList の初期化時の出力（空のスターター）：

DoublyLinkedList {
  head: null,
  tail: null,
  length: 0
}

*/

append(value) {
  // 受け取った値で新しいノードを初期化します
  const newNode = new Node(value);

  // まず二重連結リストが空かどうかを確認しましょう。
  if (!this.head) {
    // ヘッドがない場合（要素なし）、それは空です。その場合、newNodeをヘッドとして設定します。
    // この時点で唯一のノードですし、テールもありませんので、
    // テールは同じ値を持ち（ヘッドとテールはこれから同じメモリ位置を指します）：
    this.head = newNode;
    this.tail = newNode;
  } else {
    // newNodeが新しいテールになるので、変更を適用する前に現在のテールのprev値を設定します。タイミングが重要です！
    newNode.prev = this.tail;
    // 最初の入力時に this.tail = this.head が設定されます
    // 最初に this.tail.next に newNode を入れると、両方が同じオブジェクトを参照しているため、この段階でヘッドとテールが等しく見えます：
    this.tail.next = newNode;
    // この段階で、新しいノードをテールとして設定することで、テールをクリーンアップします。言い換えれば、テールを使ってヘッドを拡張し、その後新しいノードを使ってテールをクリーンアップしました。
    this.tail = newNode;
  }
  this.length++;
  return this;
}

prepend(value) {
  // まず二重連結リストが空かどうか確認しましょう。
  // もしそうなら、代わりにappendメソッドを使ってここでリターンします。

  if (!this.head) {
    return this.append(value);
  }

  // 受け取った値で新しいノードを初期化します
  const newNode = new Node(value);
  // newNode.next プロパティに参照を適用します。最初に追加するとき、自然に前に追加されたノードのnext値は this.head を指すべきです。
  newNode.next = this.head;
  // newNodeが新しいヘッドの前になるので、ヘッドのprev値をnewNodeに設定します。このポインタのthis.headをnewNodeに変更する前に行います。タイミングが重要です！
  this.head.prev = newNode;
  // newNodeにthis.headがnextとして、そしてprevとしてnewNodeがあるので、直接this.headをnewNodeに設定できます。
  this.head = newNode;
  this.length++;
  return this;
}

toArray() {
  const array = [];
  let currentNode = this.head;

  while (currentNode !== null) {
    array.push(currentNode.value);
    currentNode = currentNode.next;
  }
  return array;
}

traverseToIndex(index) {
  // 受け取ったindexパラメータを検証します：
  if (!index) return 'Index is missing';
  if (typeof index !== 'number') return 'Index should be a number';

  let counter = 0;
  let currentNode = this.head;

  while (counter !== index) {
    currentNode = currentNode.next;
    counter++;
  }

  return currentNode;
}

insert(index, value) {
  // 受け取ったindexパラメータを検証します：
  if (!index) return 'Index is missing';
  if (typeof index !== 'number') return 'Index should be a number';

  // もしインデックスが長すぎる場合、またはヘッドがない場合は、単に末尾に追加します（最後に追加）。
  if (index >= this.length || !this.head) {
    return this.append(value);
  }

  // もしインデックスが0なら、ただ先頭に追加します（最初に追加）。
  if (index === 0) {
    return this.prepend(value);
  }

  // 受け取った値で新しいノードを初期化します
  const newNode = new Node(value);

  /*
  解決策の流れ：
    1 - ターゲットidxの前のインデックスノードを選びます。
    2 - preIdx.nextポインタを使ってターゲットidxノードを選びます。
    3 - 新しいノードに指すように前<br><br>こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。<br>[https://dev.to/humblecoder00/deep-dive-into-data-structures-using-javascript-doubly-linked-list-2ddi](https://dev.to/humblecoder00/deep-dive-into-data-structures-using-javascript-doubly-linked-list-2ddi)