[C] 이중 연결 리스트 (Double Linked List)

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

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

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

void init_dlist(void);			// head와 tail 메모리 할당 및 next, prev 초기화
node *insert_node_ptr(int k, node *t);	// 매개변수 t노드의 앞에 매개변수 k를 key 값으로 가지는 노드를 추가
int delete_node_ptr(node *p);		// 매개변수 p노드를 삭제
node *find_node(int k);			// 매개변수 k를 key 값으로 가지는 노드 검색
int delete_node(int k);			// 매개변수 k를 key 값으로 가지는 노드를 삭제, 여러개일 경우 맨 앞의 노드만 삭제
node *insert_node(int t, int k);	// 매개변수 t를 key 값으로 가지는 노드가 있으면, 해당 노드 앞에 매개변수 k를 key 값으로 가지는 노드 추가
node *ordered_insert(int k);		// 오름차순으로 하여 매개변수 k를 key 값으로 가지는 노드 추가
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_dlist();

	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 다음에 7을 추가
	printf("Inserting 7 before 5\n");
	insert_node_ptr(7, t);
	print_list(head->next);

	// 3을 key 값으로 가지는 노드를 찾아 삭제
	t = find_node(3);
	printf("Deleting Node having key Value 3\n");
	delete_node_ptr(t);
	print_list(head->next);

	// 키값이 10인 노드를 찾아 그 노드 앞에 키값으로 2를 가지는 노드 추가
	printf("Insert node 2 before 10\n");
	insert_node(10, 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 1\n");
	if(!delete_node(1))
	{
		printf("deleting 11 is unsuccessful\n");
	}
	print_list(head->next);

	printf("Inserting 15 at first\n");
	insert_node_ptr(15, head->next);
	print_list(head->next);

	// 모든 노드 삭제
	printf("Deleting all node\n");
	delete_all();
	print_list(head->next);

	return 0;
}

void init_dlist(void)
{
	head = (node *)calloc(sizeof(node), 1); // head 노드 메모리 할당
	tail = (node *)calloc(sizeof(node), 1); // tail 노드 메모리 할당
	head->next = tail; // haed가 가리키는 다음 노드는 tail
	head->prev = head; // head가 가리키는 이전 노드는 자기자신
	tail->next = tail; // tail이 가리키는 다음 노드는 자기자신
	tail->prev = head; // tail이 가리키는 이전 노드는 head
}

node *insert_node_ptr(int k, node *t)
{
	node *new_node = NULL;

	if(t == head) // head 앞에는 노드 추가 불가능
	{
		return NULL;
	}

	new_node = (node *)calloc(sizeof(node), 1);
	new_node->key = k;

	t->prev->next = new_node;
	new_node->prev = t->prev;
	t->prev = new_node;
	new_node->next = t;

	return new_node;
}

int delete_node_ptr(node *p)
{
	if(p == head || p == tail)
	{
		return 0;
	}

	p->prev->next = p->next;
	p->next->prev = p->prev;

	free(p);

	return 1;
}

// 찾는 값이 없을 경우 tail 리턴
node *find_node(int k)
{
	node *s = NULL;

	s = head->next;

	while(s->key != k && s != tail)
	{
		s = s->next;
	}

	return s;
}

int delete_node(int k)
{
	node *s;

	s = find_node(k);

	if(s != tail)
	{
		delete_node_ptr(s);
		return 1;
	}

	return 0;
}

node *insert_node(int t, int k)
{
	node *s = NULL;
	node *i = NULL;

	s = find_node(t);

	if(s != tail)
	{
		i = insert_node_ptr(k, s);
	}

	return i;
}

node *ordered_insert(int k)
{
	node *s = NULL;
	node *i = NULL;

	s = head->next;

	while(s->key <= k && s != tail)
	{
		s = s->next;
	}

	i = insert_node_ptr(k, s);

	return i;
}

// 매개변수로 받은 노드부터 시작해서 끝까지 노드의 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;
}