Innsetting i sirkulær enkeltlenket liste
I denne artikkelen vil vi lære hvordan du setter inn en node i en sirkulær koblet liste. Innsetting er en grunnleggende operasjon i koblede lister som innebærer å legge til en ny node i listen. I en sirkulær koblet liste kobles den siste noden tilbake til den første noden og skaper en løkke.
Det er fire hovedmåter å legge til elementer:
- Innsetting i en tom liste
- Innsetting i begynnelsen av listen
- Innsetting på slutten av listen
- Innsetting på en bestemt plassering i listen
Fordeler med å bruke en halepeker i stedet for en hodepeker
Vi må krysse hele listen for å sette inn en node i begynnelsen. Også for innsetting på slutten må hele listen krysses. Hvis i stedet for start peker tar vi en peker til den siste noden, så i begge tilfeller vil det ikke være behov for å krysse hele listen. Så innsetting i begynnelsen eller slutten tar konstant tid uavhengig av lengden på listen.
1. Sett inn i en tom liste i den sirkulære lenkede listen
For å sette inn en node i tom sirkulær lenket liste opprettes en ny node med de gitte datasettene sin neste peker til å peke på seg selv og oppdaterer siste peker for å referere til dette ny node .
Innsetting i en tom liste Steg-for-steg tilnærming:
- Sjekk om siste er ikke nullptr . Hvis ekte retur siste (listen er ikke tom).
- Ellers opprette en ny node med de oppgitte dataene.
- Still inn nye noder neste peker for å peke på seg selv (sirkulær lenke).
- Oppdater siste å peke på ny node og returnere den.
For å lese mer om innsetting i en tom liste Se: Innsetting i en tom liste i den sirkulære lenkede listen
2. Innsetting i begynnelsen i sirkulær lenket liste
For å sette inn en ny node i begynnelsen av en sirkulær koblet liste
- Vi lager først ny node og tildele minne til det.
- Hvis listen er tom (indikert ved at den siste pekeren er NULL ) lager vi ny node peke på seg selv.
- Hvis listen allerede inneholder noder, setter vi nye noder neste peker for å peke på nåværende hode av listen (som er siste->neste )
- Deretter oppdaterer den siste nodens neste peker for å peke på ny node . Dette opprettholder den sirkulære strukturen til listen.
Innsetting i begynnelsen i sirkulær lenket liste For å lese mer om innsetting i begynnelsen, se: Innsetting i begynnelsen i sirkulær lenket liste
3. Innsetting på slutten i sirkulær lenket liste
For å sette inn en ny node på slutten av en sirkulær koblet liste, oppretter vi først den nye noden og tildeler minne for den.
- Hvis listen er tom (gjennomsnittlig siste eller hale pekervesen NULL ) initialiserer vi listen med ny node og få den til å peke på seg selv for å danne en sirkulær struktur.
- Hvis listen allerede inneholder noder, setter vi nye noder neste peker for å peke på nåværende hode (som er hale->neste )
- Oppdater deretter nåværende hale neste peker for å peke på ny node .
- Til slutt oppdaterer vi halepeker til ny node.
- Dette vil sikre at ny node er nå siste node i listen samtidig som den sirkulære koblingen opprettholdes.
Innsetting på slutten i sirkulær lenket liste For å lese mer om innsetting på slutten, se: Innsetting på slutten i sirkulær lenket liste
4. Innsetting på spesifikk posisjon i sirkulært lenket liste
For å sette inn en ny node på en bestemt posisjon i en sirkulær lenket liste sjekker vi først om listen er tom.
- Hvis det er og posisjon er ikke 1 så skriver vi ut en feilmelding fordi posisjonen ikke finnes i listen. jeg
- f den posisjon er 1 så lager vi ny node og få det til å peke på seg selv.
- Hvis listen ikke er tom, oppretter vi ny node og gå gjennom listen for å finne riktig innsettingspunkt.
- Hvis posisjon er 1 vi setter inn ny node i begynnelsen ved å justere pekerne deretter.
- For andre posisjoner går vi gjennom listen til vi når ønsket posisjon og setter inn ny node ved å oppdatere pekerne.
- Hvis den nye noden settes inn på slutten, oppdaterer vi også siste peker for å referere til den nye noden som opprettholder den sirkulære strukturen til listen.
Innsetting på bestemt posisjon i sirkulært lenket liste Steg-for-steg tilnærming:
- Hvis siste er nullptr og pos er ikke 1 skriv ut ' Ugyldig stilling! '.
- Ellers opprette en ny node med gitte data.
- Sett inn i begynnelsen: Hvis pos er 1 oppdater pekere og returner sist.
- Traversliste: Løkke for å finne innsettingspunktet; skriv ut 'Ugyldig posisjon!' hvis det er utenfor grensene.
- Sett inn node: Oppdater pekere for å sette inn den nye noden.
- Oppdatering sist: Hvis det er satt inn på slutten av oppdateringen siste .
#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 );
Produksjon
Original list: 2 3 4 List after insertions: 2 5 3 4
Tidskompleksitet: O(n) må vi krysse listen for å finne den spesifikke posisjonen.
Hjelpeplass: O(1)
