LISÄYS PYÖREÄÄN YKSITTÄIN LINKITETTYYN LUETTELOON

Tässä artikkelissa opimme lisäämään solmun pyöreään linkitettyyn luetteloon. Lisäys on linkitetyissä luetteloissa perustoiminto, joka sisältää uuden solmun lisäämisen luetteloon. Ympyränmuotoisessa linkitetyssä luettelossa viimeinen solmu yhdistää takaisin ensimmäiseen solmuun luoden silmukan.

Kohteiden lisäämiseen on neljä päätapaa:

Lisäys tyhjään luetteloon
Lisäys luettelon alkuun
Lisäys luettelon loppuun
Lisäys tiettyyn kohtaan luettelossa

Häntäosoittimen käytön edut pääosoittimen sijaan

Meidän täytyy kulkea koko luettelo, jotta voimme lisätä solmun alkuun. Myös loppuun lisäämistä varten koko lista on selattava. Jos sen sijaan aloita osoitin vie osoittimen viimeiseen solmuun, jolloin molemmissa tapauksissa ei tarvitse kulkea koko listaa läpi. Joten lisääminen alkuun tai loppuun vie vakioajan luettelon pituudesta riippumatta.

1. Lisäys tyhjään luetteloon pyöreässä linkitetyssä luettelossa

Solmun lisääminen tyhjään pyöreään linkitettyyn luetteloon luo a uusi solmu annetuilla tiedoilla asettaa seuraavan osoittimensa osoittamaan itseään ja päivittää kestää osoitin viittaa tähän uusi solmu .

Lisäys tyhjään luetteloon

Vaiheittainen lähestymistapa:

Tarkista jos kestää ei ole nullptr . Jos totta palata kestää (lista ei ole tyhjä).
Muussa tapauksessa Luo a uusi solmu toimitetuilla tiedoilla.
- Aseta uudet solmut seuraava osoitin osoittaa itseensä (pyöreä linkki).
- Päivittää kestää osoittaa uusi solmu ja palauta se.

Lue lisää lisäämisestä tyhjään luetteloon: Lisäys tyhjään luetteloon pyöreässä linkitetyssä luettelossa

2. Lisäys pyöreän linkitetyn luettelon alkuun

Uuden solmun lisääminen pyöreän linkitetyn luettelon alkuun
Luomme ensin uusi solmu ja varaa sille muistia.
Jos luettelo on tyhjä (ilmaisee viimeisen osoittimen olevan NULL ) teemme uusi solmu osoittaa itseään.
Jos luettelossa on jo solmuja, asetamme uudet solmut seuraava osoitin osoittaa nykyinen pää listasta (joka on viimeinen->seuraava )
Päivitä sitten viimeisen solmun seuraava osoitin osoittamaan uusi solmu . Tämä säilyttää luettelon pyöreän rakenteen.

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

Lisäys pyöreän linkitetyn luettelon alkuun

Jos haluat lukea lisää lisäämisestä alussa, katso: Lisäys pyöreän linkitetyn luettelon alkuun

3. Lisäys pyöreän linkitetyn luettelon loppuun

Jos haluat lisätä uuden solmun pyöreän linkitetyn luettelon loppuun, luomme ensin uuden solmun ja varaamme sille muistia.
Jos lista on tyhjä (tarkoittaa kestää tai häntää osoitin on NULL ) alustamme luettelon uusi solmu ja saamalla sen osoittamaan itseään muodostamaan pyöreän rakenteen.
Jos luettelossa on jo solmuja, asetamme uudet solmut seuraava osoitin osoittaa nykyinen pää (joka on häntä-> seuraavaksi )
Päivitä sitten nykyinen häntä seuraava osoitin osoittaa uusi solmu .
Lopuksi päivitämme hännän osoitin kohtaan uusi solmu.
Tämä varmistaa, että uusi solmu on nyt viimeinen solmu luettelossa säilyttäen samalla pyöreän yhteyden.

Lisäys-ympyrän-linkitetty-luettelon lopussa' loading='lazy' title=

Lisäys pyöreän linkitetyn luettelon loppuun

Lue lisää lisäämisestä lopussa: Lisäys pyöreän linkitetyn luettelon loppuun

4. Lisäys tiettyyn kohtaan pyöreässä linkitetyssä luettelossa

Jos haluat lisätä uuden solmun tiettyyn kohtaan pyöreässä linkitetyssä luettelossa, tarkistamme ensin, onko luettelo tyhjä.
Jos on ja asema ei ole 1 sitten tulostamme virheilmoituksen, koska sijaintia ei ole luettelossa. minä
f asema on 1 sitten luomme uusi solmu ja osoittaa sen itselleen.
Jos luettelo ei ole tyhjä, luomme uusi solmu ja selaa luetteloa löytääksesi oikean lisäyskohdan.
Jos asema on 1 asetamme uusi solmu alussa säätämällä osoittimia vastaavasti.
Muissa paikoissa kuljemme luettelon läpi, kunnes saavutamme halutun kohdan ja lisäämme uusi solmu päivittämällä osoittimet.
Jos uusi solmu lisätään loppuun, päivitämme myös kestää osoitin, joka viittaa uuteen solmuun, joka säilyttää luettelon pyöreän rakenteen.

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

Lisäys tiettyyn kohtaan pyöreässä linkitetyssä luettelossa

Vaiheittainen lähestymistapa:

Jos kestää on nullptr ja pos ei ole 1 tulosta' Virheellinen sijainti! '.
Muussa tapauksessa luo uusi solmu annetuilla tiedoilla.
Lisää alussa: Jos pos on 1 päivitä osoittimet ja palaa viimeisenä.
Kuljetuslista: Etsi lisäyskohta silmukalla; tulosta 'Virheellinen sijainti!' jos rajojen ulkopuolella.
Lisää solmu: Päivitä osoittimet lisätäksesi uuden solmun.
Päivitys viimeksi: Jos se lisätään päivityksen lopussa kestää .

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

Lähtö

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

Aika monimutkaisuus: O(n) meidän täytyy kulkea listan läpi löytääksemme tietyn sijainnin.
Aputila: O(1)

Luo tietokilpailu

TechCodeview