Infogning i cirkulär enkellänkad lista
I den här artikeln kommer vi att lära oss hur man infogar en nod i en cirkulär länkad lista. Infogning är en grundläggande operation i länkade listor som innebär att en ny nod läggs till i listan. I en cirkulär länkad lista ansluter den sista noden tillbaka till den första noden och skapar en loop.
Det finns fyra huvudsakliga sätt att lägga till objekt:
- Infoga i en tom lista
- Infogning i början av listan
- Infogning i slutet av listan
- Infogning på en specifik plats i listan
Fördelar med att använda en svanspekare istället för en huvudpekare
Vi måste gå igenom hela listan för att infoga en nod i början. Också för att infogas i slutet måste hela listan passeras. Om istället för start pekare tar vi en pekare till den sista noden så i båda fallen kommer det inte att finnas något behov av att gå igenom hela listan. Så insättning i början eller slutet tar konstant tid oavsett längden på listan.
1. Infoga i en tom lista i den cirkulära länkade listan
För att infoga en nod i en tom cirkulär länkad lista skapas en ny nod med den givna datauppsättningen dess nästa pekare att peka på sig själv och uppdaterar sista pekare för att hänvisa till detta ny nod .
Infoga i en tom lista Steg-för-steg tillvägagångssätt:
- Kontrollera om sista är inte nullptr . Om sann återvända sista (listan är inte tom).
- Skapa annars en ny nod med de angivna uppgifterna.
- Ställ in nya noder nästa pekare att peka på sig själv (cirkulär länk).
- Uppdatera sista att peka på ny nod och lämna tillbaka den.
För att läsa mer om infogning i en tom lista Se: Infoga i en tom lista i den cirkulära länkade listan
2. Infogning i början i cirkulär länkad lista
För att infoga en ny nod i början av en cirkulär länkad lista
- Vi skapar först ny nod och tilldela minne för det.
- Om listan är tom (indikeras av att den sista pekaren är NULL ) vi gör ny nod peka på sig själv.
- Om listan redan innehåller noder ställer vi in nya noder nästa pekare att peka på nuvarande huvud på listan (som är sist->nästa )
- Uppdatera sedan den sista nodens nästa pekare för att peka på ny nod . Detta bibehåller listans cirkulära struktur.
Infogning i början i cirkulär länkad lista För att läsa mer om Insättning i början Se: Infogning i början i cirkulär länkad lista
3. Infogning i slutet i cirkulär länkad lista
För att infoga en ny nod i slutet av en cirkulär länkad lista skapar vi först den nya noden och allokerar minne för den.
- Om listan är tom (medelvärde sista eller svans pekare varelse NULL ) initialiserar vi listan med ny nod och få den att peka på sig själv för att bilda en cirkulär struktur.
- Om listan redan innehåller noder ställer vi in nya noder nästa pekare att peka på nuvarande huvud (vilket är svans->nästa )
- Uppdatera sedan nuvarande svans nästa pekare att peka på ny nod .
- Äntligen uppdaterar vi svanspekare till ny nod.
- Detta kommer att säkerställa att ny nod är nu sista noden i listan samtidigt som den cirkulära kopplingen bibehålls.
Infogning i slutet i cirkulär länkad lista För att läsa mer om insättning i slutet, se: Infogning i slutet i cirkulär länkad lista
4. Infogning på specifik plats i cirkulär länkad lista
För att infoga en ny nod på en specifik position i en cirkulär länkad lista kontrollerar vi först om listan är tom.
- Om det är och placera är inte 1 sedan skriver vi ut ett felmeddelande eftersom positionen inte finns i listan. jag
- f den placera är 1 sedan skapar vi ny nod och få den att peka på sig själv.
- Om listan inte är tom skapar vi ny nod och gå igenom listan för att hitta rätt insättningspunkt.
- Om placera är 1 vi sätter in ny nod i början genom att justera pekarna därefter.
- För andra positioner går vi igenom listan tills vi når önskad position och sätter in ny nod genom att uppdatera pekarna.
- Om den nya noden infogas i slutet uppdaterar vi också sista pekare för att referera till den nya noden som bibehåller listans cirkulära struktur.
Infogning på specifik plats i cirkulär länkad lista Steg-för-steg tillvägagångssätt:
- Om sista är nullptr och pos är inte 1 skriv ut ' Ogiltig position! '.
- Skapa annars en ny nod med givna data.
- Infoga i början: Om pos är 1 uppdatera pekarna och returnera sist.
- Traverslista: Slinga för att hitta insättningspunkten; print 'Ogiltig position!' om utanför gränserna.
- Infoga nod: Uppdatera pekare för att infoga den nya noden.
- Uppdatering senast: Om det infogas i slutet av uppdateringen sista .
#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 );
Produktion
Original list: 2 3 4 List after insertions: 2 5 3 4
Tidskomplexitet: O(n) vi måste gå igenom listan för att hitta den specifika positionen.
Hjälputrymme: O(1)
