JavaScriptにおけるリンクリストの表現方法
JavaScriptにおけるリンクリストの表現
リンクリスト(連結リスト)は、データを格納するための基本的なデータ構造のひとつです。配列と異なり、各要素(ノード)が「データ」と「次の要素への参照」を持つことで、順序付きのコレクションを表現します。JavaScriptでは、オブジェクトと参照を組み合わせることで、リンクリストをシンプルに実装できます。
上図のイラストが示すとおり、リンクリストの構造を理解するうえで押さえておくべき重要なポイントは以下のとおりです。
- LinkedListには「first」と呼ばれるリンク要素が含まれる — リストの先頭を指す参照であり、ここからリスト全体をたどることができます。
- 各リンク(Link)はデータフィールドと「next」というリンクフィールドを持つ — データフィールドには実際の値が格納され、nextフィールドには次のノードへの参照が入ります。
- 各リンクは自身のnextフィールドを通じて次のリンクと接続される — この参照の連鎖によって、リスト全体がひとつの連続した構造として機能します。
- 最後のリンクはnextとしてnullを持つ — これがリストの終端を示すマーカーとなり、走査処理の終了条件として利用されます。
このように、リンクリストは「先頭への参照(first)」「各ノードが持つ次ノードへの参照(next)」「終端を示すnull」という3つの要素で構成されています。リストの走査はfirstから始め、nextを順にたどり、nullに到達した時点で終了します。この仕組みを理解することで、挿入や削除が効率的に行えるデータ構造の設計に役立ちます。
-
JavaScriptで学ぶ循環型単一リンクリスト（Circular Singly Linked List）の基本
循環型単一リンクリストとは？ 循環型単一リンクリスト（Circular Singly Linked List）とは、通常の単一リンクリスト（片方向連結リスト）を変形させたデータ構造です。最大の特徴は、最後のノードのnextポインタが最初のノードを指すという点にあります。 一般的な単一リンクリストでは、末尾ノードのnextポインタはnullを指し、そこでリストが終了します。しかし循環型の場合、このnextポインタが先頭ノードへと接続されるため、リスト全体がひとつの輪（リング）のように連なり、終端のない環状構造になります。 通常の単一リンクリストとの違い 終端の扱い： 通常のリストでは末尾ノ
-
JavaScriptで双方向連結リストの要素を削除する方法
双方向連結リストから要素を削除する仕組み連結リストからの要素削除は非常にシンプルです。やるべきことは「削除したいノードへの参照を失わせる」こと、つまり対象ノードをリンクのチェーンから切り離すだけです。ただし、削除する位置によって処理が異なるため、次の3つのケースを考慮する必要があります。先頭（head）の要素を削除する： head = head.next と代入するだけで、先頭ノードへの参照は失われ、headは2番目の要素を指すようになります。このとき、新しいheadのprevをnullに設定し、前方向のリンクも忘れずに切っておきます。末尾（tail）の要素を削除する： 後ろから2番目のノード