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;
}
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x07] 덱(Deque) (0) | 2022.07.25 |
|---|---|
| [0x06] 큐 (0) | 2022.07.25 |
| [0x05] 스택 (0) | 2022.07.25 |
| [0x03] 배열 (0) | 2022.07.25 |
| [0x02] 기초 코드 작성 요령 (0) | 2022.07.25 |