循環リンクリスト: 利点と欠点

⚡ スマートサマリー

循環連結リストは、最後のノードが最初のノードに戻るようにノードを配置するため、ラウンドロビンスケジューリング、トークンリング、およびシームレスな走査を必要とするあらゆるワークフローに適した、連続的でNULL値のない構造を実現します。

📚 定義： 各ノードは値と次のノードへのポインタを保持しており、最後のノードの次のノードへのポインタは最初のノードにリンクし、閉じたサイクルを形成します。
📌 ペース： Operaション： 挿入、削除、および走査はすべて、循環を維持しながら1つまたは2つの次のポインタを更新することを中心に展開されます。
🛠️ C言語による実装： malloc をバックとする挿入と free をバックとする削除を備えた構造体ベースのノードは、現在の位置とノード後の両方のケースに対応します。
✅ Advantages: NULL参照なし、シームレスなエンド・トゥ・スタート遷移、そして最悪の場合の検索回数を半減させる二重循環バリアント。
⚠️ 短所： ループ制御がより複雑で、単方向連結リストよりも複雑度が高く、終了処理が正しく記述されていない場合は無限ループに陥る可能性がある。
🎯 用途： ラウンドロビン方式のCPUスケジューリング、トークンリングネットワーク、循環バッファ、メディアプレイリスト、連続表示ユニット。

プロフィール

循環リンクリストとは何ですか?

循環連結リストは、各ノードが再結合できるように配置されたノードのシーケンスです。trac各「ノード」は、自身を参照する要素であり、そのすぐ近くにある 1 つまたは 2 つのノードへのポインタを持っています。

以下は、3 つのノードを持つ循環リンクリストを示しています。

ここでは、各ノードがtracそれ自体で完結します。上記の例は、循環型の単方向連結リストです。

注: 最も単純な循環連結リストは、次のポインタを持つ単一のノードです trac以下のように、元に戻ります。

Basic Opera循環連結リスト内の要素

循環連結リストにおける3つの基本的な操作は以下のとおりです。

挿入
削除と
トラバーサル

挿入は、循環リンクリスト内の指定された位置にノードを配置するプロセスです。
削除は、リンクされたリストから既存のノードを削除するプロセスです。ノードは、その値の出現または位置によって識別できます。
循環リンクリストの走査とは、リンクリスト全体の内容を表示し、tracソースノードに戻ります。

次のセクションでは、挿入の仕組みと、循環単方向連結リストで可能な2種類の挿入について説明します。

挿入 Opera生産

まず、以下に示すように、次のポインタが自身を指すノードを1つ作成します。このシードノードがないと、最初に挿入されたノードがリストの最初のノードになってしまいます。

次に、XNUMX つの可能性があります。

循環連結リストの現在の位置への挿入。これは、通常の単方向連結リストの先頭または末尾への挿入に相当します。循環連結リストでは、先頭と末尾は同じ位置になります。
インデックス付きノードの後に挿入します。ノードは、その要素の値に対応するインデックス番号によって識別される必要があります。

循環連結リストの先頭または末尾（つまり、最初にノードが追加された位置）に挿入するには、以下の手順に従ってください。

既存のノードへの既存の自己リンクを解除する必要があります。
新しいノードの次のポインタは既存のノードにリンクします。
最後のノードの次のポインタは、挿入されたノードを指します。

注：円の開始点または終了点を示すポインタは、任意のノードに再割り当てできます。後述するように、走査は依然として同じノードに戻ります。

(a) i ～ iii の手順を以下に示します。

(既存ノード)

ステップ1） 既存のリンクを解除する

ステップ2） 順方向リンクを作成します (新しいノードから既存のノードへ)

ステップ3） 最初のノードへのループリンクを作成します

次に、ノードの後に挿入してみます。

例えば、「VALUE0」を持つノードを始点として、「VALUE2」を「VALUE0」を持つノードの後に挿入します。

最初のノードと2番目のノード間のリンクを解除し、「VALUE2」を持つノードをその間に配置します。
最初のノードのネクストポインタは新しいノードにリンクし、新しいノードのネクストポインタは以前は2番目のノードだったものにリンクする。
残りの配置は変更されません。すべてのノードはtrac彼ら自身で食べられる。

注：この配列は循環構造になっているため、ノードを挿入する手順はどの位置を選択しても同じです。循環を閉じるポインタは、リスト内の他のポインタと同様に動作します。

これを以下に示します。

(ノードが XNUMX つだけだとしましょう。これは簡単なケースです)

ステップ1） 接続されているノード間の内部リンクを削除します

ステップ2） 左側のノードを新しいノードに接続します

ステップ3） 新しいノードを右側のノードに接続します。

削除 Opera生産

3つのノードからなる循環連結リストを想定します。削除のケースは次の2つです。

現在の要素を削除する
要素の後の削除。

先頭/末尾の削除：

最後のノードから最初のノードまでトラバースします。
末尾から削除する場合、最後のノードから最初のノードまでを1回走査するだけで済みます。
最後のノードと最初のノード間のリンクを削除します。
最後のノードを最初のノードの次の要素にリンクします。
最初のノードを解放します。

(既存のセットアップ)

ステップ1） 円形のリンクを削除する

ステップ2） 最初のノードと次のノードの間のリンクを削除し、最後のノードを最初のノードに続くノードにリンクします。

ステップ3） 最初のノードを解放/割り当て解除する

ノードの後の削除:

削除対象のノードが次のノードになるまで、ノードをたどります。
ポインターを前のノードに置き、次のノードに移動します。
次のポインタを使用して、前のノードを現在のノードの後のノードに接続します。
現在の (リンク解除された) ノードを解放します。

ステップ1） 「VALUE1」のノードを削除する必要があるとします。

ステップ2） 前のノードと現在のノード間のリンクを削除し、前のノードを現在のノードの次のポインタが指すノード（VALUE1の次のノード）に直接リンクします。

ステップ3） 現在のノードを解放または割り当て解除します。

循環リンクリストの走査

循環連結リストを最後のポインタから辿るには、まず最後のポインタがNULLかどうかを確認します。NULLでない場合は、リストに要素が1つだけ含まれているかどうかを確認します。そうでない場合は、以下のアニメーションに示すように、一時的なポインタを使用してリストを辿り、再び最後のポインタに到達します。

循環リンクリストの利点

循環リンクリストには次のような利点があります。

コード内で NULL を割り当てる必要はありません。循環リストは、完全に割り当てが解除されない限り、NULL ポインターを指すことはありません。
循環連結リストは、開始位置と終了位置が一致するため、リストの末尾操作において有利です。 Algorithms ラウンドロビンスケジューリングなどの方式では、ダングリングポインタやNULLポインタに遭遇することなく、キュー内のプロセスをスムーズに処理できます。
循環連結リストは、単方向連結リストのすべての通常の操作をサポートします。二重リンクリスト要素を見つけるためにリスト全体を走査する必要さえなくなる場合がある。最悪の場合でも、ターゲットは開始ポインタの反対側に位置するため、最大でもリストの半分を走査するだけで済む。

循環リンクリストの欠点

循環リンクリストを使用する場合の欠点は次のとおりです。

循環リストは、単一リンクリスト.
Rev循環リストの反転は、単方向連結リストや双方向連結リストの反転よりも複雑です。
ループの終了処理が適切に行われないと、走査コードが無限ループに陥る可能性がある。
リストの末尾を見つけることや、正しいループ制御条件を記述することはより困難です。
先頭に挿入するには、（実装上の観点から）リスト全体を走査して最後のノードに到達する必要があります。

循環リンクリストとしての単一リンクリスト

以下のC言語コードを読んで実装してみることをお勧めします。このコードは、循環単方向連結リストに関連するポインタ演算を示しています。

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

コードの説明：

コードの最初の XNUMX 行は、必要な組み込みヘッダーファイルです。
次のセクションでは、各自己参照ノードの構造を定義します。このノードには、値と、構造体と同じ型のポインタが含まれています。
各構造体インスタンスは、同じ型の他の構造体オブジェクトにリンクします。
以下のさまざまな関数プロトタイプがあります。
1. 空のリンクリストへの要素の追加
2. に挿入する 現在指されている 循環リンクリストの位置。
3. 特定の後に挿入する 索引付けされた リンクされたリストの値。
4. 特定の後の削除/削除 索引付けされた リンクされたリストの値。
5. 循環リンクリストの現在ポイントされている位置を削除する
最後の関数は、リンクリストの任意の状態で循環走査を通じて各要素を出力します。

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

コードの説明：

addToEmpty コードでは、malloc() 関数を使用して空のノードを割り当てます。
受信したデータを一時ノードに配置します。
一時ノードを最後に割り当て、その次のポインタを自身に設定することで、単一ノードが自身を指すようにします。
最後のポインタをmain() / アプリケーションコンテキストに戻します。

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
&#8230;

コードの説明

リストが空の場合は、addToEmpty() に処理を渡し、制御を戻します。
現在のノードの後に配置する一時的なノードを作成します。
上の図に示すように、ポインターを接続してください。
前の関数で使用したパターンに一致する最後のポインタを返します。

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

コードの説明：

リストが空の場合は、検索キーを無視し、現在の項目をリスト内の唯一のノードとして追加し、制御を戻します。
do-whileループの各反復において、previousポインターは最後に走査された結果を保持する。
その時になって初めて、次の走査ステップが実行される。
do-whileループは、対象データが見つかるか、tempが再び最後のポインタに達したときに終了します。次のコードブロックは、見つかった項目に対して何を行うかを決定します。

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

コードの説明：

リスト全体を走査しても目的の項目が見つからない場合は、「要素が見つかりません」というメッセージを表示し、呼び出し元に制御を戻します。
対象ノードが見つかった場合は、挿入する値のための新しいノードを割り当てます。
リンク 前のノードを新しいノードにリンクし、新しいノードの次のポインタをtemp（トラバーサル変数）にリンクします。
これにより、新しい要素は循環連結リスト内のターゲットノードの直後に配置されます。その後、制御は呼び出し元に戻ります。

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

コードの説明

最後の（現在の）ノードを削除するには、まずリストが空かどうかを確認します。リストが空の場合は、要素を削除できません。
temp変数はリンクを1つ前進させる。
最後のポインタを最初のノードの次のノードにリンクします。
一時ポインタを解放して、リンクされていないノードの割り当てを解除します。

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

コードの説明

前回の削除機能と同様に、まずリストが空かどうかを確認します。リストが空の場合は、要素を削除できません。
ツーポインタ削除する要素を見つけるために特定の位置が割り当てられます。
ポインタは、前のトレイルのテンポラリを基準に、一つずつ進んでいきます。
目的の要素が見つかるか、次のポインタが再び最後のノードに到達するまで、走査は継続されます。

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

プログラムの説明

リンクリスト全体を走査しても目的の要素が見つからない場合は、「要素が見つかりません」というメッセージが表示されます。
そうでない場合は、ステップ3と4で要素のリンクが解除され、解放されます。
前のポインタは、temp の次のポインタが指すノード（削除されるノードの次のノード）にリンクされています。
その後、一時ポインタが解放されます。

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

コードの説明

ノードがゼロの場合、ピークトラバーサルは実行できません。ユーザーはまずノードを割り当てるか挿入する必要があります。
ノードが1つしかない場合は、走査は不要です。ノードの内容が直接出力され、whileループは実行されません。
ノードが複数ある場合、temp は最後の要素までのすべての項目を出力します。
最後の要素に到達した瞬間、ループは終了し、関数は制御をmain()関数に戻します。

循環リンクリストの応用

システムプロセスにはラウンドロビンスケジューリングを、高速グラフィックスには循環スケジューリングを実装します。
コンピュータネットワークにおけるトークンリングスケジューリング。
デジタルショップボードなど、データの連続的な走査を必要とする表示装置に使用されます。

よくあるご質問

GitHub CopilotやChatGPTなどのAIアシスタントは、ノード構造、mallocベースの挿入ツール、サイクルセーフな走査ループを生成します。開発者は、生成されたコードを本番データ構造にマージする前に、正しい終了条件とメモリクリーンアップが行われていることを確認します。

機械学習パイプラインでは、ストリーミングデータのローリングウィンドウを保持するために、循環リンクリストに基づいて構築された循環バッファ、強化学習エージェント用のリプレイバッファサンプル、およびトレーニングバッチを供給するプロデューサー/コンシューマーワーカー用の循環キューが使用されます。

単方向連結リストはNULLポインタで終わりますが、循環連結リストの最後のノードは最初のノードを指します。この閉じた循環構造により、末尾でのNULLチェックが不要になり、単一のループ内で連続したラップアラウンド走査が可能になります。

循環二重リンクリストは、各ノードに「next」と「prev」という2つのポインタを持ち、両端が互いにループしています。この構造は双方向の走査をサポートし、最悪の場合でもリスト長の半分以下の検索で済みます。

フロイドのウサギとカメのアルゴリズムは、異なる速度で移動する2つのポインタを使用します。2つのポインタが出会うと、サイクルが存在することになります。このアルゴリズムはO(n)の時間計算量とO(1)の追加メモリで動作し、サイクル検出に関する標準的な面接対策となっています。

循環連結リストの現在の位置への挿入または削除は、O(1) の時間で実行されます。 Opera特定の値やインデックスを対象とする処理は、対象ノードを見つけるためにリストを走査する必要があるため、O(n) で実行されます。

Operating-systemスケジューラは、ラウンドロビン方式のCPUスケジューリングにこれらを使用し、トークンリングネットワークはステーション間で制御を渡し、メディアプレーヤーはプレイリストを順番に再生し、組み込みシステムはセンサーストリーム用に循環リストをバックエンドとする循環バッファを使用します。

よくある間違いとしては、挿入または削除後に両方のエンドポイントポインタを更新するのを忘れること、終了条件を見落とすこと、そしてping 永久に、ノードを解放しても隣接ノードを再リンクせず、リストが破棄されるときにメモリリークが発生する。

循環リンクリスト: 利点と欠点

循環リンクリストとは何ですか?

Basic Opera循環連結リスト内の要素

挿入 Opera生産

削除 Opera生産

循環リンクリストの走査

循環リンクリストの利点

循環リンクリストの欠点

循環リンクリストとしての単一リンクリスト

循環リンクリストの応用

よくあるご質問

この投稿を要約すると次のようになります:

ニュースレターに登録する

循環リンクリストとは何ですか?

Basic Opera循環連結リスト内の要素

挿入 Opera生産

削除 Opera生産

関連記事

循環リンクリストの走査

循環リンクリストの利点

循環リンクリストの欠点

循環リンク リストとしての単一リンク リスト

循環リンクリストの応用

よくあるご質問

この投稿を要約すると次のようになります:

ニュースレターに登録する

循環リンクリストとしての単一リンクリスト