Vloženie do kruhového samostatne prepojeného zoznamu
V tomto článku sa naučíme, ako vložiť uzol do kruhového prepojeného zoznamu. Vkladanie je základná operácia v prepojených zoznamoch, ktorá zahŕňa pridanie nového uzla do zoznamu. V kruhovom prepojenom zozname sa posledný uzol pripája späť k prvému uzlu a vytvára slučku.
Existujú štyri hlavné spôsoby pridávania položiek:
- Vloženie do prázdneho zoznamu
- Vloženie na začiatok zoznamu
- Vloženie na koniec zoznamu
- Vloženie na konkrétnu pozíciu v zozname
Výhody použitia ukazovateľa chvosta namiesto ukazovateľa hlavy
Aby sme na začiatok vložili uzol, musíme prejsť celý zoznam. Aj pre vloženie na koniec je potrebné prejsť celý zoznam. Ak namiesto začať Ukazovateľ vezmeme ukazovateľ na posledný uzol, potom v oboch prípadoch nebude potrebné prechádzať celým zoznamom. Takže vkladanie na začiatok alebo koniec trvá konštantný čas bez ohľadu na dĺžku zoznamu.
1. Vloženie do prázdneho zoznamu v kruhovom prepojenom zozname
Ak chcete vložiť uzol do prázdneho kruhového prepojeného zoznamu, vytvorí sa a nový uzol s danými údajmi nastaví svoj ďalší ukazovateľ tak, aby ukazoval na seba a aktualizuje posledný ukazovateľ na to odkazovať nový uzol .
Vloženie do prázdneho zoznamu Postupný prístup:
- Skontrolujte, či posledný nie je nullptr . Ak pravda vrátiť posledný (zoznam nie je prázdny).
- V opačnom prípade vytvorte a nový uzol s poskytnutými údajmi.
- Nastavte nový uzol ďalší ukazovateľ na seba (kruhový odkaz).
- Aktualizovať posledný poukázať na nový uzol a vrátiť ho.
Ak si chcete prečítať viac o vkladaní do prázdneho zoznamu, pozrite si: Vloženie do prázdneho zoznamu v kruhovom prepojenom zozname
2. Vloženie na začiatok v kruhovom prepojenom zozname
Na vloženie nového uzla na začiatok kruhového prepojeného zoznamu
- Najprv vytvoríme nový uzol a prideliť mu pamäť.
- Ak je zoznam prázdny (označený posledným ukazovateľom NULL ) vyrábame nový uzol poukázať na seba.
- Ak zoznam už obsahuje uzly, nastavíme nový uzol ďalší ukazovateľ, ktorý ukazuje na súčasná hlava zo zoznamu (čo je posledný->ďalší )
- Potom aktualizujte ďalší ukazovateľ posledného uzla tak, aby ukazoval na nový uzol . Tým sa zachová kruhová štruktúra zoznamu.
Vloženie na začiatok v kruhovom prepojenom zozname Ak si chcete prečítať viac o vložení na začiatku, pozrite si: Vloženie na začiatok v kruhovom prepojenom zozname
3. Vloženie na koniec v kruhovom prepojenom zozname
Ak chcete vložiť nový uzol na koniec kruhového prepojeného zoznamu, najprv vytvoríme nový uzol a pridelíme mu pamäť.
- Ak je zoznam prázdny (priemer posledný alebo chvost ukazovateľská bytosť NULL ) inicializujeme zoznam s nový uzol a tým, že ukazuje na seba, aby vytvoril kruhovú štruktúru.
- Ak zoznam už obsahuje uzly, nastavíme nový uzol ďalší ukazovateľ, ktorý ukazuje na súčasná hlava (čo je chvost->ďalší )
- Potom aktualizujte aktuálny chvost ďalší ukazovateľ, ktorý ukazuje na nový uzol .
- Nakoniec aktualizujeme ukazovateľ chvosta k nový uzol.
- Tým sa zabezpečí, že nový uzol je teraz posledný uzol v zozname pri zachovaní kruhového prepojenia.
Vloženie na koniec v kruhovom prepojenom zozname Ak si chcete prečítať viac o vložení na konci, pozrite si: Vloženie na koniec v kruhovom prepojenom zozname
4. Vloženie na konkrétne miesto v kruhovom prepojenom zozname
Ak chcete vložiť nový uzol na konkrétnu pozíciu v kruhovom prepojenom zozname, najprv skontrolujeme, či je zoznam prázdny.
- Ak je a pozíciu nie je 1 potom vypíšeme chybové hlásenie, pretože pozícia v zozname neexistuje. ja
- f pozíciu je 1 potom vytvoríme nový uzol a nech to poukazuje na seba.
- Ak zoznam nie je prázdny, vytvoríme nový uzol a prechádzajte zoznamom, aby ste našli správny bod vloženia.
- Ak pozíciu je 1 vložíme nový uzol na začiatku zodpovedajúcim nastavením ukazovateľov.
- Pre ďalšie pozície prechádzame cez zoznam, kým nedosiahneme požadovanú pozíciu a vložíme nový uzol aktualizáciou ukazovateľov.
- Ak je nový uzol vložený na koniec, aktualizujeme aj posledný ukazovateľ na odkaz na nový uzol zachovávajúci kruhovú štruktúru zoznamu.
Vloženie na konkrétne miesto v kruhovom prepojenom zozname Postupný prístup:
- Ak posledný je nullptr a poz nie je 1 vytlačiť Neplatná pozícia! '.
- V opačnom prípade vytvorte nový uzol s danými údajmi.
- Vložiť na začiatok: Ak je pozícia 1, aktualizujte ukazovatele a vráťte sa ako posledný.
- Zoznam prechodov: Slučka na nájdenie bodu vloženia; vytlačiť 'Neplatná pozícia!' ak je mimo hraníc.
- Vložiť uzol: Aktualizujte ukazovatele na vloženie nového uzla.
- Posledná aktualizácia: Ak je vložený na konci aktualizácie posledný .
#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 );
Výstup
Original list: 2 3 4 List after insertions: 2 5 3 4
Časová zložitosť: O(n) musíme prejsť zoznam, aby sme našli konkrétnu pozíciu.
Pomocný priestor: O(1)
