[C] 단일 연결 리스트 (Simple Linked List)

출처 - C로 배우는 알고리즘 (이재규 지음)

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

typedef struct _node
{
	int key;
	struct _node *next;
}node;

void init_list();			// head와 tail 생성 및 초기화
node *insert_after(int key, node *t);	// 매개변수로 넘겨준 노드 다음에 새로운 노드 추가
int delete_next(node *t);		// 매개변수로 넘겨준 노드 다음 노드 삭제
node *find_node(int k);			// 매개변수로 넘겨준 key 값을 가지는 노드를 검색
int delete_node(int k);			// 매개변수로 넘겨준 key 값을 가지는 노드를 삭제
node *insert_node(int k, int t);	// k를 key값으로 가지는 노드 앞에 t를 key값으로 가지는 노드 추가
node *ordered_insert(int k);		// 기존 노드에 오름차순하여 매개변수로 넘겨준 k를 추가
void print_list(node *t);		// 매개변수로 넘겨준 노드부터 시작해서 끝까지 출력
node *delete_all();			// 모든 노드를 삭제(head와 tail은 삭제 안함, head->next가 tail을 가르키도록 초기화)

node *head, *tail;

int main(int argc, char *argv[], char **env)
{
	node *t = NULL;
	init_list();		// head와 tail 메모리 할당 및 초기화
    
	ordered_insert(10);	// 오름차순 정렬로 노드를 하나씩 할당함
	ordered_insert(5);
	ordered_insert(8);
	ordered_insert(3);
	ordered_insert(1);
	ordered_insert(7);
	ordered_insert(8);
    
	// 제대로 정렬되서 들어갔는지 확인
	printf("Initial Linked list is\n");
	print_list(head->next);
    
	// 4를 키값으로 가지는 노드 검색
	printf("Finding 4 is %ssuccessful\n", find_node(4) == tail ? "un" : "");
	puts("");
    
	// 5를 키값으로 가지는 노드 검색
	t = find_node(5);
	printf("Finding 5 is %ssuccessful\n", t == tail ? "un" : "");
	puts("");
    
	// 5 다음에 9를 추가
	printf("Inserting 9 after 5\n");
	insert_after(9, t);
	print_list(head->next);
    
	// 맨 마지막 다음 노드 삭제 시도(즉 tail을 삭제하려고 함)
	t = find_node(10);
	printf("Deleting next last node\n");
	delete_next(t);
	print_list(head->next);
    
	// 3 다음 노드를 삭제 시도
	t = find_node(3);
	printf("Deleting next 3\n");
	delete_next(t);
	print_list(head->next);
    
	// 키값이 3인 노드를 찾아 그 노드 앞에 키값으로 2를 가지는 노드 추가
	printf("Insert node 2 before 3\n");
	insert_node(3, 2);
	print_list(head->next);
    
	// 키값이 2인 노드를 찾아서 삭제
	printf("Deleting node 2\n");
	if(!delete_node(2))
	{
		printf("deleting 2 is unsuccessful");
	}
	print_list(head->next);
    
	// 키값이 11인 노드를 찾아서 삭제
	printf("Deleting node 11\n");
	if(!delete_node(11))
	{
	printf("deleting 11 is unsuccessful\n");
	}
	print_list(head->next);
    
	// 키값이 1인 노드를 찾아서 삭제
	printf("Deleting node 1\n");
	delete_node(1);
	print_list(head->next);
    
	// 모든 노드 삭제
	printf("Deleting all node\n");
	delete_all();
	print_list(head->next);
    
	return 0;
}

void init_list()
{
	head = (node *)calloc(sizeof(node), 1); // head 노드 메모리 할당
	tail = (node *)calloc(sizeof(node), 1); // tail 노드 메모리 할당
    
	head->next = tail; // head 노드가 가리키는 다음 노드를 tail로 초기화
	tail->next = tail; // tail 노드가 가리키는 다음 노드를 tail로 초기화 (자기자신)
}
node *insert_after(int key, node *t)
{
	node *s = NULL;
    
	s = (node *)calloc(sizeof(node), 1); // 노드 메모리 할당
    
	s->key = key;		// 새로 생성된 노드에 매개변수로 받아온 key값으로 초기화
	s->next = t->next;	// 새로 생성된 노드가 가리키는 다음 노드를 매개변수로 받아온 노드가 가리키는 다음 노드로 초기화
	t->next = s;		// 매개변수로 받아온 노드가 가리키는 다음 노드를 새로 생성된 노드로 초기화
    
	return s;
}

int delete_next(node *t)
{
	node *s = NULL;
    
	if(t->next == tail) // 삭제하려는 다음 노드가 tail이면 0을 반환하며 종료
	{
		return 0;
	}
    
	s = t->next;			// 임시 포인터 변수가 삭제하려는 다음 노드를 가리키도록 함
	t->next = t->next->next;	// 매개변수로 넘겨받은 노드가 가리키는 노드를 매개변수 노드의 다음 다음 노드로 초기화
	free(s);			// 삭제할 노드를 가리키고 있던 임시 포인터 변수가 가리키는 메모리 해제
    
	return 1;
}

// 찾는 값이 없는경우 tail이 반환 됨.
node *find_node(int k)
{
	node *s = NULL;
    
	s = head->next; // 처음부터
    
	while(s->key != k && s != tail) // key 값이 다르거나 현재 노드가 tail이 아니면 반복
	{
		s = s->next; // 다음 노드로 넘어감
	}
    
	return s;
}
int delete_node(int k)
{
	node *s = NULL;
	node *p = NULL;
	p = head;
	s = p->next;
    
	while(s->key != k && s != tail) // key 값이 다르거나 현재 노드가 tail이 아니면 반복
	{
		p = p->next; // 다음 노드로 넘어감
		s = s->next; // s는 p노드의 다음 노드
	}
    
	if(s != tail)
	{
		p->next = s->next; // 삭제하려는 노드의 이전 노드가 삭제하려는 노드의 다음 노드를 가리키도록 함
		free(s); // 노드 삭제
		return 1;
	}
	else
	{
		return 0;
	}
}

node *insert_node(int k, int t)
{
	node *seeker;
	node *prev;
	node *r;
    
	prev = head;
	seeker = prev->next;
    
	while(seeker->key != k && seeker != tail) // key 값이 다르거나 현재 노드가 tail이 아니면 반복
	{
		prev = prev->next;	// 다음 노드로 넘어감
		seeker = prev->next;	// seeker는 prev 노드의 다음 노드
	}
    
	if(seeker != tail)
	{
		r = (node *)calloc(sizeof(node), 1); // 노드 생성
		r->key = t;		// 생성된 노드의 key 값을 매개변수로 받아온 key값으로 초기화
		prev->next = r;		// 이전 노드가 가리키는 다음 노드를 새로 생성된 노드로 초기화
		r->next = seeker;	// 새로 생성된 노드가 가리키는 다음 노드를 매개변수로 받아온 k를 key값으로 가지는 노드로 초기화
	}
    
	return prev->next; // r을 리턴시키면 안되는 이유는 k를 찾지 못했을 경우 r이 생성이 안 되기 때문
}

node *ordered_insert(int k)
{
	node *seeker = NULL;
	node *prev = NULL;
	node *r = NULL;
    
	prev = head;
	seeker = prev->next;
    
	while(seeker->key <= k && seeker != tail) // 노드의 key 값이 매개변수로 받아온 k 이하이거나 노드가 tail이 아니면 반복
	{
		prev = prev->next;	// 다음 노드로 넘어감
		seeker = prev->next;	// seeker는 prev 다음 노드를 가리키도록 함
	}
    
	r = (node *)calloc(sizeof(node), 1); // 노드 생성
	r->key = k;		// 새로 생성된 노드의 key 값을 매개변수로 받아온 k로 초기화
	prev->next = r;		// 매개변수 k보다 큰 값을 key로 가진 노드의 이전 노드가 가리키는 다음 노드를 새로 생성된 노드로 초기화
	r->next = seeker;	// 매개변수 k를 key 값으로 가지는 새로 생성된 노드가 가리키는 다음 노드를 k보다 큰 값을 가지는 노드로 초기화
    
	return r;
}

// 매개변수로 받은 노드부터 시작해서 끝까지 노드의 key 값을 출력해 줌
void print_list(node *t)
{
	while(t != tail)
	{
		printf("%-8d", t->key);
		t = t->next;
	}
    
	puts("\n");
}

// 모든 노드를 삭제(head, tail 제외)하고 head 노드가 가리키는 다음 노드를 tail로 초기화
node *delete_all()
{
	node *s = NULL;
	node *t = NULL;
    
	t = head->next;
    
	while(t != tail)
	{
		s = t;
		t = t->next;
		free(s);
	}
    
	head->next = tail;
    
	return head;
}