JavaScriptでコンピュータサイエンス。 Linked list - Human Who Codes

2009年のことですが、私は1年間、1週間に1回ブログ記事を書くことに挑戦しました。ブログへのトラフィックを増やす最良の方法は、一貫して投稿することだと読んだことがあったからです。週1回の投稿は、私が持っていたすべての記事のアイデアのために現実的な目標のように思えたが、それは私が52のアイデアを十分に不足していることが判明した。最終的にProfessional JavaScriptになる予定の、半分くらいしか書かれていない章を読んでみたところ、データ構造やアルゴリズムなど、古典的なコンピュータサイエンスのトピックに関する資料がたくさん見つかりました。その資料を 2009 年と 2012 年にいくつかの投稿にまとめ、それに対して多くの肯定的なフィードバックを得ました。

リンクリストとは
なぜリンクリストを使用するのでしょうか。
リンクリストの設計
The LinkedList class
リストへの新しいデータの追加
リストからのデータの取得
Remove data from a linked list
Making the list iterable
クラスを使用する

リンクリストとは

リンクリストは、複数の値を線形に格納するデータ構造です。リンクリストの各値は、それ自身のノード、リストの次のノードへのリンクとともにデータを含むオブジェクトに含まれています。リンクは別のノード・オブジェクトへのポインタか、次のノードがない場合はnullとなる。各ノードが他のノードへのポインタを1つだけ持つ場合（最も頻繁に使われるのは next ）、リストは単一リンクリスト（または単なるリンクリスト）とみなされ、各ノードが2つのリンクを持つ場合（通常 previous と next ）、リストは二重リンクリストとみなされます。この投稿では、単一リンクリストに焦点を当てます。

なぜリンクリストを使用するのでしょうか。

リンクリストの主な利点は、それらの値に必要な量のメモリのみを使用しながら任意の数の値を格納できることです。メモリを節約することは、メモリが不足していた古いコンピュータでは非常に重要でした。当時、C言語の組み込み配列では、配列に格納できる項目の数を指定する必要があり、プログラムはその分のメモリを確保する。メモリを確保するということは、たとえそのメモリが一杯にならなくても、プログラムの残りの部分や同時に動いている他のプログラムには使えないということであった。メモリ不足のマシンでは、配列を使っていると簡単に空きメモリがなくなってしまうのだ。リンクリストはこの問題を回避するために作成されました。リンクされたリストを使用し、必要に応じて値を追加することは、配列が含むかもしれない値の最大数を正確に推測することよりはるかに簡単でした。そのため、リンクリストはさまざまなプログラミング言語の組み込みデータ構造の基盤としてよく使用されます。

The built-in JavaScript Array type is not implemented as a linked list, although its size is dynamic and is always the best option to start with ⧏35⧐ しかし、JavaScript Array type はリンクリストとして実装されていません。 JavaScript でリンクリストを使用する必要なくキャリアを全うできるかもしれませんが、リンクリストは独自のデータ構造の作成について学ぶにはまだ良い方法です。

リンクリストの設計

リンクリストの最も重要な部分は、そのノード構造です。各ノードはいくつかのデータとリスト内の次のノードへのポインタを含む必要があります。以下は、JavaScript での簡単な表現です。

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

LinkedListNode クラスでは、data プロパティにリンク先リストのアイテムが格納すべき値が含まれ、next プロパティはリスト内の次のアイテムへのポインターとなります。 next プロパティは、まだ次のノードがわからないので null として始まっています。次に、LinkedListNode クラスを使用して、次のようにリンクリストを作成できます。

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

リンクリストの最初のノードは通常ヘッドと呼ばれるので、この例では head 識別子が最初のノードを表します。 2番目のノードはhead.nextに代入されて作られ、2つの項目を持つリストが作られる。 3番目のノードは、リストの2番目のノードのnextポインタであるhead.next.nextに割り当てられて追加される。リスト内の3番目のノードのnextポインタはnullのままである。次の画像は、結果として得られるデータ構造を示しています。

Diagram of a Linked List by Lasindi - Own work, Public Domain

リンクリストの構造では、各ノードの next ポインタをたどることによって、すべてのデータをたどることが可能になっています。以下は、リンクリストをたどり、それぞれの値をコンソールに出力する簡単な例です。

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

このコードでは、リンクリストを移動するポインタとして変数 current を使っています。変数 current はリストの先頭に初期化され、 current が null になるまで while ループが続けられる。ループの内部では、currentノードに格納された値が表示され、nextポインタが次のノードに続く。

ほとんどのリンクリスト操作はこの探索アルゴリズムかそれに似たものを使用しているので、このアルゴリズムの理解はリンクリスト一般を理解するのに重要である。

The LinkedList class

C 言語でリンクリストを記述する場合、この時点で停止し、タスクは完了したと考えるかもしれません (ただし、各ノードを表すためにクラスではなく構造体を使用します)。しかし、JavaScript のようなオブジェクト指向言語では、この機能をカプセル化するためにクラスを作成することがより一般的です。以下は簡単な例です。

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

LinkedList クラスはリンクリストを表し、それが含むデータを操作するためのメソッドを含むことになります。唯一のプロパティは head というシンボルプロパティで、これはリストの最初のノードへのポインタを含んでいます。シンボルプロパティは、このプロパティがクラスの外部で変更されることを意図していないことを明確にするために、文字列プロパティの代わりに使用されます。

リストへの新しいデータの追加

リンクリストに項目を追加するには、正しい位置を見つけるために構造を歩き、新しいノードを作成し、所定の位置に挿入することが必要です。この場合、単に新しいノードを作成し、それを head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

add() メソッドは 1 つの引数、任意のデータ片を受け入れ、それをリストの最後に追加する。リストが空の場合 (this は null) は、this を新しいノードに等しく代入する。リストが空でない場合は、既に存在するリストを走査して最後のノードを見つける必要がある。この探索はwhileループで行われ、thisから始まり、最後のノードが見つかるまで各ノードのnextリンクをたどっていく。最後のノードはnextプロパティがnullに等しいので、（前のセクションのように）currentがnullになったときではなく、その時点で走査を停止することが重要である。

新しいノードを挿入する場所を見つけるためにリスト全体を走査しなければならないので、add()メソッドの複雑さはO(n)になります。この複雑さを O(1) に減らすには、head に加えてリストの終わり (通常 tail と呼ばれる) を追跡し、正しい位置に新しいノードをすぐに挿入できるようにします。

リストからのデータの取得

リンク付きリストはそのコンテンツへのランダムアクセスを許可しませんが、リストを走査してデータを返すことによって任意の位置にデータを取得することは可能です。これを行うには、以下のように、取得するデータのゼロベースのインデックスを受け取るget()メソッドを追加します:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

get()メソッドはまず、indexが正の値であるかどうかを確認し、そうでなければundefinedを返すようにします。 i 変数はリストに対してどれだけ深く探索を行ったかを記録するために使用される。ループ自体は先ほど見た基本的な探索と同じで、iがindexに等しいときにループを抜けるという条件が追加されている。

current が null であれば、リストは index よりも短い。
i が index と等しければ、current は index 位置のノードである。

current が null なら undefined 、さもなければ current.data が返される。このチェックにより、get() がリスト内で見つからない index に対してエラーを投げることはありません (undefined を返す代わりにエラーを投げることにすることもできますが)。

get() メソッドの複雑さは、最初のノードを削除する場合 (探索は必要ありません) は O(1) 、最後のノードを削除する場合は O(n) (リスト全体の探索は必要です) といった範囲です。

Remove data from a linked list

Remove data from a linked list は、ノードが削除された後もすべての next ポインタが有効であることを確認する必要があるため、少し厄介な処理となります。たとえば、3 つのノードからなるリストの 2 番目のノードを削除する場合、最初のノードの next プロパティが 2 番目のノードではなく 3 番目のノードを指していることを確認する必要があります。この方法で 2 番目のノードをスキップすると、リストから効果的に削除されます。

Linked list removal diagram

remove 操作は、実際には 2 つの操作です。

指定されたインデックスを見つける (get() と同じアルゴリズム)
そのインデックスでノードを削除する

指定されたインデックスを見つけることは get() メソッドと同じですが、このループでは、前のノードの next ポインタを変更する必要があるので current より前のノードを追跡することも必要です。

また、4つの特殊なケースを考慮する必要があります。

The list is empty (no traversal is possible)
The index is less than zero
The index is greater than the number of items in the list
The index is zero (removing the head)

最初の三つのケースでは削除操作が完了できないため、エラーをスローします。4番目の特殊ケースではthisプロパティを書き換えることが必要です。以下は、remove() メソッドの実装の様子である。

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

remove()メソッドは、まず2つの特殊ケース、空のリスト (this は null) とゼロより小さい index について確認する。

次の特別なケースは、index が 0 である場合、つまり、リストの先頭を削除する場合です。新しいリストヘッドはリストの2番目のノードであるべきなので、this を this.next と同じに設定できます。 thisは最終的にnullと等しくなるので、リスト内にノードが1つしかなくても問題ありません。つまり、削除後のリストは空になります。

4 つの特殊なケースのうち 3 つが解決されたので、get()メソッドにあるのと同様のトラバーサルを行うことができるようになりました。先に述べたように、このループは previous 変数が current の直前に現れたノードを追跡するために使われている点が少し異なっている。 get()と同様、ループが終了するとcurrentはnullとなり、インデックスが見つからなかったことを示す。そうでない場合は previous.next に current.next がセットされ、リストから current が効果的に削除される。

remove() メソッドの複雑さは get() と同じで、最初のノードを削除するときの O(1) から最後のノードを削除するときの O(n) までです。

Making the list iterable

ループと配列再構成で使用するために、データのコレクションは iterables でなければなりません。 JavaScript の組み込みコレクションである Array や Set はデフォルトで反復可能であり、クラスに対して Symbol.iterator ジェネレータメソッドを指定することで、独自のクラスを反復可能にすることができます。私はまず values() ジェネレータメソッドを実装し (組み込みのコレクションクラスにあるメソッドと一致させ)、 Symbol.iterator が values() を直接呼び出すようにすることを好みます。

values() メソッドはリストの基本的な走査と各ノードが含む yield データを行うだけでよい:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

values()メソッドは、それが生成メソッドであることを示すアスタリスク (*) でマークされています。このメソッドはリストを走査し、遭遇したデータの各ピースを返すために yield を使用する。 (Symbol.iterator メソッドは values() ジェネレータメソッドからイテレータを返しているため、ジェネレータとしてマークされていないことに注意してください。)

クラスを使用する

完成したら、リンクリストの実装を次のように使用できます:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

このリンクリストの基本実装は、リスト内のノード数をカウントするsizeプロパティと indexOf() などのおなじみのメソッドを使用して丸くすることが可能です。完全なソースコードは、GitHub の私の [Computer Science in JavaScript] プロジェクトで入手できます。互いにポイントするノードを使用するというコンセプトは、他の多くのデータ構造で使用されており、多くの高水準プログラミング言語に組み込まれています。リンクリストがどのように機能するかをよく理解することは、他のデータ構造をどのように作成し使用するかを全体的によく理解するために重要です。

JavaScript のプログラミングでは、独自のコレクションを作成するより、Array などの組み込みコレクションクラスを使用する方がよい場合がほとんどです。組み込みのコレクションクラスはすでに実運用に最適化されており、実行環境全体にわたってよくサポートされています。