INSERIMENTO IN LISTA CIRCOLARE SINGOLARMENTE CONCATENATA

In questo articolo impareremo come inserire un nodo in una lista concatenata circolare. L'inserimento è un'operazione fondamentale nelle liste concatenate che prevede l'aggiunta di un nuovo nodo alla lista. In una lista concatenata circolare l'ultimo nodo si ricollega al primo nodo creando un loop.

Esistono quattro modi principali per aggiungere elementi:

Inserimento in una lista vuota
Inserimento all'inizio della lista
Inserimento a fine lista
Inserimento in una posizione specifica della lista

Vantaggi dell'utilizzo di un puntatore di coda invece di un puntatore di testa

Dobbiamo attraversare l'intero elenco per inserire un nodo all'inizio. Anche per l'inserimento alla fine occorre percorrere tutta la lista. Se invece del inizio pointer prendiamo un puntatore all'ultimo nodo quindi in entrambi i casi non ci sarà bisogno di attraversare l'intera lista. Quindi l'inserimento all'inizio o alla fine richiede un tempo costante indipendentemente dalla lunghezza della lista.

d infradito

1. Inserimento in una Lista vuota nella lista circolare concatenata

Per inserire un nodo in un elenco collegato circolare vuoto crea a nuovo nodo con i dati forniti imposta il puntatore successivo in modo che punti a se stesso e aggiorna il file scorso puntatore per fare riferimento a questo nuovo nodo .

Inserimento in una Lista vuota

Approccio passo dopo passo:

Controlla se scorso non lo è nullptr . Se VERO ritorno scorso (l'elenco non è vuoto).
Altrimenti crea un nuovo nodo con i dati forniti.
- Imposta il nuovi nodi puntatore successivo per puntare a se stesso (collegamento circolare).
- Aggiornamento scorso per indicare il nuovo nodo e restituirlo.

Per saperne di più sull'inserimento in una lista vuota fare riferimento a: Inserimento in una Lista vuota nella lista circolare concatenata

2. Inserimento all'inizio nella lista circolare concatenata

Per inserire un nuovo nodo all'inizio di una lista concatenata circolare
Per prima cosa creiamo il file nuovo nodo e allocare memoria per esso.
Se l'elenco è vuoto (indicato dall'ultimo puntatore che è NULL ) facciamo il nuovo nodo puntare a se stesso.
Se la lista contiene già nodi allora impostiamo il file nuovi nodi puntatore successivo per puntare a capo attuale della lista (che è ultimo->successivo )
Quindi aggiorna il puntatore successivo dell'ultimo nodo in modo che punti a nuovo nodo . Ciò mantiene la struttura circolare dell'elenco.

Inserimento-all-inizio-della-lista-collegata-circolare' loading='lazy' title=

Inserimento all'inizio in lista circolare collegata

Per saperne di più sull'inserimento all'inizio fare riferimento a: Inserimento all'inizio in lista circolare collegata

3. Inserimento alla fine nell'elenco concatenato circolare

Per inserire un nuovo nodo alla fine di un elenco collegato circolare, creiamo prima il nuovo nodo e gli assegniamo memoria.
Se l'elenco è vuoto (mean scorso O coda puntatore essere NULL ) inizializziamo la lista con il nuovo nodo e facendolo puntare su se stesso per formare una struttura circolare.
Se la lista contiene già nodi allora impostiamo il file nuovi nodi puntatore successivo per puntare a capo attuale (che è coda->successivo )
Quindi aggiorna il coda attuale puntatore successivo per puntare a nuovo nodo .
Infine aggiorniamo il puntatore della coda al nuovo nodo.
Ciò garantirà che il nuovo nodo ora è il ultimo nodo nell'elenco mantenendo il collegamento circolare.

Inserimento-alla-fine-della-lista-linkata-circolare' loading='lazy' title=

Inserimento alla fine in lista circolare collegata

Per saperne di più sull'inserimento alla fine fare riferimento a: Inserimento alla fine in lista circolare collegata

4. Inserimento in posizione specifica nella lista circolare collegata

Per inserire un nuovo nodo in una posizione specifica in una lista concatenata circolare controlliamo prima se la lista è vuota.
decodifica base64 in js
Se lo è e il posizione non lo è 1 quindi stampiamo un messaggio di errore perché la posizione non esiste nella lista. IO
f il posizione È 1 quindi creiamo il nuovo nodo e farlo puntare a se stesso.
Se l'elenco non è vuoto creiamo il file nuovo nodo e attraversa l'elenco per trovare il punto di inserimento corretto.
Se il posizione È 1 inseriamo il nuovo nodo all'inizio regolando i puntatori di conseguenza.
Per le altre posizioni attraversiamo l'elenco fino a raggiungere la posizione desiderata e inserendo il nuovo nodo aggiornando i puntatori.
Se il nuovo nodo viene inserito alla fine aggiorniamo anche il scorso puntatore per fare riferimento al nuovo nodo mantenendo la struttura circolare della lista.

Inserimento nella posizione specifica dell'elenco collegato circolare' loading='lazy' title=

Inserimento in posizione specifica nella lista circolare collegata

Approccio passo dopo passo:

Se scorso È nullptr E pos non lo è 1 stampa ' Posizione non valida! '.
Altrimenti Crea un nuovo nodo con i dati forniti.
Inserisci all'inizio: Se pos è 1 aggiorna i puntatori e ritorna per ultimo.
Elenco traversate: Ciclo per trovare il punto di inserimento; print 'Posizione non valida!' se fuori limite.
Inserisci nodo: Aggiorna i puntatori per inserire il nuovo nodo.
Ultimo aggiornamento: Se inserito a fine aggiornamento scorso .

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

Produzione

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

Complessità temporale: O(n) dobbiamo attraversare l'elenco per trovare la posizione specifica.
Spazio ausiliario: O(1)

Crea quiz

TechCodeview