[단일연결리스트] 노드 정렬 삽입(오름차순)

노드를 정렬하면서 삽입을 할 때 기본적인 고려사항은 크게 4가지가 있다. 

 

1. head == NULL

2. 가장 작은 값 삽입

3. 일반적인 경우

4. 가장 큰 값 삽입 

 

4가지 케이스 별로 오름차순으로 노드 정렬 삽입을 구현한 예제 코드이다. 

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node* next;
} node;

node* head = NULL;

void insertNodeSort() {
    node* newNode = (node*)malloc(sizeof(node));
    scanf("%d", &newNode->value);
    newNode->next = NULL;

    //head == NULL 일떄
    if (head == NULL) {
        head = newNode; 
        return; 
    }

    //삽입한 값이 가장 작을 때
    if (head->value > newNode->value) {
        newNode->next = head; 
        head = newNode;
        return; 
    }

    //중간에 끼어넣는 경우 
    //비교하기 전에 curNode 이동, 비교 후 preNode 이동 
    node* curNode, *preNode; 
    curNode = preNode = head; 
    
    while (curNode->next != NULL) {
        curNode = curNode->next;
        if (curNode->value > newNode->value) {
            newNode->next = curNode;
            preNode->next = newNode; 
        }
        preNode = preNode->next;
    }

    curNode->next = newNode; //가장 큰 값 삽입
}