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

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

循環リンクリストは、各ノードをそれ自身に遡ることができるように配置された一連のノードです。ここで、「ノード」は、すぐ近くにある XNUMX つまたは XNUMX つのノードへのポインターを持つ自己参照要素です。

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

ここで、各ノードがそれ自体に遡ることができることがわかります。上に示した例は、循環的な単一リンクリストです。

注: 最も単純な循環リンクリストは、図に示すように、それ自体のみをトレースするノードです。

Basic Opera循環リンクリスト内のオプション

循環リンクリストの基本的な操作は次のとおりです。

挿入
削除と
トラバーサル

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

次のセクションでは、ノードの挿入と、循環単一リンクリストで可能な挿入の種類について説明します。

挿入 Opera生産

最初に、この図に示すように、それ自体を指すノードを XNUMX つ作成する必要があります。このノードがない場合、挿入により最初のノードが作成されます。

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

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

循環リンクリストの先頭/末尾、つまり最初のノードが追加された位置に挿入する場合、

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

注: トークンマスターまたはサークルの開始/終了であるポインターは変更できます。前述のように、トラバースでは同じノードに戻ります。

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

(既存ノード)

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

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

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

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

たとえば、「VALUE2」のノードの後に「VALUE0」を挿入してみます。起点が「VALUE0」のノードであるとします。

最初のノードと 2 番目のノードの間の線を分割し、間に「VALUEXNUMX」を含むノードを配置する必要があります。
最初のノードの次のポインタはこのノードにリンクする必要があり、このノードの次のポインタは前の XNUMX 番目のノードにリンクする必要があります。
残りの配置は変更されません。すべてのノードはそれ自体まで遡ることができます。

注: 周期的な配置があるため、ノードの挿入にはどのノードでも同じ手順が必要です。サイクルを完了するポインタは、他のノードと同様にサイクルを完了します。

これを以下に示します。

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

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

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

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

削除 Opera生産

3 ノードの循環リンクリストを仮定します。削除対象となるケースは以下の通りです。

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

先頭/末尾の削除：

最後のノードから最初のノードまでトラバースします。
最後から削除するには、最後のノードから最初のノードまでの走査ステップが XNUMX つだけである必要があります。
最後のノードと次のノード間のリンクを削除します。
最後のノードを最初のノードの次の要素にリンクします。
最初のノードを解放します。

(既存のセットアップ)

ステップ 1) 循環リンクを削除します

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

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

ノードの後の削除:

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

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

ステップ2） 前のノードと現在のノード間のリンクを削除します。前のノードを、現在のノード (VALUE1 を使用) が指す次のノードにリンクします。

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

循環リンクリストの走査

循環リンクリストを最後のポインタからトラバースするには、最後のポインタ自体が NULL かどうかを確認します。この条件が偽の場合、要素が 1 つだけかどうかを確認します。それ以外の場合は、一時ポインタを使用して、最後のポインタに再び到達するまで、または以下の GIF に示すように必要な回数だけトラバースします。

循環リンクリストの利点

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

コード内で NULL を割り当てる必要はありません。循環リストは、完全に割り当てが解除されない限り、NULL ポインターを指すことはありません。
循環リンクリストは、開始と終了が一致するため、終了操作に有利です。 Algorithms ラウンドロビンスケジューリングなどでは、ダングリングポインタや NULL 参照ポインタに遭遇することなく、循環的にキューに入れられるプロセスを適切に排除できます。
循環リンクリストは、単一リンクリストのすべての通常の機能も実行します。実は円形二重連結リスト以下で説明するように、要素を見つけるために全長を走査する必要性を排除することもできます。その要素はせいぜい先頭のちょうど反対側にあるだけで、リンクされたリストの半分だけが完成します。

循環リンクリストの欠点

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

循環リストは、単一リンクリスト.
Rev循環リストの例は、単一リストや二重リストに比べて複雑です。
慎重に扱わないと、コードが無限ループに陥る可能性があります。
リストとループ制御の終わりを見つけるのが難しくなります。
開始位置に挿入すると、完全なリストを走査して最後のノードを見つける必要があります。（実装の視点）

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

以下のコードを読んで実装してみることをお勧めします。これは、循環リンクリストに関連付けられたポインター演算を示します。

#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)

コードの説明：

addEmpty コードの場合は、malloc 関数を使用して空のノードを割り当てます。
このノードの場合、データを temp 変数に配置します。
唯一の変数を一時変数に割り当ててリンクします。
最後の要素を 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;
…

コードの説明

挿入する要素がない場合は、必ず空のリストに追加して制御を返す必要があります。
現在の要素の後に配置する一時要素を作成します。
図のようにポインタをリンクします。
前の関数と同様に最後のポインターを返します。

...
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 ループ内のすべての反復で、最後に走査した結果を保持する前のポインターが存在することを確認します。
そうして初めて次の走査が可能になります。
データが見つかるか、temp が最後のポインターに戻ると、do-while は終了します。コードの次のセクションでは、項目に対して何を行う必要があるかを決定します。

...
    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 変数は XNUMX つのリンクを前方に移動するだけです。
最後のポインターを最初のポインターの後のポインターにリンクします。
一時ポインタを解放します。リンクされていない最後のポインタの割り当てを解除します。

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）が「next」として指すアドレスにリンクされます。
したがって、一時ポインタは割り当てが解除され、解放されます。

...
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;
    }
}