[0x04] 연결 리스트

k번째 원소를 확인/변경하기 위해 O(k) 필요. 배열은 O(1)

임의의 위치에 원소를 추가/임의의 위치의 원소 제거는 O(1). 배열은 O(N)

메모리상에 연속되어 있지 않기때문에 cache hit rate가 낮지만 할당이 다소 쉬움

오버헤드는 O(N)

 

단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 사용

STL에 리스트가 있고 이중 연결 리스트로 구현되어있음

 

면접에서 배열과 연결리스트를 비교하는걸 구술 시험으로 내기도 함

 

코딩 테스트에서 STL을 사용하지 못할 때 쓸 수 있는 야매 연결 리스트

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void insert(int addr, int num) {
	dat[unused] = num;
	
	pre[unused] = addr;
	nxt[unused] = nxt[addr];

	if (nxt[addr] != -1) pre[nxt[addr]] = unused;
	nxt[addr] = unused;
	
	unused++;
}

void erase(int addr) {
	nxt[pre[addr]] = nxt[addr];
	if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse() {
	int cur = nxt[0];
	while (cur != -1) {
		cout << dat[cur] << ' ';
		cur = nxt[cur];
	}
	cout << "\n\n";
}

void insert_test() {
	cout << "****** insert_test *****\n";
	insert(0, 10); // 10(address=1)
	traverse();
	insert(0, 30); // 30(address=2) 10
	traverse();
	insert(2, 40); // 30 40(address=3) 10
	traverse();
	insert(1, 20); // 30 40 10 20(address=4)
	traverse();
	insert(4, 70); // 30 40 10 20 70(address=5)
	traverse();
}

void erase_test() {
	cout << "****** erase_test *****\n";
	erase(1); // 30 40 20 70
	traverse();
	erase(2); // 40 20 70
	traverse();
	erase(4); // 40 70
	traverse();
	erase(5); // 40
	traverse();
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);
	insert_test();
	erase_test();


	return 0;
}

 

연습문제

 

1406: 에디터

#include <iostream>
#include <string>
#include <list>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	list<char>	editor;
	string		str;
	int			m;

	cin >> str;

	for (auto s : str)
	{
		editor.push_back(s);
	}

	cin >> m;

	auto cursor = editor.end();

	while (m--)
	{
		char command;

		cin >> command;

		switch (command)
		{
		case 'L':
			if (cursor != editor.begin())
			{
				cursor--;
			}
			break;
		case 'D':
			if (cursor != editor.end())
			{
				cursor++;
			}
			break;
		case 'B':
			if (cursor != editor.begin())
			{
				cursor = editor.erase(--cursor);
			}
			break;
		default:
			char s;
			cin >> s;
			editor.insert(cursor, s);
			break;
		}
	}

	for (auto s : editor)
	{
		cout << s;
	}

	return 0;
}

 

리스트(그외 반복자가 있는 컨테이너도 마찬가지일듯)의 erase 사용시 삭제된 원소 다음 반복자를 반환해주기 때문에 갱신을 시켜주어야 한다.

그렇지 않고 계속 사용하다간 Segmentation fault를 발생시킨다

 

5397: 키로거

#include <iostream>
#include <string>
#include <list>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int	tc;

	cin >> tc;

	while (tc--)
	{
		list<char>	editor;
		auto		cursor = editor.begin();

		string		str;

		cin >> str;

		for (auto s : str)
		{
			switch (s)
			{
			case '<':
				if (cursor != editor.begin())
				{
					cursor--;
				}
				break;
			case '>':
				if (cursor != editor.end())
				{
					cursor++;
				}
				break;
			case '-':
				if (cursor != editor.begin())
				{
					cursor = editor.erase(--cursor);
				}
				break;
			default:
				editor.insert(cursor, s);
				break;
			}
		}

		for (auto s : editor)
		{
			cout << s;
		}
		cout << '\n';
	}

	return 0;
}

 

1158: 요세푸스 문제

#include <iostream>
#include <string>
#include <list>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	list<int> josephus;

	int	n, k;
	int	idx = 1;

	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
	{
		josephus.push_back(i);
	}

	auto iter = josephus.begin();

	cout << "<";

	while (true)
	{
		if (iter == josephus.end())
		{
			iter = josephus.begin();
		}

		if (idx % k == 0)
		{
			cout << *iter;
			iter = josephus.erase(iter); // 삭제된 원소 다음 반복자 반환

			if (josephus.empty())
			{
				break;
			}

			cout << ", ";
			idx++; // 삭제로 인해 자동으로 한칸이 밀렸으므로 인덱스도 맞춰줌

			continue;
		}
		
		iter++;
		idx++;
	}

	cout << ">";

	return 0;
}