728x90
반응형
연결리스트
성질
- k 번째 원소 확인/변경 위해 O(k) 필요
- 임의의 위치에 원소 추가, 제거가 O(1) (추가/제거하는 위치를 알고있는 경우)
- Cache rate hit은 낮지만 할당이 좋다.
→ 임의의 위치에 원소 추가하거나 제거하는 연산이 많을경우 연결리스트 사용 좋다.
연결리스트 종류: 단일 연결리스트/이중연결 리스트/환형 연결리스트
배열 vs 연결리스트
연결리스트 구현
#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(void) {
fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);
insert_test();
erase_test();
}
STL List
문제 풀이 현황
연습 문제 ✔ | 1406 | 에디터 | 정답 코드 |
기본 문제 ✔ | 5397 | 키로거 | 정답 코드 |
기본 문제 | 1158 | 요세푸스 문제 | 정답 코드, 별해 1, 별해 2 |
728x90
반응형
'알고리즘 > 공부' 카테고리의 다른 글
[바킹독 알고리즘] 0x07강:Deque (1) | 2023.01.06 |
---|---|
[바킹독 알고리즘] 0x06강:Queue (0) | 2023.01.04 |
[바킹독 알고리즘] 0x05강:Stack (1) | 2022.12.27 |
[바킹독 알고리즘] 0x03강:Array (0) | 2022.12.23 |
[바킹독 알고리즘] 0x02강:STL (0) | 2022.12.22 |