ВСТАВКА В ЦИКЛІЧНИЙ ОДНОЗВ’ЯЗАНИЙ СПИСОК

У цій статті ми навчимося вставляти вузол у циклічний пов’язаний список. Вставка — це фундаментальна операція у зв’язаних списках, яка передбачає додавання нового вузла до списку. У циклічному пов’язаному списку останній вузол з’єднується з першим вузлом, створюючи цикл.

Є чотири основні способи додавання елементів:

Вставка в порожній список
Вставка на початку списку
Вставка в кінці списку
Вставка в певну позицію в списку

Переваги використання покажчика хвоста замість покажчика голови

Нам потрібно пройти весь список, щоб вставити вузол на початку. Крім того, для вставки в кінці потрібно пройти весь список. Якщо замість початок pointer ми беремо вказівник на останній вузол, тоді в обох випадках не буде необхідності проходити весь список. Таким чином, вставка на початку чи в кінці займає постійний час, незалежно від довжини списку.

1. Вставлення в порожній список у циклічному пов’язаному списку

Щоб вставити вузол у порожній циклічний пов’язаний список, створюється a новий вузол із заданими даними встановлює свій наступний вказівник на себе та оновлює останній покажчик для посилання на це новий вузол .

Вставлення-в-порожній-список-у-круговому-зв'язаному-списку' title=

Вставка в порожній список

Покроковий підхід:

Перевірте, якщо останній не є nullptr . Якщо правда повернення останній (список не порожній).
В іншому випадку Створіть a новий вузол з наданими даними.
- Встановіть новий вузол наступний покажчик, який вказує на себе (циклове посилання).
- оновлення останній вказувати на новий вузол і повернути його.

Щоб дізнатися більше про вставлення в порожній список, див. Вставлення в порожній список у циклічному пов’язаному списку

2. Вставка на початку кільцевого пов’язаного списку

Щоб вставити новий вузол на початку циклічного пов’язаного списку
diff у python
Спочатку ми створюємо новий вузол і виділити для нього пам'ять.
Якщо список порожній (позначається останнім покажчиком NULL ) ми робимо новий вузол вказувати на себе.
Якщо список уже містить вузли, ми встановлюємо новий вузол наступний покажчик, щоб вказати на діючий зав списку (що є останній->наступний )
Потім оновіть наступний покажчик останнього вузла, щоб вказувати на новий вузол . Це зберігає циклічну структуру списку.

Вставка-на-початку-круглого-зв'язаного-списку' loading='lazy' title=

Вставка на початку кільцевого пов’язаного списку

Щоб дізнатися більше про вставку на початку, зверніться до: Вставка на початку кільцевого пов’язаного списку

3. Вставка в кінець циклічного пов’язаного списку

Щоб вставити новий вузол у кінець циклічного пов’язаного списку, ми спочатку створюємо новий вузол і виділяємо для нього пам’ять.
Якщо список порожній (знач останній або хвіст покажчик істоти NULL ) ми ініціалізуємо список за допомогою новий вузол і змушуючи його вказувати на себе, щоб утворити круглу структуру.
Якщо список уже містить вузли, ми встановлюємо новий вузол наступний покажчик, щоб вказати на діючий зав (що є хвіст->наступний )
Потім оновіть поточний хвіст наступний покажчик, щоб вказати на новий вузол .
Нарешті ми оновлюємо вказівник хвоста до новий вузол.
Це гарантує, що новий вузол зараз це останній вузол у списку, зберігаючи круговий зв’язок.

Вставка-на-кінець-круглого-зв’язаного-списку' loading='lazy' title=

Вставка в кінець кільцевого пов’язаного списку

Щоб дізнатися більше про вставку в кінці, зверніться до: Вставка в кінець кільцевого пов’язаного списку

4. Вставлення в конкретну позицію в циклічному пов’язаному списку

Щоб вставити новий вузол у певну позицію в циклічному пов’язаному списку, ми спочатку перевіряємо, чи список порожній.
Якщо це і є положення не є 1 тоді ми друкуємо повідомлення про помилку, оскільки позиції немає в списку. я
f положення є 1 тоді ми створюємо новий вузол і змусити його вказувати на себе.
Якщо список не порожній, ми створюємо новий вузол і перегляньте список, щоб знайти правильну точку вставки.
Якщо положення є 1 ми вставляємо новий вузол на початку, відповідно налаштувавши покажчики.
Для інших позицій ми переходимо по списку, поки не досягнемо потрібної позиції та вставимо новий вузол шляхом оновлення покажчиків.
Якщо новий вузол вставлено в кінці, ми також оновлюємо останній покажчик для посилання на новий вузол, зберігаючи циклічну структуру списку.

Вставка-на-конкретну-позицію-кільцевого-зв’язаного-списку' loading='lazy' title=

Вставлення в конкретну позицію в циклічному пов’язаному списку

Покроковий підхід:

назви міст США

Якщо останній є nullptr і поз не є 1 друкувати Недійсна позиція! '.
В іншому випадку створіть новий вузол із заданими даними.
Вставити на початку: Якщо pos дорівнює 1, оновіть покажчики та поверніть останні.
Список траверсу: Петля для пошуку точки вставки; print 'Невірна позиція!' якщо поза межами.
Вставити вузол: Оновіть покажчики, щоб вставити новий вузол.
Останнє оновлення: Якщо вставлено в кінці оновлення останній .

C++

#include    using namespace std; struct Node{  int data;  Node *next;  Node(int value){  data = value;  next = nullptr;  } }; // Function to insert a node at a specific position in a circular linked list Node *insertAtPosition(Node *last int data int pos){  if (last == nullptr){  // If the list is empty  if (pos != 1){  cout << 'Invalid position!' << endl;  return last;  }  // Create a new node and make it point to itself  Node *newNode = new Node(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  Node *newNode = new Node(data);  // curr will point to head initially  Node *curr = last->next;  if (pos == 1){  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;    // If position is out of bounds  if (curr == last->next){  cout << 'Invalid position!' << endl;  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } void printList(Node *last){  if (last == NULL) return;  Node *head = last->next;  while (true){  cout << head->data << ' ';  head = head->next;  if (head == last->next) break;  }  cout << endl; } int main(){  // Create circular linked list: 2 3 4  Node *first = new Node(2);  first->next = new Node(3);  first->next->next = new Node(4);  Node *last = first->next->next;  last->next = first;  cout << 'Original list: ';  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  cout << 'List after insertions: ';  printList(last);  return 0; }

#include  #include  // Define the Node structure struct Node {  int data;  struct Node *next; }; struct Node* createNode(int value); // Function to insert a node at a specific position in a circular linked list struct Node* insertAtPosition(struct Node *last int data int pos) {  if (last == NULL) {  // If the list is empty  if (pos != 1) {  printf('Invalid position!n');  return last;  }  // Create a new node and make it point to itself  struct Node *newNode = createNode(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  struct Node *newNode = createNode(data);  // curr will point to head initially  struct Node *curr = last->next;  if (pos == 1) {  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;  // If position is out of bounds  if (curr == last->next) {  printf('Invalid position!n');  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } // Function to print the circular linked list void printList(struct Node *last) {  if (last == NULL) return;  struct Node *head = last->next;  while (1) {  printf('%d ' head->data);  head = head->next;  if (head == last->next) break;  }  printf('n'); } // Function to create a new node struct Node* createNode(int value) {  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  newNode->data = value;  newNode->next = NULL;  return newNode; } int main() {  // Create circular linked list: 2 3 4  struct Node *first = createNode(2);  first->next = createNode(3);  first->next->next = createNode(4);  struct Node *last = first->next->next;  last->next = first;  printf('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  printf('List after insertions: ');  printList(last);  return 0; }

Java

class Node {  int data;  Node next;  Node(int value){  data = value;  next = null;  } } public class GFG {  // Function to insert a node at a specific position in a  // circular linked list  static Node insertAtPosition(Node last int data  int pos){  if (last == null) {  // If the list is empty  if (pos != 1) {  System.out.println('Invalid position!');  return last;  }  // Create a new node and make it point to itself  Node newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  Node newNode = new Node(data);  // curr will point to head initially  Node curr = last.next;  if (pos == 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr == last.next) {  System.out.println('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the  // end  if (curr == last)  last = newNode;  return last;  }  static void printList(Node last){  if (last == null)  return;  Node head = last.next;  while (true) {  System.out.print(head.data + ' ');  head = head.next;  if (head == last.next)  break;  }  System.out.println();  }  public static void main(String[] args)  {  // Create circular linked list: 2 3 4  Node first = new Node(2);  first.next = new Node(3);  first.next.next = new Node(4);  Node last = first.next.next;  last.next = first;  System.out.print('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  System.out.print('List after insertions: ');  printList(last);  } }

Python

class Node: def __init__(self value): self.data = value self.next = None # Function to insert a node at a specific position in a circular linked list def insertAtPosition(last data pos): if last is None: # If the list is empty if pos != 1: print('Invalid position!') return last # Create a new node and make it point to itself new_node = Node(data) last = new_node last.next = last return last # Create a new node with the given data new_node = Node(data) # curr will point to head initially curr = last.next if pos == 1: # Insert at the beginning new_node.next = curr last.next = new_node return last # Traverse the list to find the insertion point for i in range(1 pos - 1): curr = curr.next # If position is out of bounds if curr == last.next: print('Invalid position!') return last # Insert the new node at the desired position new_node.next = curr.next curr.next = new_node # Update last if the new node is inserted at the end if curr == last: last = new_node return last # Function to print the circular linked list def print_list(last): if last is None: return head = last.next while True: print(head.data end=' ') head = head.next if head == last.next: break print() if __name__ == '__main__': # Create circular linked list: 2 3 4 first = Node(2) first.next = Node(3) first.next.next = Node(4) last = first.next.next last.next = first print('Original list: ' end='') print_list(last) # Insert elements at specific positions data = 5 pos = 2 last = insertAtPosition(last data pos) print('List after insertions: ' end='') print_list(last)

JavaScript

class Node {  constructor(value){  this.data = value;  this.next = null;  } } // Function to insert a node at a specific position in a // circular linked list function insertAtPosition(last data pos) {  if (last === null) {  // If the list is empty  if (pos !== 1) {  console.log('Invalid position!');  return last;  }  // Create a new node and make it point to itself  let newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  let newNode = new Node(data);  // curr will point to head initially  let curr = last.next;  if (pos === 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (let i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr === last.next) {  console.log('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the end  if (curr === last)  last = newNode;  return last; } // Function to print the circular linked list function printList(last){  if (last === null)  return;  let head = last.next;  while (true) {  console.log(head.data + ' ');  head = head.next;  if (head === last.next)  break;  }  console.log(); } // Create circular linked list: 2 3 4 let first = new Node(2); first.next = new Node(3); first.next.next = new Node(4); let last = first.next.next; last.next = first; console.log('Original list: '); printList(last); // Insert elements at specific positions let data = 5; let pos = 2; last = insertAtPosition(last data pos); console.log('List after insertions: '); printList(last);

Вихід

Original list: 2 3 4 List after insertions: 2 5 3 4

Часова складність: O(n) ми повинні пройти список, щоб знайти конкретну позицію.
Допоміжний простір: О(1)

Створіть вікторину

TechCodeview

Вставка в циклічний однозв’язаний список