Уметање у кружну једновезну листу
У овом чланку ћемо научити како да убаците чвор у кружну повезану листу. Уметање је основна операција у повезаним листама која укључује додавање новог чвора на листу. У кружној повезаној листи последњи чвор се повезује назад са првим чвором стварајући петљу.
Постоје четири главна начина за додавање ставки:
- Убацивање у празну листу
- Убацивање на почетак листе
- Убацивање на крај листе
- Уметање на одређено место на листи
Предности употребе репног показивача уместо показивача главе
Морамо да пређемо целу листу да бисмо уметнули чвор на почетку. Такође за уметање на крају цела листа мора да се пређе. Ако уместо на почети показивач узимамо показивач до последњег чвора, тада у оба случаја неће бити потребе да прелазимо целу листу. Дакле, уметање на почетку или на крају траје константно време без обзира на дужину листе.
1. Убацивање у празну листу у кружној повезаној листи
За уметање чвора у празну кружну повезану листу креира се а нови чвор са датим подацима поставља свој следећи показивач да указује на себе и ажурира последњи показивач за референцу на ово нови чвор .
Убацивање у празну листу Приступ корак по корак:
- Проверите да ли последњи није нуллптр . Ако истина повратак последњи (листа није празна).
- У супротном Креирајте а нови чвор са датим подацима.
- Подесите нови чвор следећи показивач који показује на себе (кружна веза).
- Ажурирај последњи да укаже на нови чвор и врати га.
Да бисте прочитали више о уметању у празну листу, погледајте: Уметање у празну листу у кружној повезаној листи
2. Убацивање на почетак у кружну повезану листу
Да бисте уметнули нови чвор на почетак кружне повезане листе
- Прво креирамо нови чвор и додели меморију за то.
- Ако је листа празна (означено тако што је последњи показивач НУЛЛ ) правимо нови чвор указати на себе.
- Ако листа већ садржи чворове онда постављамо нови чвор следећи показивач који показује на тренутна глава са листе (што је последњи->следећи )
- Затим ажурирајте следећи показивач последњег чвора тако да показује на нови чвор . Ово одржава кружну структуру листе.
Убацивање на почетак у кружну повезану листу Да бисте прочитали више о уметању на почетку, погледајте: Убацивање на почетак у кружну повезану листу
3. Уметање на крају у кружној повезаној листи
Да бисмо убацили нови чвор на крај кружне повезане листе, прво креирамо нови чвор и додељујемо меморију за њега.
- Ако је листа празна (сред последњи или реп показивач бића НУЛЛ ) иницијализујемо листу са нови чвор и чинећи га да укаже на себе да формира кружну структуру.
- Ако листа већ садржи чворове онда постављамо нови чвор следећи показивач који показује на тренутна глава (што је реп->следећи )
- Затим ажурирајте тренутни реп следећи показивач који показује на нови чвор .
- Коначно ажурирамо репни показивач то тхе нови чвор.
- Ово ће осигурати да се нови чвор је сада последњи чвор на листи уз одржавање кружне везе.
Уметање на крају у кружној повезаној листи Да бисте прочитали више о уметању на крају, погледајте: Уметање на крају у кружној повезаној листи
4. Уметање на одређену позицију у кружној повезаној листи
Да бисмо убацили нови чвор на одређену позицију у кружној повезаној листи, прво проверавамо да ли је листа празна.
- Ако јесте и положај није 1 онда штампамо поруку о грешци јер позиција не постоји на листи. И
- ф тхе положај је 1 онда стварамо нови чвор и учини да указује на себе.
- Ако листа није празна креирамо нови чвор и пређите преко листе да бисте пронашли исправну тачку уметања.
- Ако је положај је 1 убацујемо нови чвор на почетку одговарајућим подешавањем показивача.
- За остале позиције прелазимо кроз листу док не дођемо до жељене позиције и убацимо нови чвор ажурирањем показивача.
- Ако је нови чвор уметнут на крају, такође ажурирамо последњи показивач за референцу на нови чвор који одржава кружну структуру листе.
Уметање на одређену позицију у кружној повезаној листи Приступ корак по корак:
- Ако последњи је нуллптр и пос није 1 принт ' Неважећа позиција! '.
- У супротном, направите нови чвор са датим подацима.
- Убаци на почетку: Ако је пос 1 показивача ажурирања и врати се последњи.
- Листа прелаза: Петља да бисте пронашли тачку уметања; принт 'Неисправна позиција!' ако је ван граница.
- Уметни чвор: Ажурирајте показиваче да бисте уметнули нови чвор.
- Последње ажурирање: Ако се убаци на крају ажурирања последњи .
#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 );
Излаз
Original list: 2 3 4 List after insertions: 2 5 3 4
Временска сложеност: О(н) морамо да пређемо листу да бисмо пронашли одређену позицију.
Помоћни простор: О(1)
