Inserarea în lista circulară legată individual
În acest articol vom învăța cum să inserăm un nod într-o listă circulară legată. Inserarea este o operație fundamentală în listele legate care implică adăugarea unui nou nod la listă. Într-o listă circulară legată, ultimul nod se conectează înapoi la primul nod creând o buclă.
Există patru moduri principale de a adăuga elemente:
- Inserarea într-o listă goală
- Inserarea la începutul listei
- Inserare la sfârșitul listei
- Inserarea într-o anumită poziție din listă
Avantajele utilizării unui indicator de coadă în locul unui indicator de cap
Trebuie să parcurgem întreaga listă pentru a insera un nod la început. De asemenea, pentru inserarea la sfârșit trebuie parcursă întreaga listă. Dacă în loc de început pointer luăm un pointer către ultimul nod, apoi în ambele cazuri nu va fi nevoie să parcurgem întreaga listă. Deci inserarea la început sau la sfârșit durează timp constant, indiferent de lungimea listei.
1. Inserarea într-o Listă goală în lista circulară legată
Pentru a insera un nod într-o listă circulară goală, se creează un nod nou cu datele date își setează următorul indicator să indice spre sine și actualizează dura indicator pentru a face referire la aceasta nod nou .
Inserarea într-o Listă goală Abordare pas cu pas:
- Verifică dacă dura nu este nullptr . Dacă adevărat reveni dura (lista nu este goală).
- În caz contrar, creează un nod nou cu datele furnizate.
- Setați nodurile noi următorul indicator pentru a indica spre sine (link circular).
- Actualizare dura pentru a indica nod nou si returneaza-l.
Pentru a citi mai multe despre inserarea într-o listă goală Consultați: Inserarea într-o Listă goală în lista circulară legată
2. Inserarea la inceput in lista circulara legata
Pentru a insera un nou nod la începutul unei liste circulare legate
- Mai întâi creăm nod nou și alocați-i memorie.
- Dacă lista este goală (indicată de ultimul indicator fiind NUL ) facem nod nou arata spre sine.
- Dacă lista conține deja noduri, atunci setăm nodurile noi următorul indicator pentru a indica actualul cap a listei (care este ultimul->urmatorul )
- Apoi actualizați următorul indicator al ultimului nod pentru a indica nod nou . Aceasta menține structura circulară a listei.
Inserarea la început în lista circulară legată Pentru a citi mai multe despre Inserare la început Consultați: Inserarea la început în lista circulară legată
3. Inserarea la sfârșit în listă circulară legată
Pentru a insera un nou nod la sfârșitul unei liste circulare legate, mai întâi creăm noul nod și alocam memorie pentru acesta.
- Dacă lista este goală (media dura sau coadă indicatorul fiind NUL ) inițializam lista cu nod nou și făcându-l să se îndrepte spre sine pentru a forma o structură circulară.
- Dacă lista conține deja noduri, atunci setăm nodurile noi următorul indicator pentru a indica actualul cap (care este coada->n continuare )
- Apoi actualizați cozile curente următorul indicator pentru a indica nod nou .
- În cele din urmă, actualizăm indicatorul de coadă la nod nou.
- Acest lucru va asigura că nod nou este acum ultimul nod în listă menținând în același timp legătura circulară.
Inserarea la sfârșit în listă circulară legată Pentru a citi mai multe despre Inserarea la sfârșit Consultați: Inserarea la sfârșit în listă circulară legată
4. Inserarea la o anumită poziție în lista circulară legată
Pentru a insera un nou nod într-o anumită poziție într-o listă circulară legată, verificăm mai întâi dacă lista este goală.
- Dacă este și poziţie nu este 1 apoi tipărim un mesaj de eroare deoarece poziția nu există în listă. eu
- f poziţie este 1 apoi creăm nod nou și fă-l să se îndrepte spre sine.
- Dacă lista nu este goală, creăm nod nou și parcurgeți lista pentru a găsi punctul de inserare corect.
- Dacă poziţie este 1 introducem nod nou la început ajustând indicatoarele în mod corespunzător.
- Pentru alte pozitii parcurgem lista pana ajungem la pozitia dorita si introducem nod nou prin actualizarea indicatoarelor.
- Dacă noul nod este introdus la sfârșit, actualizăm și dura pointer pentru a face referire la noul nod menținând structura circulară a listei.
Inserarea la o anumită poziție în lista circulară legată Abordare pas cu pas:
- Dacă dura este nullptr şi poz nu este 1 printeaza ' Poziție nevalidă! '.
- În caz contrar, creați un nou Nod cu datele date.
- Introduceți la început: Dacă pos este 1, actualizați pointerii și reveniți ultimul.
- Lista transversală: Buclă pentru a găsi punctul de inserare; printează „Poziție invalidă!” dacă este în afara limitelor.
- Inserați nodul: Actualizați pointerii pentru a insera noul nod.
- Ultima actualizare: Dacă este introdus la sfârșitul actualizării dura .
#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 );
Ieșire
Original list: 2 3 4 List after insertions: 2 5 3 4
Complexitatea timpului: O(n) trebuie să parcurgem lista pentru a găsi poziția specifică.
Spațiu auxiliar: O(1)
