Вмъкване в кръгъл единично свързан списък
В тази статия ще научим как да вмъкнем възел в кръгъл свързан списък. Вмъкването е основна операция в свързани списъци, която включва добавяне на нов възел към списъка. В кръгъл свързан списък последният възел се свързва обратно с първия възел, създавайки цикъл.
Има четири основни начина за добавяне на елементи:
- Вмъкване в празен списък
- Вмъкване в началото на списъка
- Вмъкване в края на списъка
- Вмъкване на конкретна позиция в списъка
Предимства от използването на показалеца на опашката вместо показалеца на главата
Трябва да обходим целия списък, за да вмъкнем възел в началото. Също така за вмъкване в края трябва да се премине през целия списък. Ако вместо на започнете указател вземаме указател към последния възел, тогава и в двата случая няма да има нужда да преминаваме през целия списък. Така че вмъкването в началото или в края отнема постоянно време, независимо от дължината на списъка.
1. Вмъкване в празен списък в кръговия свързан списък
За да вмъкнете възел в празен кръгъл свързан списък, създава a нов възел с дадените данни задава следващия си указател да сочи към себе си и актуализира последно указател към това нов възел .
Вмъкване в празен списък Подход стъпка по стъпка:
- Проверете дали последно не е nullptr . Ако вярно връщане последно (списъкът не е празен).
- В противен случай Създайте a нов възел с предоставените данни.
- Задайте нови възли следващ указател, който да сочи към себе си (кръгова връзка).
- Актуализация последно да посочи към нов възел и го върнете.
За да прочетете повече за вмъкването в празен списък, вижте: Вмъкване в празен списък в кръговия свързан списък
2. Вмъкване в началото на кръгъл свързан списък
За да вмъкнете нов възел в началото на кръгъл свързан списък
- Първо създаваме нов възел и разпределете памет за него.
- Ако списъкът е празен (обозначено с последния показалец, който е NULL ) ние правим нов възел сочи към себе си.
- Ако списъкът вече съдържа възли, тогава задаваме нови възли следващия указател, който да сочи към текуща глава от списъка (което е последно->следващо )
- След това актуализирайте следващия указател на последния възел, за да сочи към нов възел . Това поддържа кръговата структура на списъка.
Вмъкване в началото на кръгъл свързан списък За да прочетете повече за вмъкването в началото, вижте: Вмъкване в началото на кръгъл свързан списък
3. Вмъкване в края на кръгъл свързан списък
За да вмъкнем нов възел в края на кръгъл свързан списък, първо създаваме новия възел и заделяме памет за него.
- Ако списъкът е празен (означава последно или опашка указател е NULL ) ние инициализираме списъка с нов възел и го насочва към себе си, за да образува кръгла структура.
- Ако списъкът вече съдържа възли, тогава задаваме нови възли следващия указател, който да сочи към текуща глава (което е опашка->следващ )
- След това актуализирайте текущи опашки следващия указател, който да сочи към нов възел .
- Най-накрая актуализираме показалец на опашката към нов възел.
- Това ще гарантира, че нов възел сега е последен възел в списъка при запазване на кръговата връзка.
Вмъкване в края на кръгъл свързан списък За да прочетете повече за вмъкването в края, вижте: Вмъкване в края на кръгъл свързан списък
4. Вмъкване на конкретна позиция в кръгъл свързан списък
За да вмъкнем нов възел на конкретна позиция в кръгъл свързан списък, първо проверяваме дали списъкът е празен.
- Ако е и на позиция не е 1 след това отпечатваме съобщение за грешка, защото позицията не съществува в списъка. аз
- е позиция е 1 след това създаваме нов възел и го накарайте да сочи към себе си.
- Ако списъкът не е празен, създаваме нов възел и преминете през списъка, за да намерите правилната точка на вмъкване.
- Ако позиция е 1 вмъкваме нов възел в началото, като регулирате съответно стрелките.
- За други позиции преминаваме през списъка, докато достигнем желаната позиция и вмъкваме нов възел чрез актуализиране на указателите.
- Ако новият възел е вмъкнат в края, ние също актуализираме последно указател за препратка към новия възел, поддържайки кръговата структура на списъка.
Вмъкване на конкретна позиция в кръгъл свързан списък Подход стъпка по стъпка:
- Ако последно е nullptr и поз не е 1 печат ' Невалидна позиция! '.
- В противен случай Създайте нов възел с дадени данни.
- Вмъкване в началото: Ако pos е 1 актуализирайте указателите и се върнете последни.
- Траверсен списък: Цикъл за намиране на точката на вмъкване; print 'Невалидна позиция!' ако е извън границите.
- Вмъкване на възел: Актуализирайте указателите, за да вмъкнете новия възел.
- Последна актуализация: Ако се постави в края на актуализацията последно .
#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
Времева сложност: O(n) трябва да преминем през списъка, за да намерим конкретната позиция.
Помощно пространство: О(1)
