[자료구조] C언어 연결리스트(Linked list) 노드 삽입

2021.04.09 - [C/자료구조] - [자료구조] C언어 연결리스트(Linked list) 생성 / 출력

[자료구조] C언어 연결리스트(Linked list) 생성 / 출력

 

*이 글의 예제는 연결리스트의 생성과 출력에 대해 요약한 전 글과 같은 구조체를 사용.

 

연결리스트의 첫 번째 노드로 삽입하기

char val의 값은 전 글에서 말했듯이 "월"으로 한다.

 

typedef struct node {
    char data;
    struct node* next;
} Node;
 
Node* head;
 
void insert1(char val) {
 
    Node* tmp;
    tmp = (Node*)malloc(sizeof(Node));
    tmp->data = val;
    tmp->next = head;
    head = tmp;
 
}

 

먼저 구조체 포인터 변수인 tmp를 만들고 새로운 노드를 생성해주기 위해 malloc으로 메모리를 할당해준다.

tmp->data에는 첫번째 노드에 들어갈 데이터 값val을 넣어주고, tmp->next에는 head값을 담는다.

head는 node1을 가리키고 있기 때문에 이 head값을 담은 tmp또한 node1을 가리키게 된다.

하지만 head는 모든 노드의 가장 맨 앞에서 첫번째 노드를 가리켜야 하므로, 첫번째 노드로 삽입하려는 tmp를 가리키도록 한다. head = tmp

 

 

원리를 그림으로 그리자면 위와 같다. tmp를 성공적으로 head 와 node1 사이에 넣은 것을 알 수 있다.

 

 

연결리스트의 중간에 노드 삽입하기

pre 노드가 주어졌을 때 이 노드 뒤에 삽입하는 방법

void insert(char val, Node* pre) {
    Node* tmp;
    tmp = (Node*)malloc(sizeof(Node));
    tmp->data = val;
    if (head == NULL) {
        head = tmp;
        tmp->next = NULL;
    }
    else {
        tmp->next = pre->next;
        pre->next = tmp;
    }
}
 

 

위에서 설명한 것과 비슷하게 먼저 구조체 포인터 변수 tmp를 생성하고 메모리 할당을 해준다.

tmp->data에 데이터 val을 넣고, head가 NULL이면 tmp가 첫번째 노드가 되므로 head가 tmp를 가리키게 한다.

head가 NULL이 아니라면 tmp는 pre->next의 값을 가지게 되는데 pre->next는 pre노드의 다음 노드를 가리키고 있었으므로 tmp는 그 노드를 가리키게 된다.

이 부분은 그림과 같이 보면 이해가 쉽다.

 

기존의 연결리스트의 구조는 왼쪽과 같다. pre노드가 그 다음 노드를 가리키고 있고, tmp라는 새 노드를 pre노드 뒤에 넣으려는 상황이다.

pre->next는 그 다음 노드를 가리키고 있으므로 tmp->next = pre->next 를 하게 되면 tmp는 pre 다음 노드를 가리키게 된다. (오른쪽 그림)

여기서 pre->next = tmp를 하게되면 pre노드는 tmp를 가리키므로 두 노드 사이에 tmp노드가 잘 삽입되었음을 알 수 있다. 

 

연결리스트의 마지막에 노드 삽입하기

마지막 노드를 찾고 그 뒤에 노드 삽입하는 방법

void insert2(char val) {
    Node* tmp, * ptr;
    tmp = (Node*)malloc(sizeof(Node));
    tmp->data = val;
    tmp->next = NULL;
    if (head == NULL) {
        head = tmp;
        return;
    }
    ptr = head;
    while (ptr->next != NULL)
        ptr = ptr->next;
    ptr->next = tmp;
}
 

 

삽입할 노드 tmp를 메모리 할당하여 생성, if문을 이용해 head가 NULL일 경우 바로 tmp를 가리키도록 해준다.

tmp에 데이터 값 val을 넣어주고 포인터 값은 아직 모르니 NULL을 넣어준다.

 

이제 마지막 노드를 찾을 while문을 돌 구조체 포인터 변수 ptr을 만들어 head를 가리키게 한다.

원리를 그림으로 보자면 다음과 같다.

 

1. ptr = head일 때, ptr->next는 node1을 가리킨다. node1은 NULL이 아니기 때문에 그대로 while문을 돌아 ptr = ptr->next로 다음 노드를 가리키게 된다.

2. ptr은 현재 node2를 가리킨다. ptr->next인 node3 또한 NULL값이 아니므로 while을 돌아 다음 노드를 가리키게 된다.

3. ptr은 node3를 가리키며 node3->next가 NULL이므로 while을 돌지 못하고 종료된다. 최종적으로 ptr은 마지막 노드인 node3을 가리키게 된다.

 

삽입할 노드 tmp는 마지막 노드인 node3 뒤에 와야하기 때문에 node3->next가 tmp를 가리키면 된다.

이렇게 마지막 노드를 삽입할 수 있다.

 

 

 

참조 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미