Vložení do kruhového samostatně propojeného seznamu
V tomto článku se naučíme, jak vložit uzel do kruhového propojeného seznamu. Vkládání je základní operace v propojených seznamech, která zahrnuje přidání nového uzlu do seznamu. V kruhovém propojeném seznamu se poslední uzel připojuje zpět k prvnímu uzlu a vytváří smyčku.
Existují čtyři hlavní způsoby, jak přidat položky:
- Vložení do prázdného seznamu
- Vložení na začátek seznamu
- Vložení na konec seznamu
- Vložení na konkrétní pozici v seznamu
Výhody použití ukazatele ocasu místo ukazatele hlavy
Musíme projít celý seznam, abychom vložili uzel na začátek. Také pro vložení na konec je nutné projít celý seznam. Pokud místo start ukazatel vezmeme ukazatel na poslední uzel, pak v obou případech nebude potřeba procházet celý seznam. Vložení na začátek nebo konec tedy trvá konstantní čas bez ohledu na délku seznamu.
1. Vložení do prázdného seznamu v kruhovém propojeném seznamu
Chcete-li vložit uzel do prázdného kruhového propojeného seznamu, vytvoří se a nový uzel s danými daty nastaví svůj další ukazatel tak, aby ukazoval na sebe a aktualizuje poslední ukazatel na to odkazovat nový uzel .
Vložení do prázdného seznamu Postup krok za krokem:
- Zkontrolujte, zda poslední není nullptr . Li věrný návrat poslední (seznam není prázdný).
- V opačném případě vytvořte a nový uzel s poskytnutými údaji.
- Nastavte nový uzel další ukazatel ukazuje na sebe (kruhový odkaz).
- Aktualizovat poslední ukázat na nový uzel a vrátit to.
Další informace o vkládání do prázdného seznamu naleznete na: Vložení do prázdného seznamu v kruhovém propojeném seznamu
2. Vložení na začátek v kruhovém propojeném seznamu
Chcete-li vložit nový uzel na začátek kruhového propojeného seznamu
- Nejprve vytvoříme nový uzel a přidělit mu paměť.
- Pokud je seznam prázdný (označeno posledním ukazatelem NULL ) vyrábíme nový uzel poukázat na sebe.
- Pokud seznam již obsahuje uzly, nastavíme nový uzel další ukazatel ukazující na současná hlava seznamu (což je poslední->další )
- Potom aktualizujte další ukazatel posledního uzlu tak, aby ukazoval na nový uzel . Tím se zachová kruhová struktura seznamu.
Vložení na začátek v kruhovém propojeném seznamu Chcete-li si přečíst více o vkládání na začátku, přečtěte si: Vložení na začátek v kruhovém propojeném seznamu
3. Vložení na konec v kruhovém propojeném seznamu
Chcete-li vložit nový uzel na konec kruhového propojeného seznamu, nejprve vytvoříme nový uzel a přidělíme mu paměť.
- Pokud je seznam prázdný (průměr poslední nebo ocas ukazatel bytost NULL ) inicializujeme seznam pomocí nový uzel a tím, že ukazuje na sebe, aby vytvořilo kruhovou strukturu.
- Pokud seznam již obsahuje uzly, nastavíme nový uzel další ukazatel ukazující na současná hlava (což je ocas->další )
- Poté aktualizujte aktuální ocas další ukazatel ukazující na nový uzel .
- Nakonec aktualizujeme ocasní ukazatel k nový uzel.
- Tím bude zajištěno, že nový uzel je nyní poslední uzel v seznamu při zachování kruhové vazby.
Vložení na konec v kruhovém propojeném seznamu Chcete-li si přečíst více o vkládání na konci, viz: Vložení na konec v kruhovém propojeném seznamu
4. Vložení na určitou pozici v kruhovém propojeném seznamu
Chcete-li vložit nový uzel na konkrétní pozici v kruhovém propojeném seznamu, nejprve zkontrolujeme, zda je seznam prázdný.
- Pokud je a pozice není 1 poté vypíšeme chybovou zprávu, protože pozice v seznamu neexistuje. já
- f pozice je 1 pak vytvoříme nový uzel a aby to ukazovalo na sebe.
- Pokud seznam není prázdný, vytvoříme nový uzel a procházením seznamu najděte správný bod vložení.
- Pokud pozice je 1 vložíme nový uzel na začátku odpovídajícím nastavením ukazatelů.
- Pro další pozice procházíme seznamem, dokud nedosáhneme požadované pozice a vložíme nový uzel aktualizací ukazatelů.
- Pokud je nový uzel vložen na konec, aktualizujeme také poslední ukazatel na odkaz na nový uzel zachovává kruhovou strukturu seznamu.
Vložení na konkrétní pozici v kruhovém propojeném seznamu Postup krok za krokem:
- Li poslední je nullptr a poz není 1 tisknout Neplatná pozice! '.
- Jinak vytvořte nový uzel s danými daty.
- Vložit na začátek: Pokud je pozice 1, aktualizujte ukazatele a vraťte se jako poslední.
- Seznam procházení: Smyčkou vyhledejte bod vložení; tisknout 'Neplatná pozice!' pokud je mimo meze.
- Vložit uzel: Aktualizujte ukazatele pro vložení nového uzlu.
- Poslední aktualizace: Pokud je vložen na konci aktualizace 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á náročnost: O(n) musíme procházet seznam, abychom našli konkrétní pozici.
Pomocný prostor: O(1)
