Inserció en una llista circular enllaçada individualment
En aquest article aprendrem a inserir un node en una llista enllaçada circular. La inserció és una operació fonamental en llistes enllaçades que implica afegir un nou node a la llista. En una llista enllaçada circular, l'últim node es connecta de nou al primer node creant un bucle.
Hi ha quatre maneres principals d'afegir elements:
- Inserció en una llista buida
- Inserció al començament de la llista
- Inserció al final de la llista
- Inserció en una posició concreta de la llista
Avantatges d'utilitzar un punter de cua en lloc d'un punter de cap
Hem de recórrer tota la llista per inserir un node al principi. També per a la inserció al final s'ha de recórrer tota la llista. Si en comptes de la començar punter agafem un punter a l'últim node i, en ambdós casos, no caldrà recórrer tota la llista. Per tant, la inserció al principi o al final requereix un temps constant, independentment de la longitud de la llista.
1. Inserció en una llista buida a la llista enllaçada circular
Per inserir un node en una llista enllaçada circular buida es crea un nou node amb les dades proporcionades estableix el seu següent punter per apuntar-se a si mateix i actualitza el darrer punter per fer referència a això nou node .
Inserció en una llista buida Enfocament pas a pas:
- Comproveu si darrer no ho és nullptr . Si veritat tornar darrer (la llista no està buida).
- En cas contrari, creeu un nou node amb les dades facilitades.
- Estableix el nou node següent punter per apuntar-se a si mateix (enllaç circular).
- Actualització darrer per assenyalar el nou node i retornar-lo.
Per obtenir més informació sobre la inserció en una llista buida, consulteu: Inserció en una llista buida a la llista enllaçada circular
2. Inserció al principi en llista enllaçada circular
Per inserir un nou node al principi d'una llista enllaçada circular
- Primer creem el nou node i assignar-hi memòria.
- Si la llista està buida (s'indica que l'últim punter és NULL ) fem el nou node apuntar a si mateix.
- Si la llista ja conté nodes, establim el nou node següent punter per assenyalar cap actual de la llista (que és últim->següent )
- A continuació, actualitzeu el següent punter de l'últim node per apuntar-hi nou node . Això manté l'estructura circular de la llista.
Inserció al principi en llista enllaçada circular Per obtenir més informació sobre la inserció al principi, consulteu: Inserció al principi en llista enllaçada circular
3. Inserció al final en llista enllaçada circular
Per inserir un nou node al final d'una llista enllaçada circular, primer creem el nou node i hi assignem memòria.
- Si la llista està buida (mean darrer o cua ésser punter NULL ) inicialitzem la llista amb el nou node i fent-lo apuntar cap a si mateix per formar una estructura circular.
- Si la llista ja conté nodes, establim el nou node següent punter per assenyalar cap actual (que és cua->següent )
- A continuació, actualitzeu el cua actual següent punter per assenyalar nou node .
- Finalment actualitzem el punter de cua al nou node.
- Això garantirà que el nou node ara és el últim node a la llista mantenint l'enllaç circular.
Inserció al final en llista enllaçada circular Per obtenir més informació sobre la inserció al final, consulteu: Inserció al final en llista enllaçada circular
4. Inserció en una posició específica en llista enllaçada circular
Per inserir un nou node en una posició específica en una llista enllaçada circular, primer comprovem si la llista està buida.
- Si és i el posició no ho és 1 llavors imprimim un missatge d'error perquè la posició no existeix a la llista. jo
- f la posició és 1 després creem el nou node i fer-ho apuntar a si mateix.
- Si la llista no està buida, creem el nou node i recorreu la llista per trobar el punt d'inserció correcte.
- Si el posició és 1 inserim el nou node al principi ajustant els punters en conseqüència.
- Per a altres posicions recorrem la llista fins a arribar a la posició desitjada i inserint el nou node mitjançant l'actualització dels punters.
- Si al final s'insereix el nou node, també actualitzem el darrer punter per fer referència al nou node mantenint l'estructura circular de la llista.
Inserció en una posició específica en llista enllaçada circular Enfocament pas a pas:
- Si darrer és nullptr i pos no ho és 1 imprimir' Posició no vàlida! '.
- En cas contrari, creeu un nou node amb les dades donades.
- Insereix a l'inici: Si pos és 1 actualitza els punters i torna l'últim.
- Llista transversal: Bucle per trobar el punt d'inserció; imprimir "Posició no vàlida!" si està fora dels límits.
- Insereix node: Actualitza els punters per inserir el nou node.
- Última actualització: Si s'insereix al final de l'actualització darrer .
#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 );
Sortida
Original list: 2 3 4 List after insertions: 2 5 3 4
Complexitat temporal: O(n) hem de recórrer la llista per trobar la posició específica.
Espai auxiliar: O(1)
