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.
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 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 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.
- 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 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 .
#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 ; }
C #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)
