JavaScriptで学ぶ循環型単一リンクリスト（Circular Singly Linked List）の基本

循環型単一リンクリストとは？

循環型単一リンクリスト（Circular Singly Linked List）とは、通常の単一リンクリスト（片方向連結リスト）を変形させたデータ構造です。最大の特徴は、最後のノードのnextポインタが最初のノードを指すという点にあります。

一般的な単一リンクリストでは、末尾ノードのnextポインタはnullを指し、そこでリストが終了します。しかし循環型の場合、このnextポインタが先頭ノードへと接続されるため、リスト全体がひとつの輪（リング）のように連なり、終端のない環状構造になります。

通常の単一リンクリストとの違い

• 終端の扱い： 通常のリストでは末尾ノードのnextがnullになりますが、循環型では先頭ノードへの参照を持つため、明確な終端が存在しません。
• 走査（トラバーサル）方法： 循環型をたどる際は、無限ループを避けるために「開始ノードに戻ってきたら処理を終える」といった終了条件が必須になります。
• 巡回処理： どのノードを起点にしても全ノードを一周できるため、順番に処理を回すような場面に適しています。

JavaScriptでの実装イメージ

以下は、循環型単一リンクリストをJavaScriptで構成する基本的なコード例です。

class Node {
  constructor(data) {
    this.data = data;   // ノードが保持する値
    this.next = null;   // 次のノードへの参照
  }
}

// ノードを生成して連結する
const first = new Node(1);
const second = new Node(2);
const third = new Node(3);

first.next = second;
second.next = third;
third.next = first; // 最後のノードが先頭を指す → 循環構造の完成

ポイントは最終行のthird.next = first;です。ここで末尾ノードが先頭ノードを参照することで、リストが環状につながります。

主なメリットと活用シーン

• 起点を選ばない処理： リング状につながっているため、任意のノードを出発点として全要素を巡回できます。
• 周期的な処理に最適： 音楽プレーヤーのループ再生、ゲーム内のターン制管理、CPUのラウンドロビンスケジューリングなど、繰り返し構造のモデル化に役立ちます。
• 省メモリ： 各ノードが持つ参照は次ノードへの1つだけでよいため、双方向リンクリストより少ないメモリで実現できます。

まとめ

循環型単一リンクリストは、「最後のノードのnextポインタが最初のノードを指す」というシンプルな変更によって、終わりのない環状のデータ構造を実現したものです。JavaScriptではクラスを使って直感的に実装でき、ループ再生やスケジューリングなど、周期的な処理が必要な場面で特に威力を発揮します。