Vstavljanje v krožni enojno povezani seznam
V tem članku se bomo naučili, kako vstaviti vozlišče v krožni povezan seznam. Vstavljanje je temeljna operacija v povezanih seznamih, ki vključuje dodajanje novega vozlišča na seznam. V krožnem povezanem seznamu se zadnje vozlišče poveže nazaj s prvim vozliščem, kar ustvari zanko.
Obstajajo štirje glavni načini dodajanja elementov:
- Vstavljanje na prazen seznam
- Vnos na začetek seznama
- Vnos na koncu seznama
- Vstavljanje na določeno mesto na seznamu
Prednosti uporabe kazalca repa namesto kazalca glave
Preleteti moramo celoten seznam, da na začetek vstavimo vozlišče. Tudi za vstavljanje na koncu je treba prehoditi celoten seznam. Če namesto začetek kazalec vzamemo kazalec na zadnje vozlišče, potem v obeh primerih ne bo treba prečkati celotnega seznama. Torej vstavljanje na začetek ali konec traja konstanten čas, ne glede na dolžino seznama.
1. Vstavljanje v prazen seznam v krožnem povezanem seznamu
Če želite vstaviti vozlišče v prazen krožni povezan seznam, ustvarite a novo vozlišče z danimi podatki nastavi svoj naslednji kazalec tako, da kaže samega sebe, in posodobi zadnji kazalec za sklicevanje na to novo vozlišče .
Vstavljanje v prazen seznam Pristop po korakih:
- Preverite, če zadnji ni nullptr . če res vrnitev zadnji (seznam ni prazen).
- V nasprotnem primeru Ustvari a novo vozlišče s posredovanimi podatki.
- Nastavite novo vozlišče naslednji kazalec, ki kaže sam nase (krožna povezava).
- posodobitev zadnji pokazati na novo vozlišče in ga vrniti.
Če želite prebrati več o vstavljanju na prazen seznam, glejte: Vstavljanje v prazen seznam v krožnem povezanem seznamu
2. Vstavljanje na začetek krožnega povezanega seznama
Če želite vstaviti novo vozlišče na začetek krožnega povezanega seznama
- Najprej ustvarimo novo vozlišče in mu dodelite pomnilnik.
- Če je seznam prazen (označeno z zadnjim kazalcem NULL ) naredimo novo vozlišče kažejo nase.
- Če seznam že vsebuje vozlišča, nastavimo novo vozlišče naslednji kazalec, ki kaže na trenutna glava seznama (kar je zadnji->naslednji )
- Nato posodobite naslednji kazalec zadnjega vozlišča, da kaže na novo vozlišče . To ohranja krožno strukturo seznama.
Vstavljanje na začetek krožnega povezanega seznama Če želite prebrati več o vstavitvi na začetku, glejte: Vstavljanje na začetek krožnega povezanega seznama
3. Vstavljanje na koncu krožnega povezanega seznama
Za vstavljanje novega vozlišča na konec krožnega povezanega seznama najprej ustvarimo novo vozlišče in mu dodelimo pomnilnik.
- Če je seznam prazen (pomen zadnji oz rep bitje kazalca NULL ) inicializiramo seznam z novo vozlišče in tako kaže nase, da tvori krožno strukturo.
- Če seznam že vsebuje vozlišča, nastavimo novo vozlišče naslednji kazalec, ki kaže na trenutna glava (kar je rep->naprej )
- Nato posodobite trenutni rep naslednji kazalec, ki kaže na novo vozlišče .
- Končno posodobimo repni kazalec do novo vozlišče.
- To bo zagotovilo, da novo vozlišče je zdaj zadnje vozlišče na seznamu, pri tem pa ohraniti krožno povezavo.
Vstavljanje na koncu krožnega povezanega seznama Če želite prebrati več o vstavitvi na koncu, glejte: Vstavljanje na koncu krožnega povezanega seznama
4. Vstavljanje na določeno mesto v krožnem povezanem seznamu
Za vstavljanje novega vozlišča na določen položaj v krožnem povezanem seznamu najprej preverimo, ali je seznam prazen.
- Če je in položaj ni 1 potem natisnemo sporočilo o napaki, ker položaj ne obstaja na seznamu. jaz
- f položaj je 1 potem ustvarimo novo vozlišče in naj kaže nase.
- Če seznam ni prazen, ustvarimo novo vozlišče in prečkajte seznam, da poiščete pravilno točko vstavljanja.
- Če je položaj je 1 vstavimo novo vozlišče na začetku tako, da ustrezno prilagodite kazalce.
- Pri ostalih pozicijah se premikamo po seznamu, dokler ne pridemo do želene pozicije in vstavimo novo vozlišče s posodobitvijo kazalcev.
- Če je novo vozlišče vstavljeno na koncu, posodobimo tudi zadnji kazalec za sklicevanje na novo vozlišče, ki ohranja krožno strukturo seznama.
Vstavljanje na določeno mesto v krožnem povezanem seznamu Pristop po korakih:
- če zadnji je nullptr in poz ni 1 natisni ' Neveljaven položaj! '.
- V nasprotnem primeru ustvarite novo vozlišče z danimi podatki.
- Vstavi na začetek: Če je pos 1, posodobi kazalce in vrne zadnje.
- Prečni seznam: Zanka za iskanje točke vstavljanja; natisni 'Neveljaven položaj!' če je zunaj meja.
- Vstavi vozlišče: Posodobite kazalce, da vstavite novo vozlišče.
- Zadnja posodobitev: Če je vstavljen na koncu posodobitve zadnji .
#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 );
Izhod
Original list: 2 3 4 List after insertions: 2 5 3 4
Časovna zapletenost: O(n) moramo preleteti seznam, da najdemo določen položaj.
Pomožni prostor: O(1)
