JavaScriptのリンクリスト:実装と操作(基礎)

Linked Listは、配列に非常に類似した線形データ構造である.しかし、配列において、データは各々の要素が事項インデックスを有する値の連続チャンクとして記憶される.リンクリストにおいて、全ての要素は異なるメモリー位置に格納されて、ポインタ(次のノードのメモリーアドレスである)によって、一緒にリンクされる.
各要素(ノードと呼ばれます)は2つの部分を含みます:どんなタイプのデータと次の要素へのポインタ.最後のノードはNULL(人間の言語では何も)を指します.最初の要素へのリファレンスは一般にheadと呼ばれ、最後の要素へのリファレンスはtailと呼ばれます.我々は常にテールを知っている必要はありませんが、リストの最初の要素を覚えておく必要があります.

この記事では、JavaScriptのシングルリンクリストの実装といくつかの操作について説明します.

JSにおけるリンクリストの実装

プログラミング言語では、リンクリストは、別のデータ構造として、または単にインタビューの質問でより一般的に使用されるリストの頭への参照として表現することができます.ヘッドを有すること、非常に第1のノードへのカーソルを有する、再び、コンピュータメモリの全てのノードが連結されるので、全体リストを参照できる.
JavaScriptでは、クラスまたは関数を持つ単一のリンクリストを実装できます.どちらの場合も、次のノードへのデータとポインタを2つ定義する必要があります.
このようにしてリンクリストのクラスを定義できます.

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

以下のようにして関数を定義できます:

const ListNode = (val, next) => {
  this.val = (val===undefined ? 0 : val);
  this.next = (next===undefined ? null : next);
}

最後の実装では、引数を渡さない場合、ノードはデフォルトで0値とNULLポインタで作成されます.
1の値を持つ最初のノードインスタンスを作成し、ヘッドカーソルを設定します.

let node1 = new ListNode(1);
let head = node1;

つのノードを含むリストを作成しました.ヘッドカーソルを設定すると、リスト全体head=[1]を返すことができます.

return head;

連結リストの操作

ここで、ノードを挿入し、ノードを削除し、リストを横断するなどの、単一のリンクリストの基本的な操作を実装しましょう.

ノードの挿入

リストの最も簡単な操作はノード(リストの終わりに加える)を追加することができました.そのためには、ノードのメモリを割り当て、前のノードとリンクしなければなりません.

node1.next = new ListNode(2);

2番目のノードをリストに追加しました.

同時に、ノードを追加するために(リストの先頭にpushする)、まずノードを作成し、新しいノードが最初にリストの残りの部分にリンクするようにポインタを変更し、次に頭が新しいノード(ポイントが空でないことを知っている)にポイントします.

const pushFront = (head) => {
  let newNode = new ListNode(0);
  newNode.next = head;
  head = newNode;
  return head;
};

私たちは新しいリストhead=[1,2]を返しました.
最後のノードが見つかるまで、我々がリストを横断しなければならない最後のノードに加える間、ノードをprependingすることは一定のo(1)時間で作られることができます.Nがリストの長さであるとき、これは線形O(n)時間でなされることができます.

ノードの削除

ノードを削除するには、ノードの値を変更するだけで、ノードの値を次のノードの値に変更する簡単な方法を使うことができます(同様のleetcode問題hereを見つけることができます).

const deleteNode = (node) => {
  node.val = node.next.val;
  node.next = node.next.next;
}

ここでは、我々はちょうど場所に値を変更したので、何も返さない.

リストを横断する

単独でリンクされたリストでは、我々は前進することができます.リストを辿るために、我々が取り組んでいる現在のノードを追跡するための追加のポインタを定義すべきです.我々は頭から始めなければならなくて、我々がNULLポインタに達するまで、次のポインタに続いていなければなりません.
各イテレーションの場合、現在のノードが存在するかどうかを調べます(NULLに等しくない).NULLに達するとリストの最後に到達します.

let curNode = head;
  while (curNode) {
    curNode = curNode.next;
  }

同様に、最後の要素を取得するには、次のように実装できます.

const getLast = (head) => {
  let curNode = head;
  while (curNode) {
    curNode = curNode.next;
  }
  return curNode;
};

今、我々は1つの追加の指針でリストを横断することができます.次の記事では、2つのポインターアプローチを使用して、リスト内の要素をより速く効率的に検索できる方法を示します.
私はこの記事は、単一のリンクリストの基礎を理解するのに役立ちます願っています.