04 연결리스트(1)

#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) {
	//insert(1,30)
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	
	int next = nxt[addr];
	if(next !=-1)
		pre[next] = unused;
	nxt[addr] = unused;
	unused++;



}

void erase(int addr) {
	int pre_addr = pre[addr];
	int nxt_addr = nxt[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();
}

야매리스트로 insert() 메소드, erase() 메소드 구현

 

출처:GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료