list를 사용하지 않고 연결리스트 구현해보기
#include <iostream>
using namespace std;
// addr : 해당 연결리스트의 주솟값
// num : 데이터
// 모든 원소가 비어있다는 뜻(-1)
// -1 13 65 21 17
// 0 2 1 4 5
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;
//65 다음 30을 넣는다고 가정, insert(1,30)
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]; // dummy data (-1) , 예외처리를 막기 위함
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() {
fill(pre, pre + MX, -1);
fill(nxt, nxt + MX, -1);
insert_test();
erase_test();
}