백준[1406] -에디터 (C++)

오늘은 연결리스트에 대해서 공부했다.

 

연결리스트란?

연결리스트(Linked List)는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

- 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 

연결리스트 예시

 

각 노드의 포인터는 다음 노드의 데이터의 주소를 값으로 가진다.

 

이런 특징들을 가진 연결리스트를 구현하기 위해 구조체로 연결리스트를 구현해보았다.

 

연결리스트 구현

struct Node
{
	char data;
	struct Node* next;
};

void PrintList(Node* head) {
	Node* cursor = new Node();
	if (head == NULL) {
		cout << "The head is NULL \n";
		return;
	}
	else {
		cursor = head->next;
		while (cursor != NULL) {
			cout << cursor->data << " ";
			cursor = cursor->next;
		}
	}
	
}

Node* insertNode(Node* prev_node, int key) {
	if (prev_node == NULL) {
		return prev_node;
	}
	Node* new_node = new Node();
	new_node->data = key;
	new_node->next = prev_node->next;
	prev_node->next = new_node;
	return prev_node;
}

Node* deleteNode(Node* head, int key) {
	if (head == NULL) {
		return head;
	}
	Node* cursor = new Node();
	while (cursor->next->data != key) {
		cursor = cursor->next;
	}
	Node* temp = new Node();
	temp = cursor->next;
	cursor->next = temp->next;
	delete temp;
	return head;
}

한 노드에 데이터와 다음 노드 데이터의 주소를 가진 포인터가 있기 때문에, 위 코드처럼 Node 구조체를 만들었다.

 

연결리스트(Linked List)에서의 노드 추가

 

 

 

그리고 연결리스트에서 노드를 추가할 때는 위 그림처럼 전 노드의 포인터가 새로운 노드의 데이터 주소를 가지게 하고, 새로운 노드가 전 노드가 가지던 데이터 주소를 가지게 하는 방식으로 리스트에 추가한다.

 

 

연결리스트(Linked List)에서의 노드 삭제

 

 

마찬가지로 연결리스트에서의 노드 삭제는 이전 데이터의 포인터가 삭제할 데이터의 다음 노드의 데이터 주소를 값으로 가지게 한 후 삭제할 노드를 제거하는 방식으로 이루어진다.

 

 

이게 기본적인 연결리스트의 개념인데, C++에서는 <list>라이브러리로 연결리스트가 구현되어 있기 때문에, 

이번 문제에서는 라이브러리를 사용해서 풀어보았다.

 

 

1406번 문제 풀이 (C++)

#include<iostream>
#include<list>
#include<string>
using namespace std;

int main() {
	string word;
	list<char> list;
	char command, ch;
	int n;
	auto cursor = list.end();
	cin >> word;
	for (int i = 0; i < word.size(); i++) {
		list.push_back(word[i]);
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> command;
		if (command == 'L') {
			if(cursor != list.begin()) cursor--;
		}
		else if (command == 'D') {
			if (cursor != list.end()) cursor++;
		}
		else if (command == 'B') {
			if (cursor != list.begin()) {
				auto temp = cursor;
				temp--;
				list.erase(temp);
			}
		}
		else if (command == 'P') {
			cin >> ch;
			list.insert(cursor, ch);
		}
		
	}
	for (cursor = list.begin(); cursor != list.end(); cursor++) {
		cout << *cursor;
	}
	return 0;
}

위 문제에서의 설명처럼 커서의 개념을 사용했는데, list에서 각각 노드의 포인터를 증가시키거나 감소시키며, 노드 사이를 이동할 수 있게 구현하였다. 그리고 연결리스트는 vector나 배열과는 다르게 인덱스의 개념이 없기 때문에, 출력을 할 때, 

 

for (cursor = list.begin(); cursor != list.end(); cursor++) {
		cout << *cursor;
	}

이런 방식으로 포인터를 증가시키면서 앞에서부터 출력을 할 수 있었다. 앞 뒤를 이동하며 편집을 할 때에는 연결리스트가 유용할 것 같아서 앞으로의 문제 풀이에서도 연결리스트를 종종 사용할 것 같다.