VLOŽENIE DO KRUHOVÉHO SAMOSTATNE PREPOJENÉHO ZOZNAMU

V tomto článku sa naučíme, ako vložiť uzol do kruhového prepojeného zoznamu. Vkladanie je základná operácia v prepojených zoznamoch, ktorá zahŕňa pridanie nového uzla do zoznamu. V kruhovom prepojenom zozname sa posledný uzol pripája späť k prvému uzlu a vytvára slučku.

Existujú štyri hlavné spôsoby pridávania položiek:

Vloženie do prázdneho zoznamu
Vloženie na začiatok zoznamu
Vloženie na koniec zoznamu
Vloženie na konkrétnu pozíciu v zozname

Výhody použitia ukazovateľa chvosta namiesto ukazovateľa hlavy

Aby sme na začiatok vložili uzol, musíme prejsť celý zoznam. Aj pre vloženie na koniec je potrebné prejsť celý zoznam. Ak namiesto začať Ukazovateľ vezmeme ukazovateľ na posledný uzol, potom v oboch prípadoch nebude potrebné prechádzať celým zoznamom. Takže vkladanie na začiatok alebo koniec trvá konštantný čas bez ohľadu na dĺžku zoznamu.

1. Vloženie do prázdneho zoznamu v kruhovom prepojenom zozname

Ak chcete vložiť uzol do prázdneho kruhového prepojeného zoznamu, vytvorí sa a nový uzol s danými údajmi nastaví svoj ďalší ukazovateľ tak, aby ukazoval na seba a aktualizuje posledný ukazovateľ na to odkazovať nový uzol .

Vloženie do prázdneho zoznamu

Postupný prístup:

Skontrolujte, či posledný nie je nullptr . Ak pravda vrátiť posledný (zoznam nie je prázdny).
V opačnom prípade vytvorte a nový uzol s poskytnutými údajmi.
- Nastavte nový uzol ďalší ukazovateľ na seba (kruhový odkaz).
- Aktualizovať posledný poukázať na nový uzol a vrátiť ho.

Ak si chcete prečítať viac o vkladaní do prázdneho zoznamu, pozrite si: Vloženie do prázdneho zoznamu v kruhovom prepojenom zozname

2. Vloženie na začiatok v kruhovom prepojenom zozname

Na vloženie nového uzla na začiatok kruhového prepojeného zoznamu
Najprv vytvoríme nový uzol a prideliť mu pamäť.
Ak je zoznam prázdny (označený posledným ukazovateľom NULL ) vyrábame nový uzol poukázať na seba.
Ak zoznam už obsahuje uzly, nastavíme nový uzol ďalší ukazovateľ, ktorý ukazuje na súčasná hlava zo zoznamu (čo je posledný->ďalší )
Potom aktualizujte ďalší ukazovateľ posledného uzla tak, aby ukazoval na nový uzol . Tým sa zachová kruhová štruktúra zoznamu.

Vloženie-na-začiatok-kruhového-prepojeného-zoznamu' loading='lazy' title=

Vloženie na začiatok v kruhovom prepojenom zozname

Ak si chcete prečítať viac o vložení na začiatku, pozrite si: Vloženie na začiatok v kruhovom prepojenom zozname

3. Vloženie na koniec v kruhovom prepojenom zozname

Ak chcete vložiť nový uzol na koniec kruhového prepojeného zoznamu, najprv vytvoríme nový uzol a pridelíme mu pamäť.
Ak je zoznam prázdny (priemer posledný alebo chvost ukazovateľská bytosť NULL ) inicializujeme zoznam s nový uzol a tým, že ukazuje na seba, aby vytvoril kruhovú štruktúru.
Ak zoznam už obsahuje uzly, nastavíme nový uzol ďalší ukazovateľ, ktorý ukazuje na súčasná hlava (čo je chvost->ďalší )
Potom aktualizujte aktuálny chvost ďalší ukazovateľ, ktorý ukazuje na nový uzol .
Nakoniec aktualizujeme ukazovateľ chvosta k nový uzol.
Tým sa zabezpečí, že nový uzol je teraz posledný uzol v zozname pri zachovaní kruhového prepojenia.

Vloženie-na-koniec-kruhového-prepojeného-zoznamu' loading='lazy' title=

Vloženie na koniec v kruhovom prepojenom zozname

Ak si chcete prečítať viac o vložení na konci, pozrite si: Vloženie na koniec v kruhovom prepojenom zozname
veľkosti latexového textu

4. Vloženie na konkrétne miesto v kruhovom prepojenom zozname

Ak chcete vložiť nový uzol na konkrétnu pozíciu v kruhovom prepojenom zozname, najprv skontrolujeme, či je zoznam prázdny.
Ak je a pozíciu nie je 1 potom vypíšeme chybové hlásenie, pretože pozícia v zozname neexistuje. ja
f pozíciu je 1 potom vytvoríme nový uzol a nech to poukazuje na seba.
Ak zoznam nie je prázdny, vytvoríme nový uzol a prechádzajte zoznamom, aby ste našli správny bod vloženia.
Ak pozíciu je 1 vložíme nový uzol na začiatku zodpovedajúcim nastavením ukazovateľov.
Pre ďalšie pozície prechádzame cez zoznam, kým nedosiahneme požadovanú pozíciu a vložíme nový uzol aktualizáciou ukazovateľov.
Ak je nový uzol vložený na koniec, aktualizujeme aj posledný ukazovateľ na odkaz na nový uzol zachovávajúci kruhovú štruktúru zoznamu.

Vloženie-na-špecifickej-pozícii-kruhového-prepojeného-zoznamu' loading='lazy' title=

Vloženie na konkrétne miesto v kruhovom prepojenom zozname

Postupný prístup:

Ak posledný je nullptr a poz nie je 1 vytlačiť Neplatná pozícia! '.
V opačnom prípade vytvorte nový uzol s danými údajmi.
Vložiť na začiatok: Ak je pozícia 1, aktualizujte ukazovatele a vráťte sa ako posledný.
Zoznam prechodov: Slučka na nájdenie bodu vloženia; vytlačiť 'Neplatná pozícia!' ak je mimo hraníc.
Vložiť uzol: Aktualizujte ukazovatele na vloženie nového uzla.
Posledná aktualizácia: Ak je vložený na konci aktualizácie posledný .

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

Výstup

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

Časová zložitosť: O(n) musíme prejsť zoznam, aby sme našli konkrétnu pozíciu.
Pomocný priestor: O(1)

Vytvoriť kvíz

TechCodeview