パート1に戻って、リンクリストとは何か、より高度なデータ構造を作成するためにリンクリストが必要な理由を確認しました。 これで、JavaScriptでフル機能の二重リンクリストの実装を開始する方法を学ぶことができます。

単一リンクリストと他のデータ構造の実装は、通常、ここで取り上げる内容のより基本的なバージョンになるため、一般的な参照としてブックマークすることをお勧めします。

構造

他のクラスと同様に、各ノードに必要なものを格納できます。重要な部分はnextおよびprevポインターのみで、デフォルトではnullになっています。

同様に、リストに必要なのはtailhead、およびlengthだけです。 配列とは異なり、長さは計算されず、アイテムの検索に必要になるため、手動で長さを操作する必要があります。

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

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

作成

これで、linkedListクラス内のすべてのメソッドの設定を開始できます。 pushshiftのような通常のグッズはないので、独自のバージョンを作成する必要があります。

頭と尻尾

私たちの操作のほとんどは、変更したい項目よりも、周囲のノードのポインターの操作に基づいています。 何かを追加するということは、配列のように必要な場所に新しいノードを表示するだけでなく、新しいアイテムを指すように前後のアイテムのポインターを変更してから、リストの長さを手動でインクリメントすることです。

リストに何も含まれていない場合は、新しいアイテムが唯一のアイテムであるため、ヘッドとテールの両方として設定します。 リストの最後に追加または削除するには、置き換えたい現在のヘッド/テールを取得し、そのポインターを新しいアイテムまたはnullに設定し、リストのヘッド/テールを新しいノードまたはnullに変更してから、長さ。

addHead(val) {
  let newNode = new Node(val);

  if (!this.head) {
    this.head = newNode;
    this.tail = this.head;
  };

  this.head.prev = newNode;
  newNode.next = this.head;
  this.head = newNode;

  this.length++;
  return this;
}

addTail(val) {
  let newNode = new Node(val);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  };

  this.tail.next = newNode;
  newNode.prev = this.tail;
  this.tail = newNode;

  this.length++;
  return this;
}

removeHead() {
  let removed = this.head;
  if (!this.head) return undefined;

  this.head = this.head.next;
  this.head.prev = null;

  this.length--;
  return removed;
}

removeTail() {
  let removed = this.tail;
  if (!this.tail) return undefined;

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

  this.tail = removed.prev;
  this.tail.next = null;

  this.length--;
  return removed;
}

探す

アイテムを取得するためのインデックスがないため、リストの中央での挿入/削除で問題が発生するため、独自のユーティリティ関数が必要になります。

非常に簡単です。現在のアイテムを保存し、forまたはwhileループを使用して、目的のアイテムに到達するまでポインターを使用してcurrentを更新する必要があります。 。

Animation: Finding

VisuAlgo.netのおかげでグラフィック/アニメーション

もちろん、これによりO(n)の検索時間が得られますが、二重リンクリストを使用しているため、必要なものがリストの中央を超えている場合は、末尾から開始してO(n / 2)

find(index) {
  let current
  if (index < 0 || index >= this.length) return undefined;

  if (index <= this.length / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) current = current.next;
  } else {
    current = this.tail;
    for (let i = this.length; i > index; i--) current = current.prev;
  }

  return current;
}   

挿入と削除

小さなユーティリティが配置されたので、これを使用してインデックス内のアイテムを検索し、そのアイテムとその前後のアイテムを新しいノードに設定して、所定の位置に「ステッチ」します。

Animation: inserting

VisuAlgo.netのおかげでグラフィック/アニメーション

インデックスがヘッドまたはテールにある場合は、以前のメソッドを再利用できます。

insert(val, index) {
  if (index < 0 || index > this.length) return null;
  if (index === this.length) return this.addTail(val);
  if (index === 0) return this.addHead(val);

  let prev = this.find(index - 1),
      newNode = new Node(val),
      temp = prev.next;

  prev.next = newNode;
  newNode.next = temp;
  newNode.prev = prev;

  this.length++;
  return true;
}

削除は明らかに挿入の逆であり、少し簡単です。 削除するノードを見つけて、周囲のノード上のポインターを相互に設定し、削除されたノードを参照するものは何も残しません。

Animation: removing

VisuAlgo.netのおかげでグラフィック/アニメーション

remove(index) {
  if (index < 0 || index >= this.length) return null;
  if (index === this.length) return this.removeTail();
  if (index === 0) return this.removeHead();

  let removed = this.find(index);

  removed.prev.next = removed.next;
  removed.next.prev = removed.prev;

  this.length--;
  return removed;
}

アップデート

これはとてもシンプルなので、言及する価値はほとんどありません。アイテムを見つけて、その値をリセットするだけです。

update(val, index) {
  let node = this.find(index);
  if (node) node.val = val;
  return node;
}

結論

これは大変な作業のように思えるかもしれませんが、多くの場合、すべてが必要になるわけではないことを覚えておくとよいでしょう。

手動で作成したくない場合は、 Buckets.js をチェックすることを強くお勧めしますが、概念をより深く理解することは常に良いことです。