Įterpimas į žiedinį atskirai susietą sąrašą
Šiame straipsnyje sužinosime, kaip įterpti mazgą į apskritą susietą sąrašą. Įterpimas yra pagrindinė susietų sąrašų operacija, kuri apima naujo mazgo įtraukimą į sąrašą. Apvaliame susietame sąraše paskutinis mazgas vėl prisijungia prie pirmojo mazgo ir sukuria kilpą.
Yra keturi pagrindiniai elementų pridėjimo būdai:
- Įterpimas į tuščią sąrašą
- Įterpimas sąrašo pradžioje
- Įterpimas sąrašo pabaigoje
- Įterpimas į konkrečią sąrašo vietą
Uodegos rodyklės, o ne galvos rodyklės, naudojimo pranašumai
Turime pereiti visą sąrašą, kad įterptume mazgą pradžioje. Taip pat norint įterpti į pabaigą, reikia perbraukti visą sąrašą. Jei vietoj pradėti žymeklį perkeliame į paskutinį mazgą, tada abiem atvejais nereikės kirsti viso sąrašo. Taigi įterpimas į pradžią arba pabaigą trunka pastoviai, nepriklausomai nuo sąrašo ilgio.
1. Įterpimas į tuščią sąrašą apskrito susieto sąrašo
Norėdami įterpti mazgą į tuščią apskritą susietų sąrašą, sukuriamas a naujas mazgas su pateiktais duomenimis nustato kitą žymeklį, nukreipiantį į save, ir atnaujina paskutinis nuoroda į tai naujas mazgas .
Įterpimas į tuščią sąrašą Žingsnis po žingsnio metodas:
- Patikrinkite, ar paskutinis nėra nullptr . Jeigu tiesa grąžinti paskutinis (sąrašas nėra tuščias).
- Kitu atveju sukurkite a naujas mazgas su pateiktais duomenimis.
- Nustatykite nauji mazgai kitas žymeklis, rodantis į save (apvali nuoroda).
- Atnaujinti paskutinis nurodyti į naujas mazgas ir grąžinti.
Norėdami sužinoti daugiau apie įterpimą į tuščią sąrašą, žr. Įterpimas į tuščią sąrašą apskrito susieto sąrašo
2. Įterpimas apskrito susieto sąrašo pradžioje
Norėdami įterpti naują mazgą apskrito susieto sąrašo pradžioje
- Pirmiausia sukuriame naujas mazgas ir paskirstykite jam atmintį.
- Jei sąrašas tuščias (nurodomas paskutinis žymeklis NULL ) gaminame naujas mazgas rodo į save.
- Jei sąraše jau yra mazgų, nustatome nauji mazgai kitas žymeklis, nurodantis į dabartinė galva sąrašo (tai yra paskutinis->kitas )
- Tada atnaujinkite kitą paskutinio mazgo žymeklį, kad nukreiptumėte į naujas mazgas . Taip išlaikoma apskrita sąrašo struktūra.
Įterpimas apskrito susieto sąrašo pradžioje Norėdami daugiau sužinoti apie įterpimą pradžioje, žr. Įterpimas apskrito susieto sąrašo pradžioje
3. Įterpimas apskrito susieto sąrašo pabaigoje
Norėdami įterpti naują mazgą apskrito susieto sąrašo pabaigoje, pirmiausia sukuriame naują mazgą ir skiriame jam atmintį.
- Jei sąrašas tuščias (tai paskutinis arba uodega rodyklė esmė NULL ) inicijuojame sąrašą su naujas mazgas ir nukreipiant jį į save, kad susidarytų apskrita struktūra.
- Jei sąraše jau yra mazgų, nustatome nauji mazgai kitas žymeklis, nurodantis į dabartinė galva (tai yra uodega-> kitas )
- Tada atnaujinkite dabartinė uodega kitas žymeklis, nurodantis į naujas mazgas .
- Galiausiai atnaujiname uodegos rodyklė prie naujas mazgas.
- Tai užtikrins, kad naujas mazgas dabar yra paskutinis mazgas sąraše, išlaikant žiedinį ryšį.
Įterpimas apskrito susieto sąrašo pabaigoje Norėdami daugiau sužinoti apie įterpimą pabaigoje, žr. Įterpimas apskrito susieto sąrašo pabaigoje
4. Įterpimas tam tikroje apskritimo susieto sąrašo vietoje
Norėdami įterpti naują mazgą tam tikroje apskrito susieto sąrašo vietoje, pirmiausia patikriname, ar sąrašas tuščias.
- Jei yra ir padėtis nėra 1 tada išspausdiname klaidos pranešimą, nes pozicijos sąraše nėra. aš
- f padėtis yra 1 tada sukuriame naujas mazgas ir nukreipti tai į save.
- Jei sąrašas nėra tuščias, sukuriame naujas mazgas ir pereikite sąrašą, kad surastumėte tinkamą įterpimo tašką.
- Jei padėtis yra 1 įdedame naujas mazgas pradžioje atitinkamai pakoreguodami rodykles.
- Kitose pozicijose važiuojame per sąrašą, kol pasiekiame norimą padėtį ir įterpiame naujas mazgas atnaujinant rodykles.
- Jei naujas mazgas įterpiamas pabaigoje, mes taip pat atnaujiname paskutinis žymeklis, nurodantis naują mazgą, išlaikantį apskritą sąrašo struktūrą.
Įterpimas tam tikroje apskritimo susieto sąrašo vietoje Žingsnis po žingsnio metodas:
- Jeigu paskutinis yra nullptr ir poz nėra 1 spausdinti' Neteisinga pozicija! “.
- Kitu atveju sukurkite naują mazgą su nurodytais duomenimis.
- Įterpti pradžioje: Jei poz. 1 atnaujinimo rodyklės ir grįžkite paskutinę.
- Traversų sąrašas: Sukurkite kilpą, kad surastumėte įterpimo tašką; spausdinti 'Neteisinga padėtis!' jei už ribų.
- Įterpti mazgą: Atnaujinkite nuorodas, kad įterptumėte naują mazgą.
- Paskutinis atnaujinimas: Jei įterptas atnaujinimo pabaigoje paskutinis .
#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 );
Išvestis
Original list: 2 3 4 List after insertions: 2 5 3 4
Laiko sudėtingumas: O(n) turime pereiti sąrašą, kad surastume konkrečią vietą.
Pagalbinė erdvė: O(1)
