Ievietošana apļveida atsevišķi saistītajā sarakstā
Šajā rakstā mēs uzzināsim, kā ievietot mezglu apļveida saistītā sarakstā. Ievietošana ir būtiska darbība saistītajos sarakstos, kas ietver jauna mezgla pievienošanu sarakstam. Apļveida saistītā sarakstā pēdējais mezgls savienojas ar pirmo mezglu, izveidojot cilpu.
Ir četri galvenie veidi, kā pievienot vienumus:
- Ievietošana tukšā sarakstā
- Ievietošana saraksta sākumā
- Ievietošana saraksta beigās
- Ievietošana noteiktā vietā sarakstā
Priekšrocības, izmantojot astes rādītāju, nevis galvas rādītāju
Mums ir jāšķērso viss saraksts, lai sākumā ievietotu mezglu. Arī, lai ievietotu beigās, ir jāiziet viss saraksts. Ja tā vietā sākums kursoru mēs ņemam rādītāju uz pēdējo mezglu, tad abos gadījumos nebūs jāšķērso viss saraksts. Tātad ievietošana sākumā vai beigās aizņem nemainīgu laiku neatkarīgi no saraksta garuma.
1. Ievietošana tukšā sarakstā apļveida saistītajā sarakstā
Lai ievietotu mezglu tukšā apļveida saistīto sarakstā, tiek izveidots a jauns mezgls ar dotajiem datiem iestata nākamo rādītāju, kas norāda uz sevi, un atjaunina pēdējais rādītājs, lai atsauktos uz šo jauns mezgls .
Ievietošana tukšā sarakstā Soli pa solim pieeja:
- Pārbaudiet, vai pēdējais nav nullptr . Ja taisnība atgriezties pēdējais (saraksts nav tukšs).
- Pretējā gadījumā Izveidojiet a jauns mezgls ar sniegtajiem datiem.
- Iestatiet jauni mezgli nākamais rādītājs, kas norāda uz sevi (apļveida saite).
- Atjaunināt pēdējais lai norādītu uz jauns mezgls un atdod to.
Lai uzzinātu vairāk par ievietošanu tukšā sarakstā, skatiet: Ievietošana tukšā sarakstā apļveida saistītajā sarakstā
2. Ievietošana apļveida saistītā saraksta sākumā
Lai ievietotu jaunu mezglu apļveida saistītā saraksta sākumā
- Vispirms mēs izveidojam jauns mezgls un piešķiriet tam atmiņu.
- Ja saraksts ir tukšs (norāda ar pēdējo rādītāju NULL ) mēs izgatavojam jauns mezgls norāda uz sevi.
- Ja sarakstā jau ir mezgli, mēs iestatām jauni mezgli nākamais rādītājs, lai norādītu uz pašreizējā galva no saraksta (kas ir pēdējais->nākamais )
- Pēc tam atjauniniet pēdējā mezgla nākamo rādītāju, lai norādītu uz jauns mezgls . Tādējādi tiek saglabāta saraksta apļveida struktūra.
Ievietošana apļveida saistītā saraksta sākumā Lai uzzinātu vairāk par ievietošanu sākumā, skatiet: Ievietošana apļveida saistītā saraksta sākumā
3. Ievietošana apļveida saistītā saraksta beigās
Lai ievietotu jaunu mezglu apļveida saistītā saraksta beigās, vispirms izveidojam jaunu mezglu un piešķiram tam atmiņu.
- Ja saraksts ir tukšs (vidēji pēdējais vai asti rādītāja būtne NULL ) mēs inicializējam sarakstu ar jauns mezgls un liekot tai norādīt uz sevi, lai izveidotu apļveida struktūru.
- Ja sarakstā jau ir mezgli, mēs iestatām jauni mezgli nākamais rādītājs, lai norādītu uz pašreizējā galva (kas ir aste->nākamais )
- Pēc tam atjauniniet pašreizējās astes nākamais rādītājs, lai norādītu uz jauns mezgls .
- Visbeidzot mēs atjauninām astes rādītājs uz jauns mezgls.
- Tas nodrošinās, ka jauns mezgls tagad ir pēdējais mezgls sarakstā, vienlaikus saglabājot apļveida saikni.
Ievietošana apļveida saistītā saraksta beigās Lai uzzinātu vairāk par ievietošanu beigās, skatiet: Ievietošana apļveida saistītā saraksta beigās
4. Ievietošana noteiktā pozīcijā apļveida saistītajā sarakstā
Lai ievietotu jaunu mezglu noteiktā pozīcijā apļveida saistītā sarakstā, vispirms pārbaudām, vai saraksts ir tukšs.
- Ja tā ir un pozīciju nav 1 tad mēs izdrukājam kļūdas ziņojumu, jo pozīcija sarakstā nepastāv. es
- f pozīciju ir 1 tad mēs izveidojam jauns mezgls un likt tam norādīt uz sevi.
- Ja saraksts nav tukšs, mēs izveidojam jauns mezgls un šķērsojiet sarakstu, lai atrastu pareizo ievietošanas punktu.
- Ja pozīciju ir 1 mēs ievietojam jauns mezgls sākumā, attiecīgi pielāgojot rādītājus.
- Citām pozīcijām mēs šķērsojam sarakstu, līdz sasniedzam vēlamo pozīciju un ievietojam jauns mezgls atjauninot norādes.
- Ja jaunais mezgls tiek ievietots beigās, mēs arī atjauninām pēdējais rādītājs, lai atsauktos uz jauno mezglu, saglabājot saraksta apļveida struktūru.
Ievietošana noteiktā pozīcijā apļveida saistītā sarakstā Soli pa solim pieeja:
- Ja pēdējais ir nullptr un poz nav 1 drukāt' Nederīga pozīcija! '.
- Pretējā gadījumā izveidojiet jaunu mezglu ar norādītajiem datiem.
- Ievietot sākumā: Ja pozīcija ir 1, atjauniniet norādes un atgriezieties pēdējā.
- Traversu saraksts: Cilpa, lai atrastu ievietošanas punktu; drukāt 'Nederīga pozīcija!' ja ārpus robežām.
- Ievietot mezglu: Atjauniniet norādes, lai ievietotu jauno mezglu.
- Pēdējā atjaunināšana: Ja tas ir ievietots atjaunināšanas beigās pēdējais .
#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 );
Izvade
Original list: 2 3 4 List after insertions: 2 5 3 4
Laika sarežģītība: O(n) mums ir jāšķērso saraksts, lai atrastu konkrēto pozīciju.
Palīgtelpa: O(1)
