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

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

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

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

循環リンクリスト

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

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

循環リンクリスト

循環リンクリストの基本操作

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

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

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

挿入操作

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

挿入操作

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

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

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

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

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

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

挿入操作

(既存ノード)

挿入操作

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

挿入操作

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

挿入操作

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

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

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

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

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

これを以下に示します。

挿入操作

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

挿入操作

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

挿入操作

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

挿入操作

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

削除操作

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

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

先頭/末尾の削除:

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

削除操作

(既存のセットアップ)

削除操作

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

削除操作

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

削除操作

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

ノードの後の削除:

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

削除操作

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

削除操作

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

削除操作

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

循環リンクリストの走査

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

循環リンクリストの走査

循環リンクリストの利点

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

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

循環リンクリストの欠点

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

  1. 循環リストは complex と比較して 単一リンクリスト.
  2. 循環リストの逆はcomですplex 単一リストまたは二重リストと比較して。
  3. 慎重に扱わないと、コードが無限ループに陥る可能性があります。
  4. リストとループ制御の終わりを見つけるのが難しくなります。
  5. 開始位置に挿入すると、完全なリストを走査して最後のノードを見つける必要があります。 (実装の視点)

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

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

#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()
{
...

単方向リスト

コードの説明:

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

単方向リスト

コードの説明:

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

単方向リスト

コードの説明

  1. 挿入する要素がない場合は、必ず空のリストに追加して制御を返す必要があります。
  2. 現在の要素の後に配置する一時要素を作成します。
  3. 図のようにポインタをリンクします。
  4. 前の関数と同様に最後のポインターを返します。
...
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");
...

単方向リスト

コードの説明:

  1. リストに要素がない場合は、データを無視し、現在の項目をリストの最後の項目として追加し、制御を返します。
  2. do-while ループ内のすべての反復で、最後に走査した結果を保持する前のポインターが存在することを確認します。
  3. そうして初めて次の走査が可能になります。
  4. データが見つかるか、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)
...

単方向リスト

コードの説明:

  1. リスト全体を調べても項目が見つからない場合は、「項目が見つかりません」というメッセージを表示して、呼び出し元に制御を返します。
  2. ノードが見つかった場合、またはそのノードがまだ最後のノードではない場合は、新しいノードを作成します。
  3. リンク 以前のノードと新しいノード。 現在のノードを temp (トラバーサル変数) にリンクします。
  4. これにより、要素が循環リンク リスト内の特定のノードの後に​​配置されるようになります。 発信者に戻ります。
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)

単方向リスト

コードの説明

  1. 最後の (現在の) ノードのみを削除するには、このリストが空かどうかを確認します。 存在する場合、要素は削除できません。
  2. temp 変数は XNUMX つのリンクを前方に移動するだけです。
  3. 最後のポインターを最初のポインターの後のポインターにリンクします。
  4. 一時ポインタを解放します。 リンクされていない最後のポインタの割り当てを解除します。
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");
...

単方向リスト

コードの説明

  1. 先ほどの削除機能と同様に、要素がないか確認します。 これが真の場合、要素は削除できません。
  2. ポインタ 削除する要素を見つけるために特定の位置が割り当てられます。
  3. ポインタは順番に進みます。 (前の温度の後ろ)
  4. このプロセスは、要素が見つかるか、次の要素が最後のポインターに戻るまで続行されます。
    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;	

単方向リスト

プログラムの説明

  1. リンクされたリスト全体を走査した後に要素が見つかった場合は、項目が見つからなかったことを示すエラー メッセージが表示されます。
  2. その他wiseの場合、要素はステップ 3 と 4 でリンクが解除され、解放されます。
  3. 前ポインタは、削除対象の要素(temp)が「next」として指すアドレスにリンクされます。
  4. したがって、一時ポインタは割り当てが解除され、解放されます。
...
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. 必要なものがゼロの場合、ピークまたはトラバースは不可能です。 ユーザーはノードを割り当てるか挿入する必要があります。
  2. ノードが XNUMX つしかない場合は、トラバースする必要はなく、ノードのコンテンツを出力でき、while ループは実行されません。
  3. 複数のノードがある場合、temp は最後の要素までのすべての項目を出力します。
  4. 最後の要素に到達した瞬間にループは終了し、関数は main 関数への呼び出しを返します。

循環リンクリストの応用

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