연결리스트 구현

안성현·2023년 3월 17일
0

알고리즘 공부

목록 보기
1/1

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();
}
profile
코린이

0개의 댓글