[c언어] linked list 생성하기

오늘은 오름차순으로 값을 정렬하는 linked list를 만들어보겠습니다.

 

linked list를 생성하기 위해 필요한 것은 구조체와 head입니다.

구조체는 값을 저장할 변수와 다음 노드의 주소를 가르키는 포인터변수로 이루어져 있습니다.

head는 위에서 설명한 구조체 타입의 변수이고, linked list의 맨 처음 값을 가르키는 역할을 합니다. (그렇기 때문에 아무값도 저장되어있지 않습니다.) 

head는 linked list의 맨 앞에 새로운 값을 넣고 싶을 때 유용하기 때문에 사용합니다.

head 설명 

 

오름차순의 linked list를 생성할 때 필요한 조건은 3가지로 나눌 수 있습니다.

조건 1. linked list를 처음 만들 때 (즉, linked list에 아무것도 없는 상태에서 처음 값을 저장할 때)

조건 2. linked list에 있는 모든 값보다 클 때 (즉, linked list의 맨 마지막에 저장되어야 할 때)

조건 3. linked list에 있는 모든 값보다 작을 때, 또는 어떤 값보다 작고, 어떤 값보다는 클 때 (즉, linked list의 중간에 저장되어야 할 때)

 

조건 1 새로운 linked list 생성 전 상태를 그림으로 나타내면 다음과 같습니다.

조건 1 새로운 linked list 생성 후 상태를 그림으로 나타내면 다음과 같습니다.

head는 새로운 노드를 가르키고 새로운 노드는 NULL을 가르킵니다.

 

 

조건 2 새로운 linked list 생성 전 상태를 그림으로 나타내면 다음과 같습니다.

조건 2 새로운 linked list 생성 후 상태를 그림으로 나타내면 다음과 같습니다.

 

 

조건 3 새로운 linked list 생성 전 상태를 그림으로 나타내면 다음과 같습니다.

조건 3 새로운 linked list 생성 후 상태를 그림으로 나타내면 다음과 같습니다.

 

주의할 점은 조건 2,3번은 while문을 돌면서 새로 삽입할 값의 자리를 찾아야 한다는 점입니다.

그리고 head를 이용해서 linked list 전체를 출력할 수 있습니다.

 

이제 전체 코드를 공유하겠습니다.

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

struct NODE {
	int key;
	struct NODE* next;
};

int createNode(struct NODE* head, int n, int idx) {
	//조건 1
	if (idx == 0) {
		struct NODE* new_node = (struct NODE*)malloc(sizeof(struct NODE));
		new_node->key = n;
		new_node->next = NULL;
		head->next = new_node;
		return 1;
	}
	struct NODE* prev = head;
	while (prev) {
		if (n > prev->key) {
			//조건 2
			if (prev->next == NULL) {
				struct NODE* new_node = (struct NODE*)malloc(sizeof(struct NODE));
				new_node->key = n;
				new_node->next = NULL;
				prev->next = new_node;
				return 1;
			}
			//조건 3
			else if (n < (prev->next)->key) {
				struct NODE* new_node = (struct NODE*)malloc(sizeof(struct NODE));
				new_node->key = n;
				new_node->next = prev->next;
				prev->next = new_node;
				return 1;
			}
		}

		prev = prev->next;
	}
	return 0;
}

void printNode(struct NODE* head) {
	struct NODE* ptr = head->next;
	int i = 0;
	while (ptr) {
		printf("node[%d]: %d\n", i, ptr->key);
		ptr = ptr->next;
		i++;
	}
}
int main() {
	int arr[10] = { 5,6,4,2,1,3,7,9,8,10 };
	struct NODE* head = (struct NODE*)malloc(sizeof(struct NODE));
	head->key = (int)NULL;
	head->next = NULL;
	for (int i = 0; i < 10; i++) {
		createNode(head, arr[i], i);
	}

	printNode(head);

	free(head);
	return 0;
}