Inserção em lista circular simples
Neste artigo aprenderemos como inserir um nó em uma lista vinculada circular. A inserção é uma operação fundamental em listas vinculadas que envolve adicionar um novo nó à lista. Em uma lista vinculada circular, o último nó se conecta de volta ao primeiro nó, criando um loop.
Existem quatro maneiras principais de adicionar itens:
- Inserção em uma lista vazia
- Inserção no início da lista
- Inserção no final da lista
- Inserção em uma posição específica na lista
Vantagens de usar um ponteiro de cauda em vez de um ponteiro de cabeça
Precisamos percorrer toda a lista para inserir um nó no início. Também para inserção no final toda a lista deve ser percorrida. Se em vez do começar ponteiro levamos um ponteiro para o último nó, então em ambos os casos não haverá necessidade de percorrer toda a lista. Portanto, a inserção no início ou no final leva um tempo constante, independentemente do comprimento da lista.
1. Inserção em uma lista vazia na lista vinculada circular
Inserir um nó em uma lista vinculada circular vazia cria um novo nó com os dados fornecidos define seu próximo ponteiro para apontar para si mesmo e atualiza o durar ponteiro para referenciar isso novo nó .
Inserção em uma lista vazia Abordagem passo a passo:
- Verifique se durar não é nullptr . Se verdadeiro retornar durar (a lista não está vazia).
- Caso contrário, crie um novo nó com os dados fornecidos.
- Defina o novo nó próximo ponteiro para apontar para si mesmo (link circular).
- Atualizar durar apontar para o novo nó e devolva-o.
Para ler mais sobre inserção em uma lista vazia, consulte: Inserção em uma lista vazia na lista vinculada circular
2. Inserção no início em lista vinculada circular
Para inserir um novo nó no início de uma lista vinculada circular
- Primeiro criamos o novo nó e alocar memória para isso.
- Se a lista estiver vazia (indicado pelo último ponteiro sendo NULO ) fazemos o novo nó apontar para si mesmo.
- Se a lista já contém nós, então definimos o novo nó próximo ponteiro para apontar para o chefe atual da lista (que é último->próximo )
- Em seguida, atualize o próximo ponteiro do último nó para apontar para o novo nó . Isso mantém a estrutura circular da lista.
Inserção no início da lista vinculada circular Para ler mais sobre Inserção no início, consulte: Inserção no início da lista vinculada circular
3. Inserção no final em lista vinculada circular
Para inserir um novo nó no final de uma lista vinculada circular, primeiro criamos o novo nó e alocamos memória para ele.
- Se a lista estiver vazia (significa durar ou cauda ponteiro sendo NULO ) inicializamos a lista com o novo nó e fazendo-o apontar para si mesmo para formar uma estrutura circular.
- Se a lista já contém nós, então definimos o novo nó próximo ponteiro para apontar para o chefe atual (que é cauda->próximo )
- Então atualize o cauda atual próximo ponteiro para apontar para o novo nó .
- Finalmente atualizamos o ponteiro de cauda para o novo nó.
- Isto garantirá que o novo nó é agora o último nó na lista, mantendo a ligação circular.
Inserção no final da lista vinculada circular Para ler mais sobre Inserção no final, consulte: Inserção no final da lista vinculada circular
4. Inserção em posição específica na lista vinculada circular
Para inserir um novo nó em uma posição específica em uma lista vinculada circular, primeiro verificamos se a lista está vazia.
- Se for e o posição não é 1 então imprimimos uma mensagem de erro porque a posição não existe na lista. EU
- f o posição é 1 então criamos o novo nó e fazê-lo apontar para si mesmo.
- Se a lista não estiver vazia, criamos o novo nó e percorra a lista para encontrar o ponto de inserção correto.
- Se o posição é 1 inserimos o novo nó no início, ajustando os ponteiros de acordo.
- Para as demais posições percorremos a lista até chegar à posição desejada e inserindo o novo nó atualizando os ponteiros.
- Se o novo nó for inserido no final, também atualizamos o durar ponteiro para referenciar o novo nó mantendo a estrutura circular da lista.
Inserção em posição específica na lista vinculada circular Abordagem passo a passo:
- Se durar é nullptr e posição não é 1 imprimir ' Posição inválida! '.
- Caso contrário, crie um novo nó com os dados fornecidos.
- Inserir no início: Se pos for 1, atualize os ponteiros e retorne por último.
- Lista transversal: Faça um loop para encontrar o ponto de inserção; imprima 'Posição inválida!' se estiver fora dos limites.
- Inserir nó: Atualize os ponteiros para inserir o novo nó.
- Última atualização: Se inserido no final da atualização durar .
#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 );
Saída
Original list: 2 3 4 List after insertions: 2 5 3 4
Complexidade de tempo: O(n) temos que percorrer a lista para encontrar a posição específica.
Espaço Auxiliar: O(1)
