だから、リンクリストについて教えてください
最近コーディングブートキャンプを卒業した私は、基本的な知識を深めるためにデータ構造とアルゴリズムの研究に深く取り組んできました。リンクリストは比較的単純なデータ構造ですが、今後さらに複雑なデータ構造の基礎となります。この記事では、リンクリスト（長所、短所、およびそれらの実装方法）について説明します。
データ構造は、簡単に言えば、データを効率的に整理および保持する方法です。
データ構造とは何ですか？
データ構造は、簡単に言えば、データを効率的に整理および保持する方法です。これらを使用すると、後でアクセスできるように情報を保持できます。特定のアイテムを検索したり、特定の順序で並べ替えたり、大規模なデータセットを管理したりできます。JavaScriptには、よく知っていると思われるデータ構造（配列とオブジェクト）があります。これらは、言語にネイティブなプリミティブデータ構造です。非プリミティブデータ構造は、プログラマーによって定義されるデータ構造です。例には、スタック、キュー、ツリー、グラフ、およびハッシュテーブルが含まれます。
リンクリストとは何ですか？
リンクリストは、要素を順番に保持する線形データ構造です。おなじみですか？それらは配列に似ていますが、まったく同じではありません。配列はゼロインデックスです。つまり、各インデックスは値にマップされ、配列の最初の要素はインデックス0から始まります。インデックスがわかっている限り、配列から要素を簡単に取得できます。
一方、リンクリストは他のノードを指すノードで構成されます。各ノードは、それ自体と次のノードのみを認識します。線形データ構造として、アイテムは順番に配置されます。あなたはそれを電車と考えることができます—各鉄道車両は次の鉄道車両に接続されています。リンクリストにはインデックスが付けられていないため、5番目の要素に直接アクセスすることはできません。最初から始めて、次へ進み、5番目の要素が見つかるまで次へ進む必要があります。最初のノードはヘッドと呼ばれ、最後のノードはテールと呼ばれます。リンクリストには、単一リンクリスト、二重リンクリスト、循環リンクリストなどさまざまな種類があります。この記事のために、私は単一リンクリストに焦点を当てます。
配列全体の要素へのアクセスは簡単ですが、コストがかかります。
配列よりもリンクリストを使用する理由
疑問に思われるかもしれませんが、配列を使用して要素に直接アクセスできるのに、なぜこれを使用するのでしょうか。これは本当です！配列全体の要素へのアクセスは簡単ですが、コストがかかります。
配列にはインデックスが付けられているため、要素を最初または途中から削除する必要がある場合は、次のすべてのインデックスをシフトする必要があります。これは、要素を挿入する必要がある場合にも当てはまります。後続のすべての要素のインデックスを再作成する必要があります。リンクリストから要素を挿入または削除する場合、インデックスを再作成する必要はありません。関係するのは、それが指すノードだけです。
単一リンクリストの実装
リンクリストには、単一、二重、循環など、さまざまな種類があります。単一リンクリストは、各ノードに値と次のノードへのポインタ（テールノードの場合はnull）を持つタイプのリンクリストです。一方、二重にリンクされたリストには、前のノードへの追加のポインターがあります。循環リンクリストは、テールノードがヘッドノードを指す場所です。
注：視覚的な学習者の場合は、 https://visualgo.net/en 遊んで、データ構造が変化するのを見るのに最適な場所です。
完全なコードをスキップしたい場合：これをチェックアウトしてください https://gist.github.com/joannaylin/d3dfc926ba73833138e4571c8a0f9a15。
ノードの作成
使用するノードを構築することから始めましょう。値と次のポインタがあり、後続のネイバーを示します。
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
まず、SinglyLinkedListというクラスを作成し、リストの先頭、末尾、および長さの基礎を提供します。
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
最後にノードを追加するために、リストにすでに宣言されているヘッドがあるかどうかを確認します。そうでない場合は、ヘッドとテールを新しく作成されたノードに設定します。すでにheadプロパティがある場合は、tailのnextプロパティを新しいノードに設定し、tailプロパティを新しいノードに設定します。長さを1ずつ増やします。
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
最後にノードを削除するには、最初にリストにノードがあるかどうかを確認する必要があります。ノードがある場合は、テールに到達するまでリストをループする必要があります。最後から2番目のノードの次のプロパティをnullに設定し、tailプロパティをそのノードに設定し、長さを1デクリメントして、削除されたノードの値を返します。
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
最初からノードを削除するために、リストにノードがあるかどうかを確認します。現在のheadプロパティを変数に格納し、headを現在のheadの次のノードに設定します。長さを1デクリメントし、削除されたノードの値を返します。
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
最初にノードを追加するには、最初にノードを作成し、リストにheadプロパティがあるかどうかを確認します。その場合は、新しく作成されたノードの次のプロパティを現在のヘッドに設定し、ヘッドを新しいノードに設定して、長さをインクリメントします。
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
リスト内の位置に基づいてノードにアクセスするには、最初にインデックスが有効なインデックスであるかどうかを確認します。その後、カウンター変数を保持したまま、リストをループします。カウンター変数がインデックスと一致すると、見つかったノードを返します
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
位置に基づいてノードを変更するには、最初にgetメソッドを使用してノードを検索し、値を新しい値に設定します。
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
ノードを挿入するには、最初にインデックスを確認します。0に等しい場合は、シフト解除メソッドを使用します。長さに等しい場合は、リストにプッシュします。それ以外の場合は、インデックスより1つ少ないgetメソッドを使用してbeforeノードを取得します。基本的に、ポインタが正しいノードに向けられるように、選択したインデックスの前後のノードを追跡する必要があります。
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
位置に基づいてノードを削除するには、getメソッドを再度使用し、ノードの挿入に使用したのと同じ原則を使用します。選択したインデックスの前のノードを追跡することで、ポインターを操作できます。
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
リンクリストの強み
リンクリストを使用する利点は、要素をすばやく挿入および削除できることです。リンクリストにはインデックスが付けられていないため、要素の挿入は比較的迅速かつ簡単です。
リンクリストの最後に追加するには、古いテールが新しいノードを指し、tailプロパティが新しいノードに設定されている必要があります。リンクリストの先頭に追加することも同じ前提ですが、新しいノードは古いヘッドを指し、headプロパティは新しいノードに設定されます。基本的に同じアクションなので、挿入はO（1）です。
注：リンクリストの途中に挿入するには、ノード（O（N））を見つけるために検索してから、ノード（O（1））を挿入する必要があります。
リンクリストからノードを削除するのは簡単ですが、そうではありません。これはどこに依存します。リストの先頭からノードを削除するのは簡単です。2番目のノードが新しいヘッドになり、古いヘッドの次のポインターをnullに設定します。リスト全体を調べて最後から2番目のノードで停止する必要があるため、最後から削除するのは難しいです。最悪の場合のO（N）、および最良の場合のO（1）。
リンクリストの弱点
リンクリストの弱点は、インデックスの再作成がないことが原因です。要素に直接アクセスできないため、要素の検索とアクセスが難しくなります。
リンクリスト内のノードを検索してアクセスするには、リストの先頭から開始し、リストの下のブレッドクラムの軌跡をたどる必要があります。リストの最後にあるノードを検索する場合は、リンクリスト全体を調べる必要があり、時間計算量を効果的にO（N）にします。リストが増えると、操作の数も増えます。ランダムアクセスのある配列と比較すると、要素にアクセスするには一定の時間がかかります。
それでおしまい！
リンクリストは、最初の挿入と削除が重要なアクションである場合、配列の優れた代替手段です。配列にはインデックスが付けられますが、リンクリストにはインデックスが付けられません。リンクリストは、スタックとキューを構築するための基本的なデータ構造でもあります。これについては、後の記事で説明します。ここまで進んだら、称賛に値します。プログラミングの旅とともに、ちょっとしたナゲットを学んだことを願っています。
