Inserción en lista circular individualmente enlazada
En este artículo aprenderemos cómo insertar un nodo en una lista enlazada circular. La inserción es una operación fundamental en listas enlazadas que implica agregar un nuevo nodo a la lista. En una lista circular enlazada, el último nodo se conecta nuevamente al primer nodo creando un bucle.
Hay cuatro formas principales de agregar elementos:
- Inserción en una lista vacía
- Inserción al principio de la lista.
- Inserción al final de la lista.
- Inserción en una posición específica de la lista.
Ventajas de utilizar un puntero de cola en lugar de un puntero de cabeza
Necesitamos recorrer toda la lista para insertar un nodo al principio. Además, para insertarlo al final se debe recorrer toda la lista. Si en lugar de comenzar puntero llevamos un puntero al último nodo y, en ambos casos, no será necesario recorrer toda la lista. Por lo tanto, la inserción al principio o al final requiere un tiempo constante, independientemente de la longitud de la lista.
1. Inserción en una Lista vacía en la lista circular enlazada
Para insertar un nodo en una lista enlazada circular vacía se crea un nuevo nodo con los datos dados establece su siguiente puntero para que apunte a sí mismo y actualiza el último puntero para hacer referencia a esto nuevo nodo .
Inserción en una lista vacía Enfoque paso a paso:
- comprobar si último no es nulo . Si verdadero devolver último (la lista no está vacía).
- De lo contrario, cree un nuevo nodo con los datos proporcionados.
- Establecer el nuevos nodos siguiente puntero para que apunte a sí mismo (enlace circular).
- Actualizar último para señalar el nuevo nodo y devolverlo.
Para leer más sobre la inserción en una lista vacía, consulte: Inserción en una Lista vacía en la lista circular enlazada
2. Inserción al principio en lista circular enlazada.
Para insertar un nuevo nodo al principio de una lista enlazada circular
- Primero creamos el nuevo nodo y asignarle memoria.
- Si la lista está vacía (indicado por el último puntero NULO ) hacemos el nuevo nodo apuntar a sí mismo.
- Si la lista ya contiene nodos, configuramos el nuevos nodos siguiente puntero para señalar el jefe actual de la lista (que es último->siguiente )
- Luego actualice el siguiente puntero del último nodo para que apunte al nuevo nodo . Esto mantiene la estructura circular de la lista.
Inserción al principio en lista circular enlazada. Para leer más sobre la inserción al principio, consulte: Inserción al principio en lista circular enlazada.
3. Inserción al final de una lista circular enlazada.
Para insertar un nuevo nodo al final de una lista enlazada circular, primero creamos el nuevo nodo y le asignamos memoria.
- Si la lista está vacía (significa último o cola puntero siendo NULO ) inicializamos la lista con el nuevo nodo y haciéndolo apuntar hacia sí mismo para formar una estructura circular.
- Si la lista ya contiene nodos, configuramos el nuevos nodos siguiente puntero para señalar el jefe actual (que es cola->siguiente )
- Luego actualice el cola actual siguiente puntero para señalar el nuevo nodo .
- Finalmente actualizamos el puntero de cola hacia nuevo nodo.
- Esto asegurará que el nuevo nodo es ahora el último nodo en la lista manteniendo el vínculo circular.
Inserción al final de una lista circular enlazada. Para leer más sobre Inserción al final Consulte: Inserción al final de una lista circular enlazada.
4. Inserción en una posición específica en una lista circular enlazada
Para insertar un nuevo nodo en una posición específica en una lista circular enlazada, primero verificamos si la lista está vacía.
- Si es así y el posición no es 1 luego imprimimos un mensaje de error porque la posición no existe en la lista. I
- f el posición es 1 luego creamos el nuevo nodo y hacer que se señale a sí mismo.
- Si la lista no está vacía creamos el nuevo nodo y recorra la lista para encontrar el punto de inserción correcto.
- si el posición es 1 insertamos el nuevo nodo al principio ajustando los punteros en consecuencia.
- Para otras posiciones recorremos la lista hasta llegar a la posición deseada e insertando el nuevo nodo actualizando los punteros.
- Si el nuevo nodo se inserta al final también actualizamos el último puntero para hacer referencia al nuevo nodo manteniendo la estructura circular de la lista.
Inserción en una posición específica en una lista circular enlazada Enfoque paso a paso:
- Si último es nulo y posición no es 1 imprimir ' ¡Posición no válida! '.
- De lo contrario, cree un nuevo nodo con los datos proporcionados.
- Insertar al principio: Si pos es 1, actualice los punteros y regrese al último.
- Lista transversal: Bucle para encontrar el punto de inserción; imprimir '¡Posición no válida!' si está fuera de límites.
- Insertar nodo: Actualice los punteros para insertar el nuevo nodo.
- Última actualización: Si se inserta al final de la actualización último .
#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 );
Producción
Original list: 2 3 4 List after insertions: 2 5 3 4
Complejidad del tiempo: O(n) tenemos que recorrer la lista para encontrar la posición específica.
Espacio Auxiliar: O(1)
