Circular Linked List にノードを挿入する方法は? C++


Circular Linked List は Linked List のバリエーションで、最初と最後のノードも互いにリンクされて円を形成します.通常の連結リストでは、最終ノードのネクスト ポインタは NULL を指しますが、循環連結リストの場合、最終ノードのネクスト ポインタはリストの先頭を指します.

Circular Linked List は、任意のノードが開始ノードとして機能し、任意のノードから開始してリスト全体をトラバースできるため、リスト内のトラバースをより効率的にします.また、最後のノードとヘッド ノードが接続されているため、エンキューやデキューなどの操作を実行しやすくなります.


Circular Linked List の先頭への挿入

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};
// Inserts at the head of the list
void insertAtFront(Node*& head, int info)
{
    Node* newnode = new Node(info); // Create a new node

    if (head
        == NULL) // if the list has not been created yet
    {
        newnode->next = newnode;
        head = newnode;
        return;
    }
    Node* temp = head; // Creating a pointer for traversal

    while (temp->next != head) //traversing until the first node is encountered again
    {
        temp = temp->next;
    }
    temp->next = newnode;
    newnode->next = head;
    head = newnode;
}



リストの最後に挿入

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};

// Inserts at the tail of the list
void insertAtEnd(Node*& head, int info)
{

    if (head == NULL) {
        insertAtFront(head, info);
        return;
    }

    Node* newnode = new Node(info);
    Node* temp = head; //Creating a pointer for traversal

    while (temp->next != head) //traversing until the first node is encountered again
    {
        temp = temp->next;
    }

    temp->next = newnode;
    newnode->next = head;
}



Circular List の途中への挿入は、通常の Linked List と同じアプローチに従います. here で確認できます.


以下は、上記の Circular リンク リストへの挿入と表示の両方の方法を使用する完全なプログラムです.

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};
// Inserts at the head of the list
void insertAtFront(Node*& head, int info)
{
    Node* newnode = new Node(info);

    if (head == NULL) {
        newnode->next = newnode;
        head = newnode;
        return;
    }
    Node* temp = head;

    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newnode;
    newnode->next = head;
    head = newnode;
}
// Inserts at the tail of the list
void insertAtEnd(Node*& head, int info)
{

    if (head == NULL) {
        insertAtFront(head, info);
        return;
    }

    Node* newnode = new Node(info);
    Node* temp = head;

    while (temp->next != head) {
        temp = temp->next;
    }

    temp->next = newnode;
    newnode->next = head;
}

void displaylist(Node* head)
{

    Node* temp = head;
    do {
        cout << temp->data << " ";
        temp = temp->next;
    } while (temp != head);
    cout << endl;
}

int main()
{
    Node* head = NULL;
    insertAtEnd(head, 1);
    insertAtEnd(head, 2);
    insertAtEnd(head, 3);
    insertAtEnd(head, 4);
    insertAtFront(head, 5);
    insertAtFront(head, 6);
    displaylist(head); 
}