백준 알고리즘 #4.2 - 원형 연결리스트, 이중 연결리스트

저번 포스트에서는 단순 연결리스트를 알아봤습니다. 이번에는 원형 연결리스트의 구현과 이중 연결리스트의 구현에 대해 포스팅하겠습니다.

 

 

 

 

🏳️ 원형 연결리스트의 구현

 

-  원형 연결리스트는 단순 연결리스트와 다르게, 마지막 요소 -> link가 NULL이 아닌 head를 가리키게 하는 형식입니다. 이때 head포인터는 마지막 노드를 가리키게 됩니다.

 

 

 

 

 

head 포인터를 만들어줍니다. (연결리스트를 순회하기 위해서 필요한 포인터, 여기서는 마지막 원소를 head로 가지게 해야합니다.)

 

이때 head 포인터는 아무것도 가리키지 않는 상태로 생성합니다. (NULL을 가리키게 함.)

 

 

 

 

Case #1 ) 원소를 동적 할당하고 , 만약 첫 원소라면 head포인터를 연결 시켜준후,

head->link = head형식으로 만들어줍니다.(자신으로 순환하게끔) 

 

 

1 - 노드를 동적 할당으로 생성합니다.

2 - 이때, 리스트 안에 원소가 없기때문에 생성된 노드가 head가 되게 됩니다.

3 - 또한, 리스트 안에 원소가 없기 때문에 이 노드의 link 값은 자기자신(head)를 가리킵니다.

4 - head 값을 반환해 줍시다.

 

 

 

 

 

Case #1 - 1 ) 원소를 첫번째에 삽입 하고 싶으면, 노드를 생성한 후 head포인터의 link를 변경시켜줍니다.

 

 

* 만약 head가 NULL을 가리킨다면 (리스트에 원소가 존재하지 않을때) Case#1 와 같이 실행 해줍니다.*

 

1 - 노드를 동적 할당으로 생성합니다.

2 - 생성한 노드의 link를 head에 연결합니다.

3 - head->link값을 생성한 노드로 변경해 줍니다.

4 - head 값을 반환해 줍시다.

 

 

 

 

 

 

 

Case #1 - 2 ) 원소를 마지막에 삽입하고 싶으면, 노드를 생성하고 head포인터의 link를 변경시켜준 다음, head 포인터를 변경합니다.

 

 

 

 

 

 

 

 

* 만약 head가 NULL을 가리킨다면 (리스트에 원소가 존재하지 않을때) Case#1 와 같이 실행 해줍니다.*

 

1 - 노드를 동적 할당으로 생성합니다.

2 - 생성한 노드의 link를 head->link에 연결합니다.

3 - head->link값을 생성한 노드로 변경해 줍니다.

4 - head 값을 생성한 노드의 값으로 변경시켜줍니다.(head는 맨 뒤의 원소를 가리키게 만듬)

5 - 변경된 head 값을 반환해 줍시다.

 

 

이를 코드로 나타내면 다음과 같습니다.

 

 

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

typedef struct Node
{
	char data;
	struct Node* link;
}Node;


Node* insert_first(Node* head, char card)
{
	Node* new = (Node*)malloc(sizeof(Node));
	new->data = card;
	if (head == NULL)
	{
		head = new;
		head->link = head;
	}
	else
	{
		new->link = head->link;
		head->link = new;
	}
	return head;
}

Node* insert_last(Node* head,char card)
{
	Node* new = (Node*)malloc(sizeof(Node));
	new->data = card;
	if (head == NULL)
	{
		head = new;
		head->link = head;
	}
	else
	{
		new->link = head->link;
		head->link = new;
		head = new;
	}
	return head;
}

int main(void)
{
	Node* head = NULL;
	head = insert_first(head, 'A');
	head = insert_first(head, 'B');
	head = insert_last(head, 'C');
	Node* p = head->link;
	do { // head는 마지막을 가리키기 때문에, head->link 부터 순회하기 시작합니다.
		printf("%c->", p->data);
		p = p->link;
	} while (p != head->link);
}

 

 

 

 

 

 

 

🏳️ ( 원형 ) 이중 연결리스트의 구현

-  단순 연결리스트에서는 link값을 통해서 한방향으로만 움직일 수 있었지만, 이중 연결리스트에서는 양방향으로 움직일 수 있는 포인터를 선언해서 좀 더 자유롭게 움직이게 할 수 있습니다. (선행 노드 찾기 등) 저희는 위 정보를 바탕으로 원형 이중 연결리스트를 구현하려고합니다.

 

 

 

head 노드를 만들어줍니다. 이때, head는 '더미 노드' 입니다.

 

head 노드를 생성한후, 앞서 봤던 원형 연결리스트 처럼 left 포인터와 right 포인터를 자신(head)에 연결을 시켜줍니다.

 

head를 더미로 생성한 이유는, 연산의 편의성과 일관성을 위함입니다.

 

1 - 순회를 더욱 간편하게 할 수 있습니다.(head 노드는 연결리스트의 시작과 끝을 나타냄)

2 - 빈 연결 리스트를 표현하기 쉽습니다. (head->right = head | head->left = head 이면 빈 연결리스트)

3 - 리스트의 첫번째 요소를 삭제하거나 삽입할 때 예상치 못한 상황을 피할 수 있습니다.

(강제는 아닙니다. 그러나 더미 노드를 사용하는 편이 더욱이 편리할것입니다.)

 

 

Case #1 ) 원소를 삽입 하고 싶다면 새 노드를 만든 후, left와 right 포인터를 적절하게 변경해주면 됩니다.

 

 

 

 

 

1 - 노드를 동적 할당으로 생성합니다.

2 - 생성 노드의 left을 직전 노드에 연결시켜 줍니다.

3 - 생성 노드의 right을 직전 노드의 right에 연결 시켜줍니다.

 

* 직전 노드의 right에 연결 하지 않으면 중간 삽입과 같은 케이스 때 문제가 생길 수 있습니다. *

 

ex) A 와 B 사이에 'C'를 추가하려고 할 때, C의 left는 A이고, C의 right는 B여야 하기 때문에 직전 노드의 right 값으로 받아야함.

 

 

 

 

 

 

 

 

4 - 직전 노드의 right 값(head->right는 head)의 left 값(head->left)을 생성된 노드에 연결해 줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

5 - 직전 노드의 right 값을 생성된 노드에 연결해 줍니다.

 

 

 

 

 

 

 

 

Case #2 ) 원소를 삭제 하고 싶다면 left와 right 포인터를 적절하게 변경해준후,  동적 할당 해제를 하면 됩니다. 이때, 삭제할 노드 ( removed ) 를 지정하여 함수에 인자로 넘겨야합니다.

 

 

 

 

 

 

* 만약 삭제할 노드가 head 노드를 가리킨다면 작업을 수행하지 않습니다. *

 

1 - 삭제할 노드를 지정합니다.

 

 

 

 

 

 

 

 

 

 

2 - 삭제할 노드의 left(removed->left는 A)의 right(A->right)를 삭제할 노드의 right(removed->right는 C)의 값으로 변경합니다.

 

 

 

 

 

 

 

3 - 삭제할 노드의 right(removed->right는 C)의 left(C->left)를 삭제할 노드의 left(removed->left는 A)의 값으로 변경합니다.

 

 

 

 

 

 

 

4 - 삭제할 노드를 동적 할당 해제 시켜줍니다.

 

 

 

 

 

 

 

이를 코드로 나타내면 다음과 같습니다.

 

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

typedef struct Node
{
	char data;
	struct Node* left;
	struct Node* right;
}Node;

void init(Node* head)
{
	head->left = head->right = head;
	// 원형 이중 연결리스트를 만들기 위해 head의 left, right가 자기를 향하게 합니다.
}


Node* insert(Node* prev, char card)
{
	Node* new = (Node*)malloc(sizeof(Node));
	new->data = card;
	new->left = prev;
	new->right = prev->right;
	prev->right->left = new;
	prev->right = new;
	return new;
}

void delete(Node* head, Node* removed)
{
	if (removed == head)
	{
		return;
	}
	removed->left->right = removed->right;
	removed->right->left = removed->left;
	free(removed);
}

int main(void)
{
	Node* head = (Node*)malloc(sizeof(Node)); // head(더미 노드)를 생성합니다.
	init(head); // head를 초기화 합니다.
	Node* p = NULL; // 노드의 정보를 담을 노드입니다.
	p = insert(head, 'A');
	p = insert(p, 'B');
	p = insert(p, 'C');
	for (Node* i = head->right; i != head; i = i->right)
	{
		// 노드의 오른쪽 부터 순회하여, 특정 데이터를 갖는 노드를 찾습니다.
		if (i->data == 'B')
		{
			p = i;
			break;
		}
	}
	delete(head, p);
	for (Node* i = head->right; i != head; i = i->right)
	{
		// 노드의 오른쪽 부터 순회하여, head(더미 노드)전까지 순회 합니다.
		if (i->right == head)
		{
			printf("%c", i->data);
		}
		else
		{
			printf("%c->", i->data);
		}
	}
}