[c언어] linked list 추가/삭제하기

안녕하세요 지코딩입니다.

오늘은 linked list에 값을 추가 및 삭제하는 방법에 대해 알아보겠습니다.

 

오름차순의 linked list에 새로운 노드를 추가할 때 필요한 조건은 3가지로 나눌 수 있습니다.

조건 1. 이미 같은 값이 linked list에 존재할 때

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

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

 

조건 1의 경우에는 새로운 노드를 추가하는 함수를 탈출하면 됩니다.

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

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

 

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

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

 

이제 linked list의 맨 앞의 노드를 삭제하는 방법에 대해 알아보겠습니다.head가 첫번째 노드가 가르키고 있는 노드를 가르키게 한 후

삭제할 노드의 연결을 풀어주면 됩니다.

 

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

struct NODE {
	int key;
	struct NODE* next;
}node[7];

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

void printNode(struct NODE* head) {
	struct NODE* ptr = head->next;
	printf("print nodes\n");
	while (ptr) {
		printf("%d\n", ptr->key);
		ptr = ptr->next;
	}
}

void deleteNode(struct NODE* head) {
	struct NODE* temp = (struct NODE*)malloc(sizeof(struct NODE));
	temp = head->next;
	head->next = temp->next;
}
void main() {
	struct NODE* head = (struct NODE*)malloc(sizeof(struct NODE));
	head->key = (int)NULL;
	node[0].key = 10;
	node[1].key = 20;
	node[2].key = 40;
	head->next = &node[0];
	node[0].next = &node[1];
	node[1].next = &node[2];
	node[2].next = NULL;
	addNode(20, head);
	addNode(30, head);
	addNode(50, head);
	addNode(35, head);
	printNode(head);
	deleteNode(head);
	printNode(head);
}