Вставка в циклічний однозв’язаний список
У цій статті ми навчимося вставляти вузол у циклічний пов’язаний список. Вставка — це фундаментальна операція у зв’язаних списках, яка передбачає додавання нового вузла до списку. У циклічному пов’язаному списку останній вузол з’єднується з першим вузлом, створюючи цикл.
Є чотири основні способи додавання елементів:
- Вставка в порожній список
- Вставка на початку списку
- Вставка в кінці списку
- Вставка в певну позицію в списку
Переваги використання покажчика хвоста замість покажчика голови
Нам потрібно пройти весь список, щоб вставити вузол на початку. Крім того, для вставки в кінці потрібно пройти весь список. Якщо замість початок pointer ми беремо вказівник на останній вузол, тоді в обох випадках не буде необхідності проходити весь список. Таким чином, вставка на початку чи в кінці займає постійний час, незалежно від довжини списку.
1. Вставлення в порожній список у циклічному пов’язаному списку
Щоб вставити вузол у порожній циклічний пов’язаний список, створюється a новий вузол із заданими даними встановлює свій наступний вказівник на себе та оновлює останній покажчик для посилання на це новий вузол .
Вставка в порожній список Покроковий підхід:
- Перевірте, якщо останній не є nullptr . Якщо правда повернення останній (список не порожній).
- В іншому випадку Створіть a новий вузол з наданими даними.
- Встановіть новий вузол наступний покажчик, який вказує на себе (циклове посилання).
- оновлення останній вказувати на новий вузол і повернути його.
Щоб дізнатися більше про вставлення в порожній список, див. Вставлення в порожній список у циклічному пов’язаному списку
2. Вставка на початку кільцевого пов’язаного списку
Щоб вставити новий вузол на початку циклічного пов’язаного списку
- Спочатку ми створюємо новий вузол і виділити для нього пам'ять.
- Якщо список порожній (позначається останнім покажчиком NULL ) ми робимо новий вузол вказувати на себе.
- Якщо список уже містить вузли, ми встановлюємо новий вузол наступний покажчик, щоб вказати на діючий зав списку (що є останній->наступний )
- Потім оновіть наступний покажчик останнього вузла, щоб вказувати на новий вузол . Це зберігає циклічну структуру списку.
Вставка на початку кільцевого пов’язаного списку Щоб дізнатися більше про вставку на початку, зверніться до: Вставка на початку кільцевого пов’язаного списку
3. Вставка в кінець циклічного пов’язаного списку
Щоб вставити новий вузол у кінець циклічного пов’язаного списку, ми спочатку створюємо новий вузол і виділяємо для нього пам’ять.
- Якщо список порожній (знач останній або хвіст покажчик істоти NULL ) ми ініціалізуємо список за допомогою новий вузол і змушуючи його вказувати на себе, щоб утворити круглу структуру.
- Якщо список уже містить вузли, ми встановлюємо новий вузол наступний покажчик, щоб вказати на діючий зав (що є хвіст->наступний )
- Потім оновіть поточний хвіст наступний покажчик, щоб вказати на новий вузол .
- Нарешті ми оновлюємо вказівник хвоста до новий вузол.
- Це гарантує, що новий вузол зараз це останній вузол у списку, зберігаючи круговий зв’язок.
Вставка в кінець кільцевого пов’язаного списку Щоб дізнатися більше про вставку в кінці, зверніться до: Вставка в кінець кільцевого пов’язаного списку
4. Вставлення в конкретну позицію в циклічному пов’язаному списку
Щоб вставити новий вузол у певну позицію в циклічному пов’язаному списку, ми спочатку перевіряємо, чи список порожній.
- Якщо це і є положення не є 1 тоді ми друкуємо повідомлення про помилку, оскільки позиції немає в списку. я
- f положення є 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)
