[자료구조] 연결 리스트 (단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트)

연결 리스트

• 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동할 필요가 없는 리스트
• 포인터를 사용하여 데이터 연결
• 노드 
  • 데이터 필드 : 저장하고 싶은 데이터  
  • 링크 필드 : 다른 노드를 가리키는 포인터 저장

insert_first(head,value)	리스트의 첫번째에 value 추가
insert(head,pre,value)	리스트의 prev 노드 뒤에 value 추가
insert_last(head,value)	리스트의 마지막에 value 추가
delete_first(head)	리스트 첫번째 노드 삭제
delete(head,pre)	리스트의 prev 뒤의 노드 삭제
delete_last(head)	리스트의 마지막 노드 삭제
search(head,x)	노드 탐색
concat(head1,head2)	head1과 head2를 붙여 반환
reverse(head)	리스트를 뒤집어 반환
is_is_list(head,value)	value가 리스트에 있는지 확인
get_length(head)	리스트의 길이 반환
get_total(head)	리스트 내 데이터의 합 반환
get_entry(head,pos)	pos 위치의 데이터 반환
delete_by_key(head,key)	해당 데이터(key)를 갖고있는 노드 삭제
insert_pos(head,pos,value)	pos 위치에 value 추가
delete_pos(head,pos)	pos 위치 노드 삭제
print_list(head)	리스트 출력

단순 연결 리스트

• 노드들이 하나의 링크 필드를 가지며, 이 링크 필드를 이용하여 모든 노드들이 연결되어 있음
• 마지막 노드의 링크 필드 값은 NULL

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

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;
ListNode* insert_first(ListNode* head,element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}
ListNode* insert(ListNode* head, ListNode*pre, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}
ListNode* insert_last(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	ListNode* temp = head;
	p->data = value;
	p->link = NULL;

	while (temp->link != NULL)
		temp = temp->link;
	temp->link = p;
	return head;
}
ListNode* delete_first(ListNode* head) {
	if (head == NULL) return NULL;
	ListNode* removed;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}
ListNode* delete(ListNode* head,ListNode* pre) {
	ListNode* removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}
ListNode* delete_last(ListNode* head) {
	ListNode* temp = head;
	ListNode* prevTemp = NULL;
	ListNode* removed = NULL;
	if (head->link == NULL) {
		removed = head;
		free(removed);
		return NULL;
	}

	while (temp->link != NULL) {
		prevTemp = temp;
		temp = temp->link;
	}
	prevTemp->link = NULL;
	free(temp);

	return head;
}
ListNode* search(ListNode* head, element x) {
	ListNode* p = head;
	while (p != NULL) {
		if (p->data == x)
			return p;
		p = p->link;
	}
	return NULL;
}
ListNode* concat(ListNode* head1, ListNode* head2) {
	ListNode* p;
	if (head1 == NULL) return head2;
	else if (head2 == NULL)return head1;
	else {
		p = head1;
		while (p->link != NULL)
			p = p->link;
		p->link = head2;

		return p;
	}
}
ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	p = head; r = NULL; q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}
int is_in_list(ListNode* head, element value) {
	for (ListNode* p = head; p != NULL; p = p->link)
		if (p->data == value)
			return 1;
	return 0;
}
int get_length(ListNode* head) {
	int i = 0;
	for (ListNode* p = head; p != NULL; p = p->link)
		i++;
	return i;
}
int get_total(ListNode* head) {
	int total = 0;
	for (ListNode* p = head; p != NULL; p = p->link)
		total += p->data;
	return total;
}
element get_entry(ListNode* head, int pos) {
	if (pos<0 || pos>get_length(head))
		return NULL;
	int i = 0;
	for (ListNode* p = head; p != NULL; p = p->link) 
		if (i++ == pos)
			return p->data;
}
ListNode* delete_by_key(ListNode* head, int key) {
	if (head == NULL)
		return NULL;
	if (head->data == key) {
		//return head = delete_first(head);
		ListNode* temp = head;
		head = temp->link;
		free(temp);
		return head;
	}

	ListNode* p = head->link;
	ListNode* prevTemp = head;

	while (p != NULL && p->data != key) {
		prevTemp = p;
		p = p->link;
	}
	if (p == NULL)
		return head;

	prevTemp->link = p->link;
	free(p);
	return head;
}
ListNode* insert_pos(ListNode* head, int pos, element value) {
	ListNode* p = NULL;
	ListNode* prevTemp = NULL;
	int i = 0;
	if (pos<0 || pos>get_length(head))
		return NULL;

	if (pos == 0)
		return p = insert_first(head, value);

	p = head;
	while (i != pos) {
		prevTemp = p;
		p = p->link;
		i++;
	}
	return p = insert(head, prevTemp, value);
}
ListNode* delete_pos(ListNode* head, int pos) {
	ListNode* p = NULL;
	ListNode* prevTemp = NULL;
	int i = 0;

	if (pos<0 || pos>get_length(head))
		return NULL;
	if (pos == 0)
		return p = delete_first(head);

	p = head;
	while (i != pos) {
		prevTemp = p;
		p = p->link;
		i++;
	}
	return delete(head, prevTemp);
}
void print_list(ListNode* head) {
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d ->", p->data);
	printf("NULL\n");
}
int main(void) {
	ListNode* list1 = NULL, * list2 = NULL, * list3;
	//list1 = 30->20->10->를 만든다. 이때 10, 20, 30의 순으로 노드를 삽입한다. 
	list1 = insert_first(list1, 10);
	list1 = insert_first(list1, 20);
	list1 = insert_first(list1, 30);
	// list1을 출력 
	printf("list1 = ");
	print_list(list1);

	//list1의 맨 앞 노드를 삭제한다 즉, list1 = 20->30-> 
	list1 = delete_first(list1);
	// list1을 출력 
	print_list(list1);

	//list2 = 11->22->33->44->를 만든다. 이때 11, 22, 33, 44의 순으로 노드를 삽입한다. 
	list2 = insert_first(list2, 11);
	list2 = insert_last(list2, 22);
	list2 = insert_last(list2, 33);
	list2 = insert_last(list2, 44);
	// list2를 출력 
	print_list(list2);

	// list2의 맨 뒤 노드를 삭제한다. 즉, list2 = 11->22->33-> 
	list2 = delete_last(list2);

	// list2를 출력 
	print_list(list2);

	//list2를 역순으로 바꾼 리스트를 list3가 가리키게 한다. list3 = 33->22->11->를 만든다.
	list3 = reverse(list2);

	//list3를 출력한다.
	print_list(list3);

	// list1 = 20->30->33->22->11->를 만든다. 즉, list1과 list3를 합쳐서 list1이 가리키게 한다. 
	list1 = concat(list1, list3);

	//list1을 출력한다. 
	print_list(list1);

	//list1만 사용하여 함수 테스트
	printf("\nis in list : %d\n", is_in_list(list1, 11));
	printf("\nlength : %d\n", get_length(list1));
	printf("\ntotal : %d\n", get_total(list1));
	printf("\nget_entry list[2] : %d\n", get_entry(list1, 2));

	list1 = delete_by_key(list1, 22);
	printf("\ndelete by key : 22\n");
	print_list(list1);

	list1 = insert_pos(list1, 3, 88);
	printf("\ninsert post list[3]에 88추가\n");
	print_list(list1);

	list1 = delete_pos(list1, 2);
	printf("\ndelete pos : 2\n");
	print_list(list1);
}

원형 연결 리스트

• 마지막 노드가 첫 번째 노드를 가리키는 리스트
• 즉, 마지막 노드의 링크 필드가 널(NULL)이 아닌 첫 번째 노드 주소가 되는 리스트
• 장점 : 하나의 노드에서 다른 모든 노드로 접근 가능
• 삭제나 삽입 시 항상 선행 노드를 가리키는 포인터 필요
• 첫번째 노드 = head->link
• 마지막 노드 = head

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

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;
ListNode* insert_first(ListNode* head,element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	if (head == NULL) {
		head = p;
		p->link = head;
	}
	else {
		p->link = head->link;
		head->link = p;
	}
	return head;
}
ListNode* insert(ListNode* head, ListNode*pre, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;

	if (head == NULL) {
		head = p;
		p->link = head;
	}
	else {
		p->link = pre->link;
		pre->link = p;
		if (pre == head)
			head = p;
	}
	return head;
}
ListNode* insert_last(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	if (head == NULL) {
		head = p;
		p->link = head;
	}
	else {
		p->link = head->link;
		head->link = p;
		head = p;
	}
	return head;
}
ListNode* delete_first(ListNode* head) {
	ListNode* removed = NULL;
	if (head == NULL)
		return NULL;
	else if (head->link == head) {
		removed = head;
		free(removed);
		return NULL;
	}
	else {
		removed = head->link;
		head->link = removed->link;
		free(removed);
		return head;
	}
}
ListNode* delete(ListNode* head,ListNode* pre) {
	ListNode* removed = NULL;
	if (head == NULL)
		return NULL;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}
ListNode* delete_last(ListNode* head) {
	if (head == NULL)
		return NULL;
	else if (head->link == head) {
		free(head);
		return NULL;
	}
	else {
		ListNode* p = head;
		ListNode* prev = NULL;
		do {
			prev = p;
			p = p->link;
		} while (p != head);
		prev->link = head->link;
		free(p);
		return prev;
	}
}
ListNode* search(ListNode* head, element x) {
	if (head == NULL)
		return NULL;
	ListNode* p = head;
	do {
		if (p->data == x)
			return p;
		p = p->link;
	} while (p != head);

	return NULL;
}
ListNode* concat(ListNode* head1, ListNode* head2) {
    if (head1 == NULL)
        return head2;
    else if (head2 == NULL)
        return head1;
	else {
		ListNode* p1 = head1->link;
		ListNode* p2 = head2->link;
		head1->link = p2;
		head2->link = p1;

		return head2;
	}
}

ListNode* reverse(ListNode* head) {
	ListNode* p, * q, * r;
	if (head == NULL || head->link == head)
		return head;

	p = head->link;
	q = head;
	while (p != head) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	head = head->link;
	p->link = q;
	return head;
}
int is_in_list(ListNode* head, element value) {
	if (head == NULL)
		return head;
	else {
		ListNode* p = head->link;
		do {
			if (p->data == value)
				return 1;
			p = p->link;
		} while (p != head->link);

		return 0;
	}
}
int get_length(ListNode* head) {
	if (head == NULL)
		return 0;
	else {
		ListNode* p = head->link;
		int i = 0;
		do {
			i++;
			p = p->link;
		} while (p != head->link);

		return i;
	}
}
int get_total(ListNode* head) {
	int total = 0;
	if (head == NULL)
		return 0;
	else {
		ListNode* p = head->link;
		do {
			total += p->data;
			p = p->link;
		} while (p != head->link);

		return total;
	}
}
element get_entry(ListNode* head, int pos) {
	if (pos<0 || pos>get_length(head) || head == NULL)
		return NULL;
	ListNode* p = head->link;
	int i = 0;
	do {
		if (i == pos)
			return p->data;
		p = p->link;
		i++;
	} while (p != head->link);
}
ListNode* delete_by_key(ListNode* head, int key) {
	if (head == NULL)
		return NULL;
	ListNode* p = head->link;
	ListNode* prev = head;

	do {
		if (p->data == key) {
			prev->link = p->link;
			free(p);
			return head;
		}
		prev = p;
		p = p->link;
	} while (p != head->link);
	return head;
}
ListNode* insert_pos(ListNode* head, int pos, element value) {
	ListNode* p, * prev;
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->data = value;
	if (pos<0 || pos>get_length(head))
		return head;
	if (head == NULL) {
		head = newNode;
		newNode->link = head;
	}
	else {
		int i = 0;
		p = head->link;
		prev = head;
		do {
			if (i == pos) {
				prev->link = newNode;
				newNode->link = p;
				return head;
			}
			i++;
			prev = p;
			p = p->link;
		} while (p != head->link);
	}
	return head;
}
ListNode* delete_pos(ListNode* head, int pos) {
	if (pos<0 || pos>get_length(head)||head==NULL)
		return head;
	else {
		int i = 0;
		ListNode* p = head->link;
		ListNode* prev = head;
		do {
			if (i == pos) {
				prev->link = p->link;
				free(p);
				return head;
			}
			i++;
			prev = p;
			p = p->link;
		} while (p != head->link);
	}
	return head;
}
void print_list(ListNode* head) {
	ListNode* p;
	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d-> ", p->data);
		p = p->link;
	} while (p != head->link);
	printf("NULL\n");
}
int main(void) {
	ListNode* list1 = NULL, * list2 = NULL, * list3;
	//list1 = 30->20->10->를 만든다. 이때 10, 20, 30의 순으로 노드를 삽입한다. 
	list1 = insert_first(list1, 10);
	list1 = insert_first(list1, 20);
	list1 = insert_first(list1, 30);
	// list1을 출력 
	printf("list1 = ");
	print_list(list1);

	//list1의 맨 앞 노드를 삭제한다 즉, list1 = 20->30-> 
	list1 = delete_first(list1);
	// list1을 출력 
	print_list(list1);

	//list2 = 11->22->33->44->를 만든다. 이때 11, 22, 33, 44의 순으로 노드를 삽입한다. 
	list2 = insert_first(list2, 11);
	list2 = insert_last(list2, 22);
	list2 = insert_last(list2, 33);
	list2 = insert_last(list2, 44);
	// list2를 출력 
	print_list(list2);

	// list2의 맨 뒤 노드를 삭제한다. 즉, list2 = 11->22->33-> 
	list2 = delete_last(list2);

	// list2를 출력 
	print_list(list2);

	//list2를 역순으로 바꾼 리스트를 list3가 가리키게 한다. list3 = 33->22->11->를 만든다.
	list3 = reverse(list2);

	//list3를 출력한다.
	print_list(list3);

	// list1 = 20->30->33->22->11->를 만든다. 즉, list1과 list3를 합쳐서 list1이 가리키게 한다. 
	list1 = concat(list1, list3);

	//list1을 출력한다. 
	print_list(list1);

	//list1만 사용하여 함수 테스트
	printf("\nis in list : %d\n", is_in_list(list1, 10));
	printf("\nlength : %d\n", get_length(list1));
	printf("\ntotal : %d\n", get_total(list1));
	printf("\nget_entry list[2] : %d\n", get_entry(list1, 2));

	list1 = delete_by_key(list1, 22);
	printf("\ndelete by key : 22\n");
	print_list(list1);

	list1 = insert_pos(list1, 3, 88);
	printf("\ninsert post list[3]에 88추가\n");
	print_list(list1);

	list1 = delete_pos(list1, 2);
	printf("\ndelete pos : 2\n");
	print_list(list1);
}

이중 연결 리스트

• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
• 링크가 양방향이므로 양방향으로 검색 가능
• head node라는 특별한 노드를 추가하는 경우가 많음
  • head node는 데이터를 가지고 있지 않는 특별한 노드를 추가하는 것 
  • head node의 데이터 필드는 아무런 정보도 담고 있지 않음
  • 삽입과 삭제 알고리즘을 간편하게 하기 위하여 존재
• head pointer는 리스트의 첫 번째 노드를 가리키는 포인터
• 구조
  • 데이터 필드
  • 왼쪽 링크 필드
  • 오른쪽 링크 필드

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

typedef int element;
typedef struct DListNode {
	element data;
	struct DListNode* llink;
	struct DListNode* rlink;

}DListNode;

//초기화
void init(DListNode* phead) {
	phead->llink = phead->rlink = phead;
}

//새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
	DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
	newNode->data = data;

	newNode->llink = before;
	newNode->rlink = before->rlink;

	before->rlink->llink = newNode;
	before->rlink = newNode;
}
//노드 removed 삭제
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == NULL)
		return;
	
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}
DListNode* search(DListNode* phead, element data) {
	DListNode* p = phead;
	do {
		if (p->data == data)
			return p;
		p = p->rlink;
	} while (p != phead);

	return NULL;
}
DListNode* dconcat(DListNode* phead1, DListNode* phead2) {
	if (phead1->rlink == phead1) return phead2;
	else if (phead2->rlink == phead2) return phead1;
	else {
		phead2->rlink->llink = phead1->llink;
		phead1->llink->rlink = phead2->rlink;
		phead2->llink->rlink = phead1;
		phead1->llink = phead2->llink;
		phead2->rlink = phead2;
		phead2->llink = phead2;

		return phead1;
	}
}
//노드 출력
void print_dlist(DListNode* phead) {
	for(DListNode* p=phead->rlink;p!=phead;p=p->rlink)
		printf("<-| |%d |-> ", p->data);
	printf("\n");
}
//역순 출력
void print_reverse_dlist(DListNode* phead) {
	for (DListNode* p = phead->llink; p != phead; p = p->llink)
		printf("<-| |%d |-> ", p->data);
	printf("\n");
}
int main(void) {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	DListNode* head2 = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	printf("추가 단계\n");

	//맨 앞에 노드를 삽입
	dinsert(head, 10);
	print_dlist(head);
	dinsert(head, 20);
	print_dlist(head);
	dinsert(head, 30);
	print_dlist(head);

	//맨 뒤에 노드 삽입
	dinsert(head->llink, 99);
	print_dlist(head);

	printf("\n삭제 단계\n");

	//맨 앞 노드 삭제
	ddelete(head, head->rlink);
	print_dlist(head);

	//맨 뒤 노드 삭제
	ddelete(head, head->llink);
	print_dlist(head);

	//역순으로 순회하며 저장된 데이터 값 출력
	printf("\nreverse\n");
	print_reverse_dlist(head);

	//data를 갖는 노드를 찾아서 반환
	if (search(head, 20)) printf("%d 찾음\n",20);
	else printf("%d 없음\n",20);
	if (search(head, 30)) printf("%d 찾음\n", 30);
	else printf("%d 없음\n", 30);

	//두 리스트 연결
	printf("\nconcat\n");
	init(head2);
	dinsert(head2, 70);
	dinsert(head2, 80);
	dinsert(head2, 90);

	head = dconcat(head, head2);
	print_dlist(head);
	free(head);
	free(head2);
	return 0;
}