ĮTERPIMAS Į ŽIEDINĮ ATSKIRAI SUSIETĄ SĄRAŠĄ

Šiame straipsnyje sužinosime, kaip įterpti mazgą į apskritą susietą sąrašą. Įterpimas yra pagrindinė susietų sąrašų operacija, kuri apima naujo mazgo įtraukimą į sąrašą. Apvaliame susietame sąraše paskutinis mazgas vėl prisijungia prie pirmojo mazgo ir sukuria kilpą.

Yra keturi pagrindiniai elementų pridėjimo būdai:

Įterpimas į tuščią sąrašą
Įterpimas sąrašo pradžioje
Įterpimas sąrašo pabaigoje
Įterpimas į konkrečią sąrašo vietą

Uodegos rodyklės, o ne galvos rodyklės, naudojimo pranašumai

Turime pereiti visą sąrašą, kad įterptume mazgą pradžioje. Taip pat norint įterpti į pabaigą, reikia perbraukti visą sąrašą. Jei vietoj pradėti žymeklį perkeliame į paskutinį mazgą, tada abiem atvejais nereikės kirsti viso sąrašo. Taigi įterpimas į pradžią arba pabaigą trunka pastoviai, nepriklausomai nuo sąrašo ilgio.

1. Įterpimas į tuščią sąrašą apskrito susieto sąrašo

Norėdami įterpti mazgą į tuščią apskritą susietų sąrašą, sukuriamas a naujas mazgas su pateiktais duomenimis nustato kitą žymeklį, nukreipiantį į save, ir atnaujina paskutinis nuoroda į tai naujas mazgas .

Įterpimas į tuščią sąrašą

Žingsnis po žingsnio metodas:

Patikrinkite, ar paskutinis nėra nullptr . Jeigu tiesa grąžinti paskutinis (sąrašas nėra tuščias).
Kitu atveju sukurkite a naujas mazgas su pateiktais duomenimis.
- Nustatykite nauji mazgai kitas žymeklis, rodantis į save (apvali nuoroda).
- Atnaujinti paskutinis nurodyti į naujas mazgas ir grąžinti.

Norėdami sužinoti daugiau apie įterpimą į tuščią sąrašą, žr. Įterpimas į tuščią sąrašą apskrito susieto sąrašo

2. Įterpimas apskrito susieto sąrašo pradžioje

Norėdami įterpti naują mazgą apskrito susieto sąrašo pradžioje
Pirmiausia sukuriame naujas mazgas ir paskirstykite jam atmintį.
Jei sąrašas tuščias (nurodomas paskutinis žymeklis NULL ) gaminame naujas mazgas rodo į save.
Jei sąraše jau yra mazgų, nustatome nauji mazgai kitas žymeklis, nurodantis į dabartinė galva sąrašo (tai yra paskutinis->kitas )
Tada atnaujinkite kitą paskutinio mazgo žymeklį, kad nukreiptumėte į naujas mazgas . Taip išlaikoma apskrita sąrašo struktūra.

Insertion-at-the-beginning of-circular-linked-list' loading='lazy' title=

Įterpimas apskrito susieto sąrašo pradžioje

Norėdami daugiau sužinoti apie įterpimą pradžioje, žr. Įterpimas apskrito susieto sąrašo pradžioje

3. Įterpimas apskrito susieto sąrašo pabaigoje

Norėdami įterpti naują mazgą apskrito susieto sąrašo pabaigoje, pirmiausia sukuriame naują mazgą ir skiriame jam atmintį.
Jei sąrašas tuščias (tai paskutinis arba uodega rodyklė esmė NULL ) inicijuojame sąrašą su naujas mazgas ir nukreipiant jį į save, kad susidarytų apskrita struktūra.
Jei sąraše jau yra mazgų, nustatome nauji mazgai kitas žymeklis, nurodantis į dabartinė galva (tai yra uodega-> kitas )
Tada atnaujinkite dabartinė uodega kitas žymeklis, nurodantis į naujas mazgas .
Galiausiai atnaujiname uodegos rodyklė prie naujas mazgas.
Tai užtikrins, kad naujas mazgas dabar yra paskutinis mazgas sąraše, išlaikant žiedinį ryšį.

Įterpimas-sąrašo-sąrašo pabaigoje' loading='lazy' title=

Įterpimas apskrito susieto sąrašo pabaigoje

Norėdami daugiau sužinoti apie įterpimą pabaigoje, žr. Įterpimas apskrito susieto sąrašo pabaigoje

4. Įterpimas tam tikroje apskritimo susieto sąrašo vietoje

Norėdami įterpti naują mazgą tam tikroje apskrito susieto sąrašo vietoje, pirmiausia patikriname, ar sąrašas tuščias.
Jei yra ir padėtis nėra 1 tada išspausdiname klaidos pranešimą, nes pozicijos sąraše nėra. aš
f padėtis yra 1 tada sukuriame naujas mazgas ir nukreipti tai į save.
Jei sąrašas nėra tuščias, sukuriame naujas mazgas ir pereikite sąrašą, kad surastumėte tinkamą įterpimo tašką.
Jei padėtis yra 1 įdedame naujas mazgas pradžioje atitinkamai pakoreguodami rodykles.
Kitose pozicijose važiuojame per sąrašą, kol pasiekiame norimą padėtį ir įterpiame naujas mazgas atnaujinant rodykles.
Jei naujas mazgas įterpiamas pabaigoje, mes taip pat atnaujiname paskutinis žymeklis, nurodantis naują mazgą, išlaikantį apskritą sąrašo struktūrą.

Insertion-at-specific-position of-circular-linked-list' loading='lazy' title=

Įterpimas tam tikroje apskritimo susieto sąrašo vietoje

Žingsnis po žingsnio metodas:

Jeigu paskutinis yra nullptr ir poz nėra 1 spausdinti' Neteisinga pozicija! “.
Kitu atveju sukurkite naują mazgą su nurodytais duomenimis.
Įterpti pradžioje: Jei poz. 1 atnaujinimo rodyklės ir grįžkite paskutinę.
Traversų sąrašas: Sukurkite kilpą, kad surastumėte įterpimo tašką; spausdinti 'Neteisinga padėtis!' jei už ribų.
Įterpti mazgą: Atnaujinkite nuorodas, kad įterptumėte naują mazgą.
Paskutinis atnaujinimas: Jei įterptas atnaujinimo pabaigoje paskutinis .

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);

Išvestis

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

Laiko sudėtingumas: O(n) turime pereiti sąrašą, kad surastume konkrečią vietą.
Pagalbinė erdvė: O(1)

Sukurti viktoriną

TechCodeview

Įterpimas į žiedinį atskirai susietą sąrašą