開発者ドキュメント

JavaScriptを介したリンクリストの概要-パート2：実装

getdocs

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

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

構造

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

同様に、私たちのリストに必要なのは tail, head、 と 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 クラス。 私たちには通常のグッズがないので push また shift 独自のバージョンを作成する必要があります。

頭と尻尾

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

リストに何も含まれていない場合は、新しいアイテムが唯一のアイテムであるため、ヘッドとテールの両方として設定します。 リストの最後に追加または削除するには、置き換えたい現在のヘッド/テールを取得し、そのポインターを新しいアイテムまたは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 必要なアイテムに到達するまで。

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;
}

挿入と削除

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

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;
}

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

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 をチェックすることを強くお勧めしますが、概念をより深く理解することは常に良いことです。

モバイルバージョンを終了