Double Linked List, 더블 링크드 리스트, 백준 5397

백준 5397


https://www.acmicpc.net/problem/5397

이 문제는 이번에 설명할 더블 링크드 리스트를 안쓰더라도 풀 수 있습니다.

예를 들어 char 배열로 풀 수 있습니다.

char str[1000000] 배열에 문자를 하나하나 집어넣으면서

’<’가 나오면 str의 idx를 -1해주고, ‘>’이 나오면 idx를 +1 해주면 됩니다.

문제는 ‘-‘가 나와 삭제할 때입니다. 삭제를 할 때, 삭제하는 위치 뒤에 있는 문자열을

모두 한칸씩 땡겨야 합니다. 삭제가 빈번하게 이루어지면 당연히 프로그램 속도도 느려질 것입니다.

이를 해결할 수 있는 방법이 더블 링크드 리스트 자료구조입니다.



더블 링크드 리스트(Doubly linked list)


더블 링크드 리스트는 여기에서 설명한

싱글 링크드 리스트와 유사합니다.

다만 싱글 링크드 리스트에서 노드에 다음 노드의 주소값만 저장했다면

더블 링크드 리스트는 이전 노드의 주소값까지 저장한다는 것입니다.


다음 그림이 더블 링크드 리스트의 형태 입니다.

doubly_linked_list1

첫 노드인 teemo 노드는 연결된 이전 노드가 없으므로 prev가 NULL입니다.

마지막 노드인 gnar 노드는 연결된 다음 노드가 없으므로 next가 NULL입니다.


그렇다면 새 노드를 특정 위치에 추가하려면?

doubly_linked_list_push

결론적으론 새 노드를 추가함으로써 영향을 받는 노드들의 prev와 next를 바꿔주면 됩니다.

doubly_linked_list_push2


그렇다면 특정 노드를 살제할 때는?

doubly_linked_list_del1

이것도 마찬가지로 기존 노드를 삭제함으로써 영향을 받는 노드들의 prev와 next를 바꿔주면 됩니다.

doubly_linked_list_del2

그림이 너무 복잡하니 없어지는 연결링크를 다 지우고 보면 다음과 같습니다.

doubly_linked_list_del3

teemo 노드와 gnar 노드가 서로 연결되어 있고, jax 노드는 나가리가 된 걸 볼 수 있습니다.

알고리즘 문제를 풀 때는 정답만 나오면 되므로, jax 노드를 그냥 냅두고 무시하면 되지만,

실제로 서비스 되고 있는 어떤 앱에서 이 더블 링크드 리스트를 쓴다면 jax 노드는 삭제해야 메모리를 절약할 수 있을 것입니다.



다시 문제로 돌아와서…


다음은 제 코드입니다.

#include <stdio.h>

const int LM = 1e6 + 7;
char str[LM];
int cnt;

struct Node {
	char c;
	Node *prev, *next;

	Node* myAlloc(char ch, Node* p, Node* n) {
		c = ch;
		if (p) p->next = this;
		prev = p;
		if (n) n->prev = this;
		next = n;
		return this;
	}
}buf[LM], *head, *cur;

void left() {
	if (cur != head) cur = cur->prev;
}

void right() {
	if (cur->next) cur = cur->next;
}

void del() {
	if (cur == head) return;
	if (cur->next) cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	cur = cur->prev;
}

void init() {
	cnt = 0;
	cur = head = buf[++cnt].myAlloc(0, NULL, NULL);
}

int main() {
	//freopen("input.txt", "r", stdin);
	int tc;
	scanf("%d", &tc);

	for (int t = 0; t < tc; ++t) {
		init();
		scanf("%s", str);
		char* c = str;
		while (*c) {
			if (*c == '<') left();
			else if (*c == '>') right();
			else if (*c == '-') del();
			else cur = buf[++cnt].myAlloc(*c, cur, cur->next);
			++c;
		}

		Node *tmp = head->next;
		for (; tmp; tmp = tmp->next) printf("%c", tmp->c);
		printf("\n");
	}

	return 0;
}

Node 구조체 정의 부분을 보면 Node 포인터 변수로 prev와 next를 선언했습니다.


init()를 보면 Node 구조체의 포인터 변수인 head와 cur를 초기화하고 있습니다.

head는 제가 임의로 dummy tail로서 넣은 것입니다. cur은 현재 커서의 위치를 의미하고,

커서가 맨 앞에 있으면 cur는 head를 가리킬 것입니다.


각 테스트 케이스의 진행은 main()함수의 for문에서 이루어집니다.

문자열을 읽은 후, 문자열의 문자를 하나하나 살펴봅니다.

left()를 살펴보면, 커서가 맨 앞이 아니면, 즉 cur이 head가 아니면 cur의 위치를 prev로 변경합니다.

right()도 비슷하게 진행하였습니다.


del()을 할 때는 먼저 커서가 맨 앞에 있으면 할 게 없으므로 바로 return 입니다.

그리고 연결된 다음 노드가 있다면, 다음노드의 prev를 현재 노드의 prev에 연결하고,

이전 노드의 next노드를 현재 노드의 next노드로 연결합니다.

그리고 cur을 이전 노드로 설정해줍니다.


사실 이렇게 까지만 하면 위에서 jax를 삭제할 때와 조금 다릅니다.

jax를 예로 들면 jax의 prev와 next는 건드리지 않았기 때문입니다.

하지만 문제를 푸는데는 큰 상관은 없습니다.

이미 cur은 jax의 이전 노드인 teemo를 가리키고 있고, teemo의 next는 gnar이기 때문에

더이상 jax 노드로 갈 수가 없기 때문입니다.

하지만 문제풀이가 아닌 현업에서 더블 링크드 리스트를 개발할 때는

메모리 낭비를 막기위해 위에서 설명할 때처럼 jax의 prev, next도 NULL로 설정해주고

jax 노드 자체도 삭제를 해야합니다.