アプリケーションとデータがますます複雑になるにつれて、基本的なアレイに制限されることは、パフォーマンスと達成できることの大きなボトルネックになります。 JavaScriptが提供する最も基本的なすぐに使えるデータ型よりも優れたものを開発する必要があります。 リンクリストを使用すると、より高度なデータ構造とアルゴリズムを学習するための基盤を構築できます。

コンセプト

リンクリストは、クラスを使用して接続されたオブジェクトのチェーンを作成する特別な方法です。 これらの各オブジェクトには、次のノードへのポインターと前のノードへのポインターの2つのポインターが含まれています。

配列を使用すると、インデックスによってアイテムに直接アクセスできますが、これは常に O(1)、ノードにはインデックスがないため、リストの先頭または末尾から開始し、ポインタを使用して各アイテムを検索し、変更するアイテムを探す必要があります。 O(n).

配列上にリンクリストが必要なのはなぜですか? 配列は、アイテムに直接アクセスして移動する方が簡単なため、検索と並べ替えの点で優れています。 リンクリストは、特に最後にアイテムを挿入および削除するのにはるかに効率的です。 アイテムを配列に挿入または削除する場合、コンピューターは残りのデータのインデックスを再作成する必要があります。 O(n)、リンクリストでそれを行うことができます O(1) さらに、検索時間も最適化する方法がいくつかあります。

多くのブラウザは、リンクリストを使用して検索履歴を記録します。これは、ユーザーが何かを検索したり、全体を表示したりする必要がほとんどない場合に、チェーンを上下に移動する方がはるかに実用的だからです。

配列を使用すると、Googleに直接再度アクセスできますが、リンクリストを使用すると、配列を新しいテールとして設定するか、手動で目的の配列に戻る必要があります。その間にあるものを飛び越えることはできません。

単一リンクリストと二重リンクリスト

リンクリストを設定するには、主に2つの方法があります。1つのポインターを使用して1つの方向に強制するか、2つの方法で双方向にします。

単一リンクリストを検索するには、各アイテムで必要なものを探す必要がありますが、二重リンクリストは、アイテムの半分がオンになっていることに応じて、先頭または末尾から検索を開始できます。 O(n / 2).

二重にリンクされたリストは、各アイテムが次と前のアイテムへのポインタを格納する必要があるため、より多くのメモリを必要とします。これは、大量のデータを格納する場合に大きな違いを意味する可能性があります。

後で、他の構造にリンクリストを実装するときは、ほとんどの場合、単一リンクリストを使用します。 たとえば、スタックとキューでは、エンドとのみ対話し、リスト全体をトラバースする必要はほとんどないため、2つのポインターは実用的ではありません。

なぜわざわざ?

  • リンクリストは、スタック、キュー、ツリー、グラフ、ヒープなどのより高度なデータ構造の基盤として機能します。 これらはすべて、使用目的に応じて、リンクリストの利点を活用しながら、いくつかの欠点を無効にする方法を備えています。
  • 多くの追加や削除を行う必要がある場合は、アレイよりもパフォーマンスが大幅に向上し、スキップリストを使用するなどの他の手法と組み合わせると、検索時間が短縮されます。
  • カルーセルコンポーネントのように、テールの次のポインタをヘッドに設定することで、ループリストを簡単に作成できます。

結論

この短い紹介の後、標準アレイのより良い代替案を検討する準備ができていることを願っています。 パート2をチェックして、JavaScriptで完全にデッキアウトされた二重リンクリストの実装を開始する方法を学習してください。