Меню

Структура даних кругового зв’язаного списку на C ++ з ілюстрацією

  • Головна
  • Інший
  • Структура даних кругового зв’язаного списку на C ++ з ілюстрацією

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) Вставте в кінець списку

останній вузол вказує на новий вузол

Щоб вставити новий вузол в кінці списку, виконуємо такі дії:

додаток для планування публікацій в Instagram безкоштовно

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 для операцій зв’язаного списку Circular.

//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

Переваги / недоліки

Давайте обговоримо деякі переваги та недоліки кругового пов'язаного списку.

Переваги:

  • Ми можемо перейти до будь-якого вузла і перейти з будь-якого вузла. Нам просто потрібно зупинитися, коли ми знову відвідаємо той самий вузол.
  • Оскільки останній вузол вказує на перший вузол, перехід до першого вузла з останнього вузла займає лише один крок.

Недоліки:

  • Зміна кругового пов'язаного списку є громіздкою.
  • Оскільки вузли з'єднані у коло, у списку немає належного позначення для початку чи кінця. Отже, важко знайти кінець списку або елемент управління. Якщо не піклуватися про це, реалізація може опинитися в нескінченному циклі.
  • Ми не можемо повернутися до попереднього вузла за один крок. Ми маємо пройти весь список спочатку.

Застосування кругового пов'язаного списку

  • Застосування кругового пов'язаного списку в режимі реального часу може бути операційною системою з декількома програмуваннями, в якій планується кілька програм. Кожній програмі призначається спеціальна позначка часу для виконання, після чого ресурси передаються іншій програмі. Це триває безперервно в циклі. Цього подання можна ефективно досягти за допомогою кругового пов'язаного списку.
  • Ігри, в які грають із кількома гравцями, також можуть бути представлені за допомогою кругового пов'язаного списку, в якому кожен гравець є вузлом, якому надається можливість грати.
  • Ми можемо використовувати круговий зв’язаний список для представлення кругової черги. Роблячи це, ми можемо зняти два вказівники спереду і ззаду, які використовуються для черги. Натомість ми можемо використовувати лише один покажчик.

Висновок

Круговий зв’язаний список - це сукупність вузлів, у яких вузли пов’язані між собою, утворюючи коло. Це означає, що замість того, щоб встановити для наступного вказівника останнього вузла значення 'нуль', він пов'язаний з першим вузлом.

Круговий зв’язаний список корисний для представлення структур або заходів, які потрібно повторювати знову і знову через певний інтервал часу, як програми в середовищі багатопрограмного програмування. Це також корисно для проектування кругової черги.

Кругові зв’язані списки підтримують різні операції, такі як вставка, видалення та обхід. Таким чином, ми детально розглянули операції в цьому посібнику.

У наступній темі про структури даних ми дізнаємося про структуру даних стеку.

=> Перегляньте тут, щоб побачити A-Z з навчальних посібників з C ++ тут.

Рекомендована література

^