circular linked list data structure c with illustration
循環リンクリストの完全な概要。
循環リンクリストは、リンクリストのバリエーションです。これは、ノードが円を形成するように接続されているリンクリストです。
循環リンクリストでは、最後のノードの次のポインタはnullに設定されていませんが、最初のノードのアドレスが含まれているため、円を形成します。
=> ゼロからC ++を学ぶには、ここにアクセスしてください。
学習内容：
C ++の循環リンクリスト
以下に示す配置は、単一リンクリスト用です。
循環リンクリストは、単一リンクリストまたは二重リンクリストにすることができます。二重循環リンクリストでは、最初のノードの前のポインタが最後のノードに接続され、最後のノードの次のポインタが最初のノードに接続されます。
その表現を以下に示します。
宣言
以下に示すように、循環リンクリスト内のノードを他のノードとして宣言できます。
struct Node { int data; struct Node *next; }; 循環リンクリストを実装するために、循環リンクリストの最後のノードを指す外部ポインタ「last」を維持します。したがって、last-> nextは、リンクリストの最初のノードを指します。
これを行うことにより、リストの最初または最後に新しいノードを挿入するときに、リスト全体をトラバースする必要がないようにします。これは、lastが最後のノードを指し、last-> nextが最初のノードを指すためです。
外部ポインタを最初のノードに向けていたら、これは不可能でした。
基本操作
循環リンクリストは、リストの挿入、削除、およびトラバースをサポートします。ここでは、それぞれの操作について詳しく説明します。
挿入
循環リンクリストにノードを最初のノード（空のリスト）として、最初、最後、または他のノードの間に挿入できます。以下の図を使用して、これらの挿入操作のそれぞれを見てみましょう。
＃1）空のリストに挿入する
循環リストにノードがなく、リストが空の場合、最後のポインターはnullです。次に、上記のように最後のポインターをノードNにポイントして、新しいノードNを挿入します。ノードは1つしかないため、Nの次のポインタはノードN自体を指します。したがって、Nはリストの最初と最後のノードになります。
＃2）リストの先頭に挿入
上記の表現に示されているように、リストの先頭にノードを追加すると、最後のノードの次のポインターが新しいノードNを指し、それによってそれが最初のノードになります。
N->次=最後->次
最後->次= N
＃3）リストの最後に挿入
リストの最後に新しいノードを挿入するには、次の手順に従います。
binファイルを開くにはどうすればよいですか
N->次=最後->次;
最後->次= N
最後= N
＃4）リストの間に挿入する
N3とN4の間に新しいノードNを挿入する必要があるとすると、最初にリストをトラバースして、新しいノードが挿入されるノード（この場合はそのN3）を見つける必要があります。
ノードが見つかったら、次の手順を実行します。
N->次= N3->次;
N3->次= N
これにより、N3の後に新しいノードNが挿入されます。
削除
循環リンクリストの削除操作には、削除するノードを見つけて、そのメモリを解放することが含まれます。
このために、currとprevの2つの追加ポインターを維持し、リストをトラバースしてノードを見つけます。削除する特定のノードは、最初のノード、最後のノード、またはその間のノードにすることができます。場所に応じて、currポインターとprevポインターを設定してから、currノードを削除します。
削除操作の図解を以下に示します。
トラバーサル
トラバーサルは、すべてのノードにアクセスする手法です。単一リンクリストや二重リンクリストなどの線形リンクリストでは、各ノードにアクセスし、NULLが検出されると停止するため、トラバーサルは簡単です。
ただし、これは循環リンクリストでは不可能です。循環リンクリストでは、最初のノードである最後のノードの次から開始し、各ノードをトラバースします。もう一度最初のノードに到達すると停止します。
ここで、C ++とJavaを使用した循環リンクリスト操作の実装を示します。ここでは、挿入、削除、およびトラバーサル操作を実装しました。明確に理解するために、循環リンクリストを次のように示しています。
したがって、最後のノード５０に、最初のノードであるノード１０を再び接続し、それによってそれを循環リンクリストとして示す。
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout < data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '< 出力：
作成される循環リンクリストは次のとおりです。
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
データ10のノードがリストから削除されます
10を削除した後の循環リンクリストは次のとおりです。
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
次に、Circularリンクリスト操作のJava実装を示します。
//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print('
'); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf('
Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } } 出力：
作成される循環リンクリストは次のとおりです。
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
40を削除した後、循環リストは次のようになります。
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
長所/短所
循環リンクリストのいくつかの長所と短所について説明しましょう。
利点：
- 任意のノードに移動して、任意のノードからトラバースできます。同じノードに再度アクセスしたときに停止する必要があります。
- 最後のノードが最初のノードを指しているので、最後のノードから最初のノードに移動するのは1つのステップだけです。
短所：
- 循環リンクリストを逆にするのは面倒です。
- ノードが接続されて円を形成しているため、リストの開始または終了を適切にマークすることはできません。したがって、リストまたはループ制御の終わりを見つけることは困難です。注意しないと、実装が無限ループになる可能性があります。
- 1つのステップで前のノードに戻ることはできません。最初からリスト全体をトラバースする必要があります。
循環リンクリストのアプリケーション
- 循環リンクリストのリアルタイムアプリケーションは、複数のプログラムをスケジュールするマルチプログラミングオペレーティングシステムにすることができます。各プログラムには、実行するための専用のタイムスタンプが与えられ、その後、リソースが別のプログラムに渡されます。これはサイクルで継続的に続きます。この表現は、循環リンクリストを使用して効率的に実現できます。
- 複数のプレーヤーでプレイされるゲームは、各プレーヤーがプレイする機会が与えられるノードである循環リンクリストを使用して表すこともできます。
- 循環リンクリストを使用して、循環キューを表すことができます。これにより、キューに使用されている前後の2つのポインターを削除できます。代わりに、使用できるポインターは1つだけです。
結論
循環リンクリストは、ノードが相互に接続されて円を形成するノードのコレクションです。これは、最後のノードの次のポインタをnullに設定する代わりに、最初のノードにリンクされることを意味します。
循環リンクリストは、マルチプログラミング環境のプログラムのように、特定の時間間隔の後に何度も繰り返す必要がある構造またはアクティビティを表すのに役立ちます。循環キューの設計にも役立ちます。
循環リンクリストは、挿入、削除、トラバーサルなどのさまざまな操作をサポートします。したがって、このチュートリアルでは操作について詳しく見てきました。
データ構造に関する次のトピックでは、スタックデータ構造について学習します。
=> ここでC ++トレーニングチュートリアルのA〜Zを確認するには、ここをクリックしてください。
推奨読書