순환 단일 연결 목록에 삽입
이번 포스팅에서는 순환 연결 리스트에 노드를 삽입하는 방법에 대해 알아보겠습니다. 삽입은 목록에 새 노드를 추가하는 것과 관련된 연결 목록의 기본 작업입니다. 순환 연결 리스트에서는 마지막 노드가 첫 번째 노드에 다시 연결되어 루프를 생성합니다.
항목을 추가하는 네 가지 주요 방법은 다음과 같습니다.
- 빈 목록에 삽입
- 목록의 시작 부분에 삽입
- 목록 끝에 삽입
- 목록의 특정 위치에 삽입
헤드 포인터 대신 테일 포인터를 사용할 때의 장점
처음에 노드를 삽입하려면 전체 목록을 순회해야 합니다. 또한 끝에 삽입하려면 전체 목록을 순회해야 합니다. 대신에 시작 포인터 마지막 노드에 대한 포인터를 가져오면 두 경우 모두 전체 목록을 탐색할 필요가 없습니다. 따라서 처음이나 끝 부분에 삽입하면 목록의 길이에 관계없이 일정한 시간이 걸립니다.
1. 순환 연결 리스트의 빈 리스트에 삽입
빈 순환 연결 리스트에 노드를 삽입하려면 새 노드 주어진 데이터를 사용하여 다음 포인터가 자신을 가리키도록 설정하고 업데이트합니다. 마지막 이것을 참조하는 포인터 새 노드 .
빈 목록에 삽입 단계별 접근 방식:
- 다음 사항을 확인하세요. 마지막 아니다 nullptr . 만약에 진실 반품 마지막 (목록이 비어 있지 않습니다).
- 그렇지 않으면 새 노드 제공된 데이터로.
- 설정 새로운 노드 자신을 가리키는 다음 포인터(원형 링크)
- 업데이트 마지막 ~을 가리키다 새 노드 그리고 그것을 돌려보내세요.
빈 목록에 삽입하는 방법에 대한 자세한 내용은 다음을 참조하세요. 순환 연결 리스트의 빈 리스트에 삽입
2. 순환 연결 리스트의 시작 부분에 삽입
순환 연결 리스트의 시작 부분에 새 노드를 삽입하려면
- 우리는 먼저 새 노드 그리고 거기에 메모리를 할당합니다.
- 목록이 비어 있는 경우(마지막 포인터가 NULL ) 우리는 새 노드 그 자체를 가리킨다.
- 목록에 이미 노드가 포함되어 있으면 다음을 설정합니다. 새로운 노드 다음 포인터를 가리키는 현재 머리 목록의 (이것은 마지막->다음 )
- 그런 다음 마지막 노드의 다음 포인터를 업데이트하여 새 노드 . 이는 목록의 순환 구조를 유지합니다.
순환 연결 리스트의 시작 부분에 삽입 처음에 삽입에 대해 자세히 알아보려면 다음을 참조하세요. 순환 연결 리스트의 시작 부분에 삽입
3. 순환 연결 리스트의 끝에 삽입
순환 연결 리스트의 끝에 새 노드를 삽입하려면 먼저 새 노드를 만들고 이에 대한 메모리를 할당합니다.
- 목록이 비어 있는 경우(평균 마지막 또는 꼬리 포인터 존재 NULL ) 우리는 다음과 같이 목록을 초기화합니다. 새 노드 원형 구조를 형성하기 위해 자신을 가리키도록 만듭니다.
- 목록에 이미 노드가 포함되어 있으면 다음을 설정합니다. 새로운 노드 다음 포인터를 가리키는 현재 머리 (이것은 꼬리->다음 )
- 그런 다음 업데이트 현재의 꼬리 다음 포인터를 가리키는 새 노드 .
- 마지막으로 우리는 꼬리 포인터 에 새 노드.
- 이렇게 하면 새 노드 지금은 마지막 노드 순환 연결을 유지하면서 목록에 포함됩니다.
순환 연결 리스트의 끝에 삽입 끝에 삽입에 대한 자세한 내용을 보려면 다음을 참조하십시오. 순환 연결 리스트의 끝에 삽입
4. 순환 연결 리스트의 특정 위치에 삽입
순환 연결 리스트의 특정 위치에 새 노드를 삽입하려면 먼저 리스트가 비어 있는지 확인합니다.
- 만약 그렇다면 위치 아니다 1 그런 다음 해당 위치가 목록에 존재하지 않기 때문에 오류 메시지를 인쇄합니다. 나
- f 위치 ~이다 1 그런 다음 우리는 새 노드 그리고 그것이 그 자체를 가리키도록 하세요.
- 목록이 비어 있지 않으면 새 노드 목록을 탐색하여 올바른 삽입 지점을 찾으세요.
- 만약 위치 ~이다 1 우리는 새 노드 처음에는 그에 따라 포인터를 조정하여 시작합니다.
- 다른 위치의 경우 원하는 위치에 도달할 때까지 목록을 탐색하고 새 노드 포인터를 업데이트하여.
- 새 노드가 끝에 삽입되면 우리는 또한 업데이트합니다 마지막 목록의 순환 구조를 유지하는 새 노드를 참조하는 포인터입니다.
순환 연결 리스트의 특정 위치에 삽입 단계별 접근 방식:
- 만약에 마지막 ~이다 nullptr 그리고 포스 아니다 1 '를 인쇄하다 위치가 잘못되었습니다! '.
- 그렇지 않으면 주어진 데이터로 새 노드를 만듭니다.
- 처음에 삽입: pos가 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
시간 복잡도: O(n) 특정 위치를 찾으려면 목록을 순회해야 합니다.
보조 공간: 오(1)
