循环链表是一种数据结构，其中最后一个节点的next连接回到第一个节点，形成一个循环。此结构允许连续遍历而不会中断。
循环链表对于日程安排和音乐播放列表等任务特别有用，这允许播放完毕后回到第一首继续播放。
在这小节中，我们将介绍循环链表的基础知识、如何使用它们、它们的优点和缺点以及它们的应用。

什么是循环链表？

循环链表是一种特殊类型的链表，其中所有节点都连接起来形成一个环。
与我们前面讲到的链表不同的是，循环链表中的最后一个节点的next指向第一个节点。这意味着当遍历到尾部时可以继续向头部遍历。

循环链表是从单链表和双链表扩展出来的，因此，循环链表基本只有这两种类型。

循环单链表

在循环单链表中，每个节点只有一个指针，称为next指针。最后一个节点的next指针指向第一个节点，这样就形成了一个环。在循环单链表中，我们只能沿一个方向遍历链表。

循环单链表结构

数据结构

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

data：数据域，也是节点的值
next：指针域，指向下一个结点的指针

在上面的定义中，每个节点都有data数据域和next指针域，和普通的单链表结构一模一样，唯一区别就是当我们为循环链表创建多个节点时，我们只需要将最后一个节点连接回第一个节点即可。

循环单链表的基本操作实现

创建循环单链表

插入是链表中的基本操作。和普通单链表的唯一区别是将最后一个节点的next连接到第头结点。
插入大概可以分为以下三种情况

1.在空链表中插入新结点

在空链表中插入新结点

这里使用的是带头结点的单链表来实现循环链表，所以链表空的条件是头结点的next指向头结点，即头结点自己指向自己。
在空的循环链表中插入一个节点，需要创建一个新结点，将其next指针指向头结点，以达到循环的目的。

2.在链表中部插入新结点

在链表中部插入新结点

和普通单链表操作一样，在中部插入结点并没有改变尾结点next的指向。

3.在链表尾部插入新结点

在链表尾部插入新结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;
LNode* pTemp = (LNode*)malloc(sizeof(LNode));
pTemp->data = e;
pTemp->next = p->next; // 将新节点的next指向p的下一个节点
p->next = pTemp; // 更新p的next指向新节点，完成插入操
// 完整代码：https://totuma.cn

上面三种情况，都可以统一为同一操作：
1.找到待插入位置的前驱结点，即p；
2.创建新结点pTemp；
3.使pTemp的next指向p的next；
（如果是空链表，那么p的next指向头结点本身。如果是在末尾插入，p的next同样也是指向头结点）
4.使p的next指向pTemp；

按位序插入结点 | 可视化完整可视化

2.4 循環単方向連結リスト詳解 - 線形リストチュートリアルアニメーションでコードを可視化しよう

データ構造とアルゴリズム可視化学習プラットフォームへようこそ：連結リスト（Linked List）を完全理解する

データ構造とアルゴリズムの学習において、連結リスト（Linked List）は線形リストの一種であり、配列と並んで最も基本的かつ重要なデータ構造です。しかし、多くの学習者が「連結リストのノードがどのように連結されているのか」「ポインタの繋ぎ替えがなぜ必要なのか」といった概念でつまずきます。本記事では、初心者にもわかりやすく連結リストの原理、特徴、応用シーンを解説し、さらにデータ構造可視化学習プラットフォームを使うことで、なぜ効率的に理解が深まるのかをご紹介します。

連結リスト（Linked List）とは何か？基本の「き」

連結リストとは、複数のノード（要素）がポインタ（参照）によって一方向または双方向に連結されたデータ構造です。配列がメモリ上で連続した領域を確保するのに対し、連結リストの各ノードはメモリ上の任意の場所に存在し、次のノードへのポインタを持っています。このため、連結リストは動的なサイズ変更や途中への挿入・削除が非常に得意です。

例えば、あなたが電車の連結を想像してみてください。各車両（ノード）が連結器（ポインタ）でつながっています。新しい車両を追加したいときは、連結器を外して新しい車両を挟み込めば良いのです。これが連結リストの基本的な動作イメージです。

連結リストの種類：単方向、双方向、循環

連結リストには主に以下の3種類があります。

単方向連結リスト（Singly Linked List）：各ノードが次のノードへのポインタのみを持ちます。最後のノードのポインタはNULL（終端）を指します。シンプルでメモリ効率が良い反面、前のノードに戻ることができません。

双方向連結リスト（Doubly Linked List）：各ノードが前のノードへのポインタと次のノードへのポインタの両方を持ちます。これにより前後の移動が自由自在ですが、その分メモリを多く消費します。

循環連結リスト（Circular Linked List）：最後のノードのポインタが最初のノードを指すことで、環状（サークル）になった構造です。単方向・双方向の両方のバリエーションがあります。無限ループに注意が必要ですが、リングバッファなどの実装に便利です。

連結リストの操作：挿入、削除、検索の仕組み

連結リストの操作を理解することは、アルゴリズム学習の核心です。ここでは代表的な操作を解説します。

先頭への挿入（Insert at Head）：新しいノードを作成し、そのポインタを現在の先頭ノードに向けます。その後、リストの先頭ポインタを新しいノードに更新します。この操作はO(1)の定数時間で完了します。

末尾への挿入（Insert at Tail）：末尾ノードまで辿り（O(n)）、そのポインタを新しいノードに向けます。双方向連結リストであれば、末尾ポインタを保持することでO(1)で挿入可能です。

特定位置への挿入（Insert at Position）：挿入したい位置の1つ前のノードまで辿り、ポインタの繋ぎ替えを行います。この作はO(n)の時間がかかります。

ノードの削除（Deletion）：削除したいノードの前後のポインタを繋ぎ直します。単方向リストでは削除するノードの1つ前のノードを特定する必要があるため、通常はO(n)です。双方向リストでは削除するノード自体から前後のノードにアクセスできるため、そのノードが特定できていればO(1)で削除可能です。

検索（Search）：先頭から順にノードを辿り、目的のデータを持つノードを探します。最悪の場合、リスト全体を走査するためO(n)です。

配列（Array）と連結リスト（Linked List）の比較：どちらを選ぶべきか？

データ構造を選ぶ際、配列と連結リストの特性を理解することは重要です。

メモリ使用量：配列はデータ自体のみを格納しますが、連結リストはデータに加えてポインタ（単方向で1つ、双方向で2つ）を格納するため、オーバーヘッドが発生します。

アクセス速度：配列はインデックスによるランダムアクセスがO(1)で可能ですが、連結リストは先頭から順に辿る必要があるためO(n)です。

挿入・削除の速度：配列は途中への挿入・削除で要素のシフトが必要なためO(n)ですが、連結リストはポインタの繋ぎ替えのみでO(1)（ただし、挿入位置の特定にO(n)かかる場合あり）です。

サイズ変更：配列は固定サイズであり、動的配列でもリサイズ時にコピーコストが発生します。連結リストは動的なサイズ変更が容易です。

つまり、「頻繁に検索を行うなら配列」「頻繁に挿入・削除を行うなら連結リスト」というのが基本的な選択基準です。

連結リストの実践的な応用シーン

連結リストは理論上のデータ構造だけでなく、実際のソフトウェア開発でも広く使われています。

1. ファイルシステム：OSのファイルシステムでは、ディスク上のブロックを連結リストで管理することがあります。特にFAT（File Allocation Table）ファイルシステムは、クラスタを連結リストで繋ぐ方式を採用しています。

2. ブラウザの履歴（戻る・進む）：ブラウザの「戻る」「進む」機能は双方向連結リストで実装されています。現在のページを基準に、前のページと次のページをインタで繋いでいるのです。

3. 音楽プレイヤーのプレイリスト：曲を追加・削除・並び替えするプレイリストは、連結リストの典型的な応用例です。特に循環連結リストを使えば、最後の曲の次に最初の曲を再生する「リピート」機能が簡単に実装できます。

4. 画像ビューア：複数の画像を順に表示するアプリケーションでは、双方向連結リストを使って前後の画像にスムーズに移動できます。

5. グラフの隣接リスト表現：グラフアルゴリズムにおいて、各頂点に隣接する頂点のリストを連結リストで保持することが一般的です。これは疎なグラフ（エッジが少ないグラフ）でメモリ効率が良くなります。

6. ハッシュテーブルのチェイン法：ハッシュテーブルで衝突が発生した場合、同じハッシュ値を持つ要素を連結リストで連結する方法（チェイン法）は非常にポピュラーです。

7. メモリ管理（フリーリスト）：OSのモアロケータは、解放されたメモリブロックを連結リスト（フリーリスト）で管理し、新しいメモリ要求があった際に適切なブロックを割り当てます。

連結リストのメリットとデメリット：総まとめ

メリット

動的なサイズ変更が容易
先頭や末尾への挿入・削除が高速（O(1)）
メモリの断片化に対応しやすい
実装が比較的シンプルで理解しやすい

デメリット

ランダムアクセスができない（インデックス指定で直接アクセス不可）
ポインタのための余分なメモリが必要
キャッシュの局所性が低い（メモリ上で連続していないため、キャッシュミスが発生しやすい）
検索にO(n)の時間がかかる

データ構造可視化プラットフォームの機能と利点

ここで、本プラットフォーム「データ構造とアルゴリズム可視化学習プラットフォーム」の特長をご紹介します。このプラットフォームは、連結リストを含むあらゆるデータ構造とアルゴリズムをアニメーションとインタラクティブな操作で視覚的に学習できる環境を提供します。

1. リアルタイム可視化：連結リストのノードが画面上で実際に連結され、ポインタが矢印で表示されます。ノードの挿入や削除を行うと、ポインタの繋ぎ替えがアニメーションで表現されるため、「なぜこの操作でO(1)なのか」が直感的に理解できます。

2. ステップ実行機能：連結リストの操作を1ステップずつ実行できます。例えば「ノード3を削除する」という操作を、ポインタの変更前→変更中→変更後と段階的に確認できます。これにより、アルゴリズムの内部動作を完全に追跡できます。

3. コードと可視化の連携：画面上で表示されている連結リストの操作と、実際のコード（Python、Java、C++など）が同期して表示されます。コードのどの行が実行されると、画面上のどのノードが変化するのかが一目でわかります。

4. インタラクティブな操作：学習者自身がマウス操作でノードを追加・削除・移動できます。例えば、連結リストの途中に新しいノードをドラッグ＆ドロップで挿入すると、自動的にポインタが繋ぎ替えられ、その結果を視覚的に確認できます。

5. 複数の連結リスト種類に対応：単方向、双方向、循環連結リストのすべてを可視化できます。それぞれの違いを横断的に比較しながら学習できます。

6. パフォーマンスの可視化：操作ごとに計算量（O(n)やO(1)など）が表示され、なぜその操作がその時間計算量になるのかをグラフィカルに説明します。例えば、検索操作でノードを1つずつ辿る様子がアニメーションで表示され、O(n)の意味が体感できます。

7. エラー検出とデバッグ支援：誤った操作（例えば、NULLポインタを参照しようとした場合など）を検出し、画面上に警告を表示します。これにより、初心者がよく陥る「ポインタ切れ」や「メモリリーク」の概念を安全に学習できます。

8. カスタムデータセット：学習者が任意のデータ（数値、文字列など）をノードに設定し、独自の連結リストを作成して操作を試すことができます。理論だけでなく、実際のデータを使った実践的な学習が可能です。

可視化プラットフォームの具体的な使い方：連結リスト学習の流れ

では、実際にこのプラットフォームを使って連結リストを学習する流れを説明します。

ステップ1：基本モードで理解する
まずは「基本モード」を選択し、単方向連結リストの構造を確認します。画面上に3〜5個のノードが表示され、各ノードにデータと次のノードへの矢印が表示されます。マウスでノードをクリックすると、そのノードの詳細情報（データ値、ポインタのアドレスなど）がポップアップ表示されます。

ステップ2：挿入操作を試す
「先頭に挿入」「末尾に挿入」「位置指定で挿入」の3つのボタンを用意しています。例えば「先頭に挿入」ボタンをクリックすると、新しいノードが画面上部に出現し、既存の先頭ノードに向かって矢印が伸びるアニメーションが再生されます。同時に、右側のコードパネルで対応するコード行がハイライトされます。

ステップ3：削除操作を試す
削除したいノードをクリックして選択し、「削除」ボタンを押します。すると、削除されるノードが点滅した後、前後のノードのポインタが自動的に繋ぎ直され、削除ノードがフェードアウトします。このとき、ポインタの変更箇所が赤色で強調表示されるため、どのポインタが変更されたのかが明確です。

ステップ4：検索操作を試す
「検索」ボタンをクリックし、検索したい値を入力します。すると、先頭ノードから順に1つずつノードがハイライトされながら移動していきます。目的の値が見つかった時点で停止し、見つからなかった場合はリストの終端まで辿って「見つかりませんでした」と表示されます。このアニメーションにより、線形探索の動作原理が完全に理解できます。

ステップ5：双方向・循環連結リストに挑戦
基本を理解したら、双方向連結リストや循環連結リストに切り替えます。双方向では前後の矢印が両方向に表示され、循環では最後のノードから最初のノードへの矢印が表示されます。それぞれの特徴を比較しながら操作を繰り返すことで、連結リスト全体の理解が深まります。

ステップ6：応用問題にチャレンジ
プラットフォームには「連結リストの反転」「中間ノードの検出」「サイクルの検出」などの応用問題が用意されています。これらの問題を可視化環境で解くことで、理論と実践を結びつけた学習が可能です。例えば「連結リストの反転」では、ポインタの向きが1つずつ変わっていく様子をアニメーションで確認しながら、コードを書くことができます。

なぜ可視化学習が効果的なのか：認知科学の観点から

データ構造とアルゴリズムの学習において、可視化は単なる「おまけ」ではなく、学習効果を劇的に高める手法です。認知科学研究によれば、人間の脳は視覚情報を処理するのに特化しており、抽象的な概念を具体的なイメージとして捉えることで理解と記憶が促進されます。

特に連結リストのような「ポインタの繋ぎ替え」という動的な操作は、静止した図やテキストの説明だけでは理解が困難です。可視化プラットフォームでは、操作が動的にアニメーションとして表示されるため、「時間的な変化」を伴うアルゴリズムの動作を直感的に把握できます。

また、インタラクティブ操作により「もしこうしたらどうなるか？」という仮説検証が容易になります。例えば「このノードを除したら、後続のノードはどうなるのか」を実際に試すことができ、試行錯誤を通じた能動的な学習が可能です。

さらに、コードと可視化の同期表示により、「抽象的なコード」と「具体的な動作」の対応関係が明確になります。これにより、コードを読む力（リーディングスキル）と、アルゴリズムを設計する力（デザインスキル）の両方を同時に養うことができます。

学習の次のステップ：連結リストからさらに高度なデータ構造へ

連結リストをマスターしたら、次に挑戦すべきデータ構造とアルゴリズムをご紹介します。

スタック（Stack）とキュー（Queue）：連結リストを使って実装できる基本的なデータ構造です。スタックはLIFO（後入れ先出し）、キューはFIFO（先入れ先出し）の動作をします。本プラットフォームでは、連結リストベースのスタックとキューの可視化も用意されています。

二分探索木（Binary Search Tree）：連結リストの考え方を拡張した、ツリー構造の基本です。各ノードが最大2つの子ノードを持ち、データの大小関係に基づいて配置されます。検索・挿入・削除が平均O(log n)で行えます。

ハッシュテーブル（Hash Table）：連結リストをチェイン法の実装に使うデータ構造です。キーと値のペアを高速に保存・検索できます。

グラフ（Graph）：連結リストの応用である隣接リスト表現を使うことで、大規模なグラフを効率的に扱えます。深さ優先探索（DFS）や幅優先探索（BFS）の可視化も本プラットフォームで学習できます。

ソートアルゴリズム：連結リスト特有のソートアルゴリズム（マージソートなど）も存在します。配列とは異なるポインタ操作が必要となるため、可視化環境での学習が特に有効です。

プラットフォームの技術サポートとコミュニティ

本プラットフォームは、学習者が安心して利用できるよう、以下のサポートを提供しています。

多言語対応：日本語を含む10以上の言語に対応しており、母国語で学習できます。用語の説明も各言語の教育現場で使われる標準的な表現に準拠しています。

進捗管理機能：学習者がどのデータ構造・アルゴリズムをどの程度学習したかを記録し、学習の進捗を可視化します。苦手な分野を自動的に特定し、重点的に復習するためのレコメンド機能も搭載しています。

オンラインエディタ：プラットフォーム内でコードを書き、即座に実行して可視化と連携させることができます。コンパイルや実行環境のセットアップは不要で、ブラウザだけで完結します。

コミュニティフォーラム：他の学習者と疑問点を共有したり、可視化コンテンツを共同で作成したりできるコミュニティ機能があります。初心者から上級者まで、互いに学び合える環境が整っています。

定期的なアップデート：新しいデータ構造やアルゴリズムの可視化コンテンツが定期的に追加されます。ユーザーからのフィードバックをもとに、可視化の品質向上も継続的に行われています。

まとめ：連結リストをマスターして、データ構造の基礎を固めよう

連結リストは、データ構造とアルゴリズムの学習において避け通れない重要なテーマです。その原理を理解することは、より複雑なデータ構造（ツリー、グラフ、ハシュテーブルなど）を学ぶための強固な基盤となります。

本記事で解説したように、連結リストには単方向・双方向・循環といった種類があり、それぞれに適したユースケースがあります。また、配列との比較を通じて、データ構造選択の判断基準を身につけることができます。

そして何より、データ構造可視化学習プラットフォームを活用することで、抽象的な概念を視覚的・インタラクティブに理解することが可能です。ポインタの繋ぎ替えやノードの操作をアニメーションで確認し、コードと連動させながら学習することで、従来の教科書や動画学習では得られない深い理解を得ることができます。

連結リストの学習は、データ構造とアルゴリズムの世界への第一歩です。このプラットフォームで基礎をしっかり固め、次のステップへと進んでいきましょう。今すぐ無料で始められる基本機能を試して、視覚的学習の効果を実感してください。

あなたのデータ構造学習が、より効果的で楽しいものになることを願っています。

为什么要使用头插法创建，而不是尾插法创建？
如果我们要在链表末尾进行插入，那么需要先遍历整个链表找到尾结点，或者使用一个变量记录尾结点的。
而且每次都需要改变尾结点的next指向头结点，以达到循环。
而我们使用头插法，无论链表是否为空，代码都是统一不变，不需要做其他判断。

按位序删除结点

删除操作和普通单链表相同。主要区别在于我们需要确保删除后链表保持循环。

要从循环链表中删除特定的结点，首先需要检查删除的位序是否满足条件。
找到待删除结点的前驱结点即p结点
找到前驱结点p后，使用q记录为待删除结点
修改前驱结点p的next指向待删除结点q的next，即跳过q结点并将其删除

仅有一个结点时，循环指向头结点

删除尾部结点，更新链表循环

删除中间结点

💡 提示
对于带头结点的链表，上面三种情况都可以统一为同一种操作代码

按位序删除结点 | 可视化完整可视化