Umetanje u kružni jednostruko povezani popis
U ovom ćemo članku naučiti kako umetnuti čvor u kružni povezani popis. Umetanje je temeljna operacija u povezanim popisima koja uključuje dodavanje novog čvora na popis. U kružnom povezanom popisu posljednji čvor povezuje se s prvim čvorom stvarajući petlju.
Postoje četiri glavna načina za dodavanje stavki:
- Umetanje u praznu listu
- Umetanje na početak popisa
- Umetanje na kraju popisa
- Umetanje na određeno mjesto na popisu
Prednosti korištenja pokazivača repa umjesto pokazivača glave
Moramo proći cijeli popis kako bismo umetnuli čvor na početku. Također za umetanje na kraju mora se prijeći cijeli popis. Ako umjesto start pokazivač uzimamo pokazivač na zadnji čvor, tada u oba slučaja neće biti potrebe za obilaskom cijele liste. Dakle, za umetanje na početak ili kraj potrebno je konstantno vrijeme bez obzira na duljinu popisa.
1. Umetanje u prazan popis u kružnom povezanom popisu
Za umetanje čvora u prazan kružni povezani popis stvara se a novi čvor s danim podacima postavlja svoj sljedeći pokazivač da pokazuje na sebe i ažurira trajati pokazivač na ovo novi čvor .
Umetanje u prazan popis Pristup korak po korak:
- Provjerite je li trajati nije nullptr . Ako pravi povratak trajati (lista nije prazna).
- U suprotnom Stvorite a novi čvor s dostavljenim podacima.
- Postavite novi čvorovi sljedeći pokazivač koji pokazuje na sebe (kružna veza).
- Ažurirati trajati ukazati na novi čvor i vratite ga.
Da biste pročitali više o umetanju u prazan popis, pogledajte: Umetanje u prazan popis u kružnom povezanom popisu
2. Umetanje na početak u kružnom povezanom popisu
Za umetanje novog čvora na početak kružnog povezanog popisa
- Prvo stvaramo novi čvor i dodijeliti memoriju za to.
- Ako je popis prazan (označeno posljednjim pokazivačem NULL ) izrađujemo novi čvor ukazati na sebe.
- Ako popis već sadrži čvorove tada postavljamo novi čvorovi sljedeći pokazivač koji pokazuje na trenutna glava popisa (što je zadnji->sljedeći )
- Zatim ažurirajte sljedeći pokazivač zadnjeg čvora da pokazuje na novi čvor . Time se održava kružna struktura popisa.
Umetanje na početak u kružnom povezanom popisu Da biste pročitali više o umetanju na početku, pogledajte: Umetanje na početak u kružnom povezanom popisu
3. Umetanje na kraju kružnog povezanog popisa
Da bismo umetnuli novi čvor na kraj kružnog povezanog popisa, prvo kreiramo novi čvor i dodijelimo mu memoriju.
- Ako je lista prazna (znači trajati ili rep pokazivač bića NULL ) inicijaliziramo popis s novi čvor i čineći ga usmjerenim prema sebi kako bi formirao kružnu strukturu.
- Ako popis već sadrži čvorove tada postavljamo novi čvorovi sljedeći pokazivač koji pokazuje na trenutna glava (što je rep->sljedeci )
- Zatim ažurirajte trenutni repovi sljedeći pokazivač koji pokazuje na novi čvor .
- Napokon ažuriramo repni pokazivač na novi čvor.
- Ovo će osigurati da novi čvor je sada posljednji čvor u popisu zadržavajući kružnu vezu.
Umetanje na kraju kružnog povezanog popisa Da biste pročitali više o umetanju na kraju, pogledajte: Umetanje na kraju kružnog povezanog popisa
4. Umetanje na određeno mjesto u kružnom povezanom popisu
Za umetanje novog čvora na određeno mjesto u kružnom povezanom popisu prvo provjeravamo je li popis prazan.
- Ako jest i položaj nije 1 tada ispisujemo poruku o pogrešci jer pozicija ne postoji na listi. ja
- f the položaj je 1 onda stvaramo novi čvor i učiniti da ukaže na sebe.
- Ako lista nije prazna kreiramo novi čvor i prijeđite popisom kako biste pronašli ispravnu točku umetanja.
- Ako je položaj je 1 umećemo novi čvor na početku tako da prema tome prilagodite kazaljke.
- Za ostale pozicije prelazimo kroz listu dok ne dođemo do željene pozicije i ubacimo novi čvor ažuriranjem pokazivača.
- Ako je novi čvor umetnut na kraju, također ažuriramo trajati pokazivač za referencu na novi čvor održavajući kružnu strukturu popisa.
Umetanje na određeno mjesto u kružnom povezanom popisu Pristup korak po korak:
- Ako trajati je nullptr i poz nije 1 ispisati ' Neispravna pozicija! '.
- Inače Stvorite novi čvor s danim podacima.
- Umetni na početak: Ako je pos 1, ažurirajte pokazivače i vratite zadnje.
- Popis prijelaza: Petlja za pronalaženje točke umetanja; print 'Neispravna pozicija!' ako je izvan granica.
- Umetni čvor: Ažurirajte pokazivače za umetanje novog čvora.
- Zadnje ažuriranje: Ako se umetne na kraju ažuriranja trajati .
#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 );
Izlaz
Original list: 2 3 4 List after insertions: 2 5 3 4
Vremenska složenost: O(n) moramo proći kroz popis kako bismo pronašli određenu poziciju.
Pomoćni prostor: O(1)
