ВМЪКВАНЕ В КРЪГЪЛ ЕДИНИЧНО СВЪРЗАН СПИСЪК

В тази статия ще научим как да вмъкнем възел в кръгъл свързан списък. Вмъкването е основна операция в свързани списъци, която включва добавяне на нов възел към списъка. В кръгъл свързан списък последният възел се свързва обратно с първия възел, създавайки цикъл.

Има четири основни начина за добавяне на елементи:

Вмъкване в празен списък
Вмъкване в началото на списъка
Вмъкване в края на списъка
Вмъкване на конкретна позиция в списъка

Предимства от използването на показалеца на опашката вместо показалеца на главата

Трябва да обходим целия списък, за да вмъкнем възел в началото. Също така за вмъкване в края трябва да се премине през целия списък. Ако вместо на започнете указател вземаме указател към последния възел, тогава и в двата случая няма да има нужда да преминаваме през целия списък. Така че вмъкването в началото или в края отнема постоянно време, независимо от дължината на списъка.

javascript глобална променлива

1. Вмъкване в празен списък в кръговия свързан списък

За да вмъкнете възел в празен кръгъл свързан списък, създава a нов възел с дадените данни задава следващия си указател да сочи към себе си и актуализира последно указател към това нов възел .

Вмъкване в празен списък

Подход стъпка по стъпка:

Проверете дали последно не е nullptr . Ако вярно връщане последно (списъкът не е празен).
В противен случай Създайте a нов възел с предоставените данни.
- Задайте нови възли следващ указател, който да сочи към себе си (кръгова връзка).
- Актуализация последно да посочи към нов възел и го върнете.

За да прочетете повече за вмъкването в празен списък, вижте: Вмъкване в празен списък в кръговия свързан списък

2. Вмъкване в началото на кръгъл свързан списък

За да вмъкнете нов възел в началото на кръгъл свързан списък
Първо създаваме нов възел и разпределете памет за него.
Ако списъкът е празен (обозначено с последния показалец, който е NULL ) ние правим нов възел сочи към себе си.
Ако списъкът вече съдържа възли, тогава задаваме нови възли следващия указател, който да сочи към текуща глава от списъка (което е последно->следващо )
След това актуализирайте следващия указател на последния възел, за да сочи към нов възел . Това поддържа кръговата структура на списъка.

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

Вмъкване в началото на кръгъл свързан списък

За да прочетете повече за вмъкването в началото, вижте: Вмъкване в началото на кръгъл свързан списък

3. Вмъкване в края на кръгъл свързан списък

За да вмъкнем нов възел в края на кръгъл свързан списък, първо създаваме новия възел и заделяме памет за него.
Ако списъкът е празен (означава последно или опашка указател е NULL ) ние инициализираме списъка с нов възел и го насочва към себе си, за да образува кръгла структура.
Ако списъкът вече съдържа възли, тогава задаваме нови възли следващия указател, който да сочи към текуща глава (което е опашка->следващ )
След това актуализирайте текущи опашки следващия указател, който да сочи към нов възел .
Най-накрая актуализираме показалец на опашката към нов възел.
Това ще гарантира, че нов възел сега е последен възел в списъка при запазване на кръговата връзка.

Вмъкване в края на кръгъл свързан списък

За да прочетете повече за вмъкването в края, вижте: Вмъкване в края на кръгъл свързан списък

4. Вмъкване на конкретна позиция в кръгъл свързан списък

За да вмъкнем нов възел на конкретна позиция в кръгъл свързан списък, първо проверяваме дали списъкът е празен.
java ламбда изрази
Ако е и на позиция не е 1 след това отпечатваме съобщение за грешка, защото позицията не съществува в списъка. аз
е позиция е 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

Вмъкване в кръгъл единично свързан списък