circular linked list data structure c with illustration
Пълен преглед на циркулярно свързан списък.
Кръговият свързан списък е вариант на свързания списък. Това е свързан списък, чиито възли са свързани по такъв начин, че да образува кръг.
В списъка с кръгови връзки следващият указател на последния възел не е зададен за нула, но съдържа адреса на първия възел, като по този начин образува кръг.
=> Посетете тук, за да научите C ++ от нулата.
Какво ще научите:
Кръгово свързан списък в C ++
Устройството, показано по-долу, е за еднократно свързан списък.
Кръгово свързан списък може да бъде единично свързан списък или двойно свързан списък. В двойно кръгово свързан списък предишният указател на първия възел е свързан с последния възел, докато следващият указател на последния възел е свързан с първия възел.
Неговото представяне е показано по-долу.
Декларация
Можем да декларираме възел в кръгово свързан списък като всеки друг възел, както е показано по-долу:
struct Node { int data; struct Node *next; };
За да приложим циркулярно свързан списък, ние поддържаме външен указател „последен“, който сочи към последния възел в циркулярно свързания списък. Следователно last-> next ще сочи към първия възел в свързания списък.
Правейки това, ние гарантираме, че когато вмъкваме нов възел в началото или в края на списъка, не е необходимо да обхождаме целия списък. Това е така, защото последният сочи към последния възел, докато последният-> следващия сочи към първия възел.
Това не би било възможно, ако бяхме насочили външния указател към първия възел.
Основни операции
Кръговият свързан списък поддържа вмъкване, изтриване и обръщане на списъка. Сега ще обсъдим подробно всяка от операциите.
Вмъкване
Можем да вмъкнем възел в кръгово свързан списък или като първи възел (празен списък), в началото, в края или между останалите възли. Нека да видим всяка от тези операции за вмъкване, използвайки изобразително изображение по-долу.
# 1) Вмъкнете в празен списък
Когато в кръговия списък няма възли и списъкът е празен, последният указател е нула, тогава ние вмъкваме нов възел N, като насочваме последния указател към възела N, както е показано по-горе. Следващият указател на N ще сочи към самия възел N, тъй като има само един възел. Така N става първият, както и последният възел в списъка.
# 2) Поставете в началото на списъка
Както е показано в горното представяне, когато добавяме възел в началото на списъка, следващият указател на последния възел сочи към новия възел N, като по този начин го прави първи възел.
N-> следващ = последен-> следващ
Последно-> следващо = N
# 3) Поставете в края на списъка
За да вмъкнете нов възел в края на списъка, следваме следните стъпки:
жизнен цикъл на развитие на системата на водопада
N-> следващ = последен -> следващ;
последно -> следващо = N
последно = N
# 4) Поставете между списъка
Да предположим, че трябва да вмъкнем нов възел N между N3 и N4, първо трябва да прекосим списъка и да намерим възела, след който трябва да се вмъкне новия възел, в този случай неговия N3.
След като възелът бъде локализиран, изпълняваме следните стъпки.
N -> следващ = N3 -> следващ;
N3 -> следващ = N
Това вмъква нов възел N след N3.
Изтриване
Операцията за изтриване на кръгово свързан списък включва намиране на възела, който трябва да бъде изтрит, и след това освобождаване на паметта му.
За това поддържаме два допълнителни указателя 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, той е свързан с първия възел.
Циклично свързан списък е полезен при представяне на структури или дейности, които трябва да се повтарят отново и отново след определен интервал от време, като програми в среда за многопрограмиране. Също така е полезно за проектиране на кръгова опашка.
Циркулярно свързани списъци поддържат различни операции като вмъкване, изтриване и обхождане. По този начин видяхме операциите подробно в този урок.
В следващата ни тема за структурите на данни ще научим за структурата на стека данни.
=> Проверете тук, за да видите A-Z на C ++ уроци за обучение тук.
Препоръчително четене
- Свързана структура на списъка с данни в C ++ с илюстрация
- Структура на данните от двойно свързан списък в C ++ с илюстрация
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните за стека в C ++ с илюстрация
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Топ 15 най-добри безплатни инструменти за извличане на данни: Най-изчерпателният списък
- Въведение в структурите на данни в C ++
- 15 най-добри ETL инструмента през 2021 г. (Пълен актуализиран списък)