문과생이 이해한 단일 연결 리스트(기타 연산- 합병, 역순, 출력/순회, 탐색)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

#전체 코드

#include<stdio.h>
#include<stdbool.h>

typedef struct {
	int data;
	struct node* link;
}node;

node* insert_first(node* head, int x) {
	node* p = (node*)malloc(sizeof(node));
	p->data = x;
	p->link = head;      //head는 노드 생성을 안했으니까 head->link 연산이 안 됨
	head= p;
	return head;
}

node* insert(node* head, node* pre, int s) {
	node* p = (node*)malloc(sizeof(node));
	p->data = s;
	p->link = pre->link;
	pre->link = p;
	return head;
}

void print_node(node* head) {
	for (node* p = head; p != NULL; p = p->link)
		printf("%d -> ", p->data);
	printf("NULL \n");
}

node* delete_first(node* head) {
	node* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;
	return head;
}

node* delete(node* head, node*pre) {
	node* removed;
	removed = pre->link;
	pre->link = removed->link;
	return head;
}

bool search_node(node* head, int x) {
	for (node* p = head; p != NULL; p = p->link)
		if (p->data == x) return true;
	return false;
}

node* concat(node* head1, node* head2) {
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;
	else {
		node* p = head1;
		while (p->link != NULL)
			p = p->link;
		p->link = head2;
		return head1;
	}
}

node* reverse(node* head3) {
	node* p, *q, *r;
	p = head3;
	q = NULL;
	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}

int main() {
	node* head = NULL;
	
	//데이터 삽입 및 출력
	for (int i = 0; i < 5; i++) {
		head = insert_first(head,i);  //반환된 head 포인터를 저장. 아니면 null값만 출력됨
		print_node(head);
	}

	//삭제 연산
	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_node(head);
	}

	printf("\n");

	//탐색 연산
	if (search_node(head, 10)) 
		printf("탐색 성공!");
	else 
		printf("탐색 실패");

	printf("\n");

	//두 개의 리스트 합산
	node* head1 = NULL;
	node* head2 = NULL;

	head1 = insert_first(head1, 10);
	head1 = insert_first(head1, 20);
	head1 = insert_first(head1, 30);

	head2 = insert_first(head2, 40);
	head2 = insert_first(head2, 50);

	concat(head1, head2);
	print_node(head1);

	//역순 출력
	node* head3 = NULL;
	node* head4 = NULL;

	head3 = insert_first(head3, 10);
	head3 = insert_first(head3, 20);
	head3 = insert_first(head3, 30);
	print_node(head3);

	head4 = reverse(head3);
	print_node(head4);

	return 0;
}

 

 

#연결 리스트 출력 

 

처음 배울 때는 while문을 썼는데 for문으로 쓰면 코드 길이가 이렇게 압축된다. 

 

 짠. 이렇게 p에 p가 가리키는 링크를 저장해서 20', 30', 40' 50'를 순회하다가 p가 가리키는 노드의 링크가 NULL 즉, 연결리스트의 끝에 다다르면 함수를 종료한다. 삽입, 삭제 연산을 한 코드를 출력한 값은 다음과 같다. 

 

 

 

---

 

 

 

 

#노드 탐색 

 

 head의 값과 찾을 값을 인자값을 보낸 뒤에 순회 연산과 비슷하게 똑같은 값이 있는지 찾는다. 참고로 c언어에서 boolean 자료형을 사용하려면 처음에,

 

#include<stdbool.h>

 

를 추가해줘야 한다. 

 

 

 

---

 

 

#2개의 노드를 합병

 짠. 메인문을 실행하면 메모리는 이런 구조로 저장되어 있을거다. 54줄 if문은 혹시 head1이나 head2가 NULL이면 그 연결리스트는 비어있다는 의미이므로 둘 중에 하나만 반환해도 된다는 거다. 

 

1. 그리고 여기서는 while문을 사용했다! p->link=NULL일 때까지 반복문을 돈다. 

 

 

 2. p->link에 head2를 넣으면 간단하게 두 연결리스트가 이어진다.

 

 concat 함수를 종료하면 이런 형태다. (와 그리고 main문에 head1,2라고 썻어야 했는데 head랑 i로 썻다. 와.)

 

 

---

 

 

 

#역순

p:  선행노드

q:  방향을 바꿀 노드를 가리키는 포인터

r:  q가 가리키는 노드의 링크에 들어갈 주소값

 

 

1. 

 

 

2. 

 

 

 

3.  

 

 

4.