circular linked list data structure c with illustration
순환 연결 목록의 전체 개요.
순환 연결 목록은 연결 목록의 변형입니다. 노드가 원을 형성하는 방식으로 연결된 연결 목록입니다.
순환 연결 목록에서 마지막 노드의 다음 포인터는 null로 설정되지 않지만 첫 번째 노드의 주소를 포함하여 원을 형성합니다.
=> 처음부터 C ++를 배우려면 여기를 방문하십시오.
학습 내용 :
C ++의 순환 연결 목록
아래 표시된 배열은 단일 연결 목록에 대한 것입니다.
순환 연결 목록은 단일 연결 목록 또는 이중 연결 목록 일 수 있습니다. 이중 순환 연결 목록에서 첫 번째 노드의 이전 포인터는 마지막 노드에 연결되고 마지막 노드의 다음 포인터는 첫 번째 노드에 연결됩니다.
그 표현은 아래와 같습니다.
선언
순환 연결 목록의 노드를 아래와 같이 다른 노드로 선언 할 수 있습니다.
struct Node { int data; struct Node *next; }; 순환 연결 목록을 구현하기 위해 순환 연결 목록의 마지막 노드를 가리키는 외부 포인터 'last'를 유지합니다. 따라서 last-> next는 연결 목록의 첫 번째 노드를 가리 킵니다.
이렇게하면 목록의 시작 부분이나 끝에 새 노드를 삽입 할 때 전체 목록을 탐색 할 필요가 없습니다. 이는 마지막 노드가 마지막 노드를 가리키고 last-> next가 첫 번째 노드를 가리 키기 때문입니다.
외부 포인터를 첫 번째 노드로 가리켰다면 불가능했을 것입니다.
기본 작동
순환 연결 목록은 목록의 삽입, 삭제 및 순회를 지원합니다. 이제 각 작업에 대해 자세히 설명하겠습니다.
삽입
순환 연결 목록에 노드를 첫 번째 노드 (빈 목록), 시작, 끝 또는 다른 노드 사이에 삽입 할 수 있습니다. 아래의 그림 표현을 사용하여 이러한 각 삽입 작업을 살펴 보겠습니다.
# 1) 빈 목록에 삽입
순환 목록에 노드가없고 목록이 비어있는 경우 마지막 포인터가 null 인 경우 위에 표시된대로 마지막 포인터를 노드 N에 지정하여 새 노드 N을 삽입합니다. N의 다음 포인터는 노드가 하나뿐이므로 노드 N 자체를 가리 킵니다. 따라서 N은 목록의 첫 번째 노드이자 마지막 노드가됩니다.
# 2) 목록 시작 부분에 삽입
위의 표현에서 볼 수 있듯이 목록의 시작 부분에 노드를 추가하면 마지막 노드의 다음 포인터가 새 노드 N을 가리 키므로 첫 번째 노드가됩니다.
N-> 다음 = 마지막-> 다음
마지막-> 다음 = N
# 3) 목록 끝에 삽입
목록 끝에 새 노드를 삽입하려면 다음 단계를 따릅니다.
사용하기에 가장 좋은 이메일은 무엇입니까
N-> 다음 = 마지막-> 다음;
마지막-> 다음 = N
마지막 = N
# 4) 목록 사이에 삽입
N3과 N4 사이에 새 노드 N을 삽입해야한다고 가정하면 먼저 목록을 탐색하고 새 노드가 삽입 될 노드 (이 경우에는 N3)를 찾아야합니다.
노드를 찾은 후 다음 단계를 수행합니다.
N-> 다음 = N3-> 다음;
N3-> 다음 = N
그러면 N3 뒤에 새 노드 N이 삽입됩니다.
삭제
순환 연결 목록의 삭제 작업에는 삭제할 노드를 찾은 다음 해당 메모리를 해제하는 작업이 포함됩니다.
이를 위해 curr 및 prev 두 개의 추가 포인터를 유지 한 다음 목록을 탐색하여 노드를 찾습니다. 삭제할 주어진 노드는 첫 번째 노드, 마지막 노드 또는 그 사이의 노드 일 수 있습니다. 위치에 따라 curr 및 prev 포인터를 설정 한 다음 curr 노드를 삭제합니다.
삭제 작업의 그림 표현은 아래와 같습니다.
순회
순회는 각 노드를 방문하는 기술입니다. 단일 연결 목록 및 이중 연결 목록과 같은 선형 연결 목록에서는 각 노드를 방문하고 NULL이 발생하면 중지하므로 순회가 쉽습니다.
그러나 순환 연결 목록에서는 불가능합니다. 순환 연결 목록에서 첫 번째 노드 인 마지막 노드의 다음 노드부터 시작하여 각 노드를 순회합니다. 다시 한 번 첫 번째 노드에 도달하면 멈 춥니 다.
이제 C ++ 및 Java를 사용한 순환 연결 목록 작업의 구현을 보여줍니다. 여기에 삽입, 삭제 및 순회 작업을 구현했습니다. 명확한 이해를 위해 순환 연결 목록을 다음과 같이 묘사했습니다.
따라서 마지막 노드 (50)에 다시 첫 번째 노드 인 노드 (10)를 연결하여 순환 연결 목록으로 표시합니다.
#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
다음으로 순환 연결 목록 작업을위한 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
장점 단점
순환 연결 목록의 장점과 단점에 대해 설명하겠습니다.
장점 :
- 모든 노드로 이동하여 모든 노드에서 트래버스 할 수 있습니다. 같은 노드를 다시 방문 할 때 중지하면됩니다.
- 마지막 노드가 첫 번째 노드를 가리 키므로 마지막 노드에서 첫 번째 노드로 이동하는 것은 한 단계 만 거치면됩니다.
단점 :
- 순환 연결 목록을 되 돌리는 것은 번거 롭습니다.
- 노드가 연결되어 원을 형성하기 때문에 목록의 시작 또는 끝에 대한 적절한 표시가 없습니다. 따라서 목록 또는 루프 제어의 끝을 찾기가 어렵습니다. 주의하지 않으면 구현이 무한 루프로 끝날 수 있습니다.
- 한 번에 이전 노드로 돌아갈 수 없습니다. 우리는 처음부터 전체 목록을 탐색해야합니다.
순환 연결 목록의 응용
- 순환 연결 목록의 실시간 적용은 여러 프로그램을 예약하는 다중 프로그래밍 운영 체제 일 수 있습니다. 각 프로그램에는 리소스가 다른 프로그램으로 전달 된 후 실행할 전용 타임 스탬프가 제공됩니다. 이것은 주기적으로 지속적으로 진행됩니다. 이 표현은 순환 연결 목록을 사용하여 효율적으로 달성 할 수 있습니다.
- 여러 플레이어와 함께 플레이하는 게임은 각 플레이어가 플레이 할 기회가 주어진 노드 인 순환 연결 목록을 사용하여 나타낼 수도 있습니다.
- 순환 연결 목록을 사용하여 순환 대기열을 나타낼 수 있습니다. 이렇게하면 대기열에 사용되는 앞뒤 두 개의 포인터를 제거 할 수 있습니다. 대신 하나의 포인터 만 사용할 수 있습니다.
결론
순환 연결 목록은 노드가 서로 연결되어 원을 형성하는 노드 모음입니다. 즉, 마지막 노드의 다음 포인터를 null로 설정하는 대신 첫 번째 노드에 연결됩니다.
순환 연결 목록은 다중 프로그래밍 환경의 프로그램과 같이 특정 시간 간격 후에 반복해야하는 구조 또는 활동을 나타내는 데 유용합니다. 순환 대기열을 디자인하는데도 유용합니다.
순환 연결 목록은 삽입, 삭제 및 순회와 같은 다양한 작업을 지원합니다. 따라서이 튜토리얼에서 작업을 자세히 살펴 보았습니다.
데이터 구조에 대한 다음 주제에서는 스택 데이터 구조에 대해 배웁니다.
=> 여기에서 C ++ 교육 자습서의 A-Z를 보려면 여기를 확인하십시오.
추천 도서