Beillesztés a kör alakú, egyedileg összekapcsolt listába
Ebben a cikkben megtudjuk, hogyan lehet csomópontot beszúrni egy körkörös hivatkozásos listába. A beszúrás a csatolt listák alapvető művelete, amely magában foglalja egy új csomópont hozzáadását a listához. Egy kör alakú linkelt listában az utolsó csomópont visszacsatlakozik az első csomóponthoz, létrehozva egy hurkot.
Négy fő módja van az elemek hozzáadásának:
- Beillesztés egy üres listába
- Beszúrás a lista elejére
- Beillesztés a lista végére
- Beszúrás a lista egy adott helyére
A fejmutató helyett a farokmutató használatának előnyei
A teljes listát be kell járnunk, hogy az elejére beszúrjunk egy csomópontot. A végére történő beszúráshoz is a teljes listát kell végigjárni. Ha ahelyett a indul mutatót az utolsó csomópontra viszünk, akkor mindkét esetben nem kell a teljes listát bejárni. Tehát a beszúrás az elejére vagy a végére állandó időt vesz igénybe, függetlenül a lista hosszától.
1. Beszúrás egy üres listába a kör alakú linkelt listában
Csomópont beszúrásához üres körkörös hivatkozási listába létrejön a új csomópont a megadott adatokkal beállítja a következő mutatóját, amely önmagára mutat, és frissíti a utolsó mutató erre hivatkozva új csomópont .
Beillesztés egy üres listába Lépésről lépésre történő megközelítés:
- Ellenőrizze, ha utolsó nem nullptr . Ha igaz visszatérés utolsó (a lista nem üres).
- Ellenkező esetben hozzon létre a új csomópont a megadott adatokkal.
- Állítsa be a új csomópontok következő mutató önmagára mutat (kör alakú hivatkozás).
- Frissítés utolsó hogy rámutasson a új csomópont és adja vissza.
Ha többet szeretne megtudni az üres listába történő beillesztésről, olvassa el: Beszúrás egy üres listába a kör alakú linkelt listában
2. Beszúrás a kör alakú linkelt listába az elejére
Új csomópont beszúrása egy körkörös csatolt lista elejére
- Először létrehozzuk a új csomópont és foglaljon le neki memóriát.
- Ha a lista üres (ezt az utolsó mutató jelzi NULL ) elkészítjük a új csomópont mutat magára.
- Ha a lista már tartalmaz csomópontokat, akkor beállítjuk a új csomópontok következő mutató mutat a jelenlegi fej a listából (ami utolsó->következő )
- Ezután frissítse az utolsó csomópont következő mutatóját, hogy az a új csomópont . Ez megőrzi a lista körkörös szerkezetét.
Beszúrás a kör alakú linkelt lista elején Ha többet szeretne megtudni a beszúrásról az elején, tekintse meg: Beszúrás a kör alakú linkelt lista elején
3. Beszúrás a kör alakú linkelt lista végére
Új csomópont beszúrásához egy kör alakú linkelt lista végére először létrehozzuk az új csomópontot, és lefoglalunk számára memóriát.
- Ha a lista üres (értsd utolsó vagy farok mutató lény NULL ) inicializáljuk a listát a új csomópont és önmagára mutogatva körkörös szerkezetet alkot.
- Ha a lista már tartalmaz csomópontokat, akkor beállítjuk a új csomópontok következő mutató mutat a jelenlegi fej (ami farok->következő )
- Ezután frissítse a jelenlegi farok következő mutató mutat a új csomópont .
- Végül frissítjük a farokmutató a új csomópont.
- Ez biztosítja, hogy a új csomópont most a utolsó csomópont a listában a körkörös kapcsolat megtartása mellett.
Beszúrás a kör alakú linkelt lista végére Ha többet szeretne megtudni a beillesztésről a végén, olvassa el: Beszúrás a kör alakú linkelt lista végére
4. Beszúrás a kör alakú linkelt listában egy adott helyre
Ha új csomópontot szeretne beszúrni egy körkörös hivatkozású lista egy adott pozíciójába, először ellenőrizze, hogy a lista üres-e.
- Ha igen és a pozíció nem 1 akkor hibaüzenetet nyomtatunk, mert a pozíció nem létezik a listában. én
- f a pozíció van 1 majd létrehozzuk a új csomópont és önmagára mutassa.
- Ha a lista nem üres, létrehozzuk a új csomópont és a listán áthaladva megtalálja a megfelelő beszúrási pontot.
- Ha a pozíció van 1 beillesztjük a új csomópont elején a mutatók megfelelő beállításával.
- A többi pozíciónál addig haladunk a listán, amíg el nem érjük a kívánt pozíciót és beillesztjük a új csomópont a mutatók frissítésével.
- Ha az új csomópont a végére kerül beillesztésre, akkor frissítjük a utolsó mutató, amely az új csomópontra hivatkozik, megtartva a lista körkörös szerkezetét.
Beszúrás a kör alakú linkelt listában egy adott pozícióba Lépésről lépésre történő megközelítés:
- Ha utolsó van nullptr és pozíció nem 1 nyomtat Érvénytelen pozíció! '.
- Ellenkező esetben hozzon létre egy új csomópontot a megadott adatokkal.
- Beszúrás az elején: Ha a poz 1 frissítési mutatók és visszatérés utolsó.
- Bejárási lista: Hurok a beillesztési pont megkereséséhez; print 'Érvénytelen pozíció!' ha kívül esik a határokon.
- Csomópont beszúrása: Frissítse a mutatókat az új csomópont beillesztéséhez.
- Utolsó frissítés: Ha a frissítés végén beillesztik utolsó .
#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 );
Kimenet
Original list: 2 3 4 List after insertions: 2 5 3 4
Időbeli összetettség: O(n) a listát kell bejárnunk, hogy megtaláljuk a konkrét pozíciót.
Kiegészítő tér: O(1)
