[C 언어] 링크드 리스트 Node삽입 (Linked list node insert at nth node)

이번에는 단일 링크드 리스트(Single Linked List)에서... 특정 위치에 Node를 삽입하여 

저장하는 코드입니다.

head -> 1_번node -> 2_번Node -> 3_번Node -> NULL(자료의 끝)

위와 같이 Node들이 연결되어 있다면,

2번에 새로운 new_node를 삽입하는 함수를 만들었습니다.

void InsertNode(int data, int n);

data는 넣을 자료값, n은 몇번째 node에 넣을지 알려줍니다.

주의 사항은, Node를 1번부터 시작한다고 약속한 점이고,

추가로... 신규 new_node를 2번에 넣는다면, 기존 2번Node는 뒤로 밀리고,

새로운 new_node가 2번Node가 되는 형태로 작성하였으니...

아래의 for(i=0 ; i<n-2 ; i++) 내용에서 n-2로 위치를 지정한 것을 참고하세요.

또한 원하는 node로 이동하는 것이나, Node를 모두 탐색하는 것은

둘 다 현재_node = 현재_node->next; 의 방식을 사용하는 점이 동일합니다.

// insert a node at nth position
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    printf("Good bye");
}
 

이 코드에서 추가로 n번째 자료를 지우는 부분도 추가합니다.

지우는 함수도 Insert 함수와 유사합니다.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node * next;
}Node_T;
 
Node_T * head;
 
void InsertNode(int data, int n);
void DeleteNode(int n);
void PrintNodes(void);
 
// n should be from 1... (not 0)
// head -> 1_node -> 2_node -> 3_node ->...
// if Node is inserted 2 node...
// head -> 1_node -> new_node -> 2_node -> 3_node ->
void InsertNode(int data, int n)
{
    int i;
    Node_T * new_node = (Node_T*)malloc(sizeof(Node_T));
    new_node->data = data;
    new_node->next = NULL;
    if (n == 1)
    {
        new_node->next = head;
        head = new_node;
        return;
    }
 
    // travel from head to 'n'th node
    Node_T * temp2 = head;
    // stop before 'n'th node.
    // and insert node start 1. so... n-2
    for (i = 0; i < n-2; i++) 
    {
        temp2 = temp2->next;
    }
    new_node->next = temp2->next;
    temp2->next = new_node;
 
}
 
void DeleteNode(int n)
{
    int i;
    Node_T *temp1 = head;
    if (n == 1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }
    
    for (i = 0; i < n - 2; i++)
        temp1 = temp1->next;
        
    Node_T * del_node = temp1->next;
    temp1->next = del_node->next;
    free(del_node);
    
//    delete_node = NULL;  
    // 주의 delete_node가 가르키는 malloc된 공간을 free해야하며
    // delete_node 포인터 자체는... NULL로 하면 안된다.
    
}
 
void PrintNodes(void)
{
    // travel from head to last node
    Node_T * temp = head;
    
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
void main(void)
{
    head = NULL;
 
    InsertNode(6, 1);
    InsertNode(8, 2);
    InsertNode(2, 1);
    InsertNode(4, 2);
    InsertNode(1, 3);
    PrintNodes();
    DeleteNode(1);
    DeleteNode(2);
    PrintNodes();
    printf("Good bye");
}