循環単一リンクリストへの挿入
この記事では、循環リンク リストにノードを挿入する方法を学びます。挿入は、リストに新しいノードを追加するリンク リストの基本的な操作です。循環リンク リストでは、最後のノードが最初のノードに接続してループを作成します。
項目を追加するには主に 4 つの方法があります。
- 空のリストへの挿入
- リストの先頭に挿入
- リストの最後に挿入
- リスト内の特定の位置に挿入
ヘッド ポインターの代わりにテール ポインターを使用する利点
リスト全体を走査して先頭にノードを挿入する必要があります。また、最後に挿入する場合は、リスト全体を走査する必要があります。の代わりに 始める pointer 最後のノードへのポインタを取得する場合、どちらの場合もリスト全体を走査する必要はありません。したがって、リストの長さに関係なく、先頭または末尾への挿入には一定の時間がかかります。
1. 循環リンクリスト内の空のリストへの挿入
空の循環リンク リストにノードを挿入すると、 新しいノード 指定されたデータを使用して、次のポインターがそれ自体を指すように設定し、 最後 これを参照するためのポインタ 新しいノード 。
空のリストへの挿入 段階的なアプローチ:
- どうかを確認してください 最後 ではありません nullptr 。もし 真実 戻る 最後 (リストは空ではありません)。
- それ以外の場合は、 新しいノード 提供されたデータを使用して。
- を設定します。 新しいノードの それ自体を指す次のポインター (循環リンク)。
- アップデート 最後 を指す 新しいノード そしてそれを返します。
空のリストへの挿入の詳細については、以下を参照してください。 循環リンク リスト内の空のリストへの挿入
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)
