연결리스트 배열로 구현

Published: March 28, 2019 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

• 문제를 보고 해결 방법을 떠올리지 못하였고, 문제 분류를 보고도 떠올리지 못하였다.ㅠㅠ
• 연결리스트 배열로 구현
• 삭제 할 때, 삭제할 공간에 젤 뒤 원소와 swap 하여 공간 복잡도를 줄였다.

#include <stdio.h>
#include <algorithm>
#include <list>
#include "Windows.h"
using namespace std;

struct Node {
	int prev;
	int next;
	int val;
};

const int NODE_SIZE = 30000;

const int PUSH_BACK = 0;
const int PUSH_FRONT = 1;
const int INSERT = 2;
const int POP_BACK = 3;
const int POP_FRONT = 4;
const int ERASE = 5;

int test_cmd[NODE_SIZE][3];

struct MY_LIST {
	int pos;
	Node node[NODE_SIZE + 2];
	int HEAD = NODE_SIZE;
	int TAIL = NODE_SIZE + 1;

	MY_LIST() {
		pos = 0;
		node[HEAD].next = TAIL;
		node[TAIL].prev = HEAD;
	}

	void push_back(int data) {
		int prev = node[TAIL].prev;
		int next = node[prev].next;

		node[pos].val = data;
		node[pos].prev = prev;
		node[prev].next = pos;
		node[pos].next = next;
		node[next].prev = pos;
		++pos;
	}
	void push_front(int data) {
		int next = node[HEAD].next;
		int prev = node[next].prev;

		node[pos].val = data;
		node[pos].prev = prev;
		node[prev].next = pos;
		node[pos].next = next;
		node[next].prev = pos;
		++pos;
	}
	void insert(int n, int data) { // n위치에 data 삽입
		int prev = HEAD;
		for (int i = 0; i < n; i++, prev = node[prev].next);
		int next = node[prev].next;
		node[pos].val = data;
		node[pos].prev = prev;
		node[prev].next = pos;
		node[pos].next = next;
		node[next].prev = pos;
		++pos;
	}
	void  pop_back() {
		int target = node[TAIL].prev;

		int prev = node[target].prev;
		int next = node[target].next;

		node[prev].next = next;
		node[next].prev = prev;

		--pos;
			node[target].val = node[pos].val;
			node[target].next = node[pos].next;
			node[target].prev = node[pos].prev;
		if (target != pos) {
			node[node[pos].prev].next = target;
			node[node[pos].next].prev = target;
		}
	}
	void pop_front() {
		int target = node[HEAD].next;

		int prev = node[target].prev;
		int next = node[target].next;

		node[prev].next = next;
		node[next].prev = prev;

		--pos;

		node[target].val = node[pos].val;
		node[target].next = node[pos].next;
		node[target].prev = node[pos].prev;
		if (target != pos) {
			node[node[pos].prev].next = target;
			node[node[pos].next].prev = target;
		}
	}
	void erase(int p) { // p위츼 데이터 삭제
		int prev = HEAD;
		for (int i = 0; i < p; i++, prev = node[prev].next);
		int target = node[prev].next;
		int next = node[target].next;
		node[prev].next = next;
		node[next].prev = prev;
		--pos;
			node[target].val = node[pos].val;
			node[target].next = node[pos].next;
			node[target].prev = node[pos].prev;
			if (target != pos) {
				node[node[pos].prev].next = target;
				node[node[pos].next].prev = target;
			}
	}
};
MY_LIST my_list;
list<int> stl_list;

int main() {
	int cur_size = 0;

	for (int i = 0; i < NODE_SIZE; ++i) {
		//test_cmd[i][0] = 0;
		if (i < NODE_SIZE / 3) {
			test_cmd[i][0] = rand() % 2;
		}
		else {
			test_cmd[i][0] = rand() % 6;
		}

		switch (test_cmd[i][0]) {
		case PUSH_BACK: {
			test_cmd[i][1] = rand();
			++cur_size;
			my_list.push_back(test_cmd[i][1]);
			stl_list.push_back(test_cmd[i][1]);
			break;
		}
		case PUSH_FRONT: {
			test_cmd[i][1] = rand();
			++cur_size;
			my_list.push_front(test_cmd[i][1]);
			stl_list.push_front(test_cmd[i][1]);
			break;
		}
		case INSERT: {
			test_cmd[i][1] = rand() % cur_size;
			test_cmd[i][2] = rand();
			my_list.insert(test_cmd[i][1], test_cmd[i][2]);
			++cur_size;
			list<int>::iterator it = stl_list.begin();
			for (int k = 0; k < test_cmd[i][1]; ++k) {
				++it;
			}
			stl_list.insert(it, test_cmd[i][2]);
			break;
		}
		case POP_BACK: {
			--cur_size;
			my_list.pop_back();
			stl_list.pop_back();
			break;
		}
		case POP_FRONT: {
			--cur_size;
			my_list.pop_front();
			stl_list.pop_front();
			break;
		}
		case ERASE: {
			test_cmd[i][1] = rand() % cur_size;
			--cur_size;
			my_list.erase(test_cmd[i][1]);
			list<int>::iterator it = stl_list.begin();
			for (int k = 0; k < test_cmd[i][1]; ++k) {
				++it;
			}
			stl_list.erase(it);
			break;
		}
		}
	}

	int my_list_begin = GetTickCount();
	//for (int i = 0; i < NODE_SIZE; ++i) {
	//	switch (test_cmd[i][0]) {
	//	case PUSH_BACK: {
	//		my_list.push_back(test_cmd[i][1]);
	//		break;
	//	}
	//	case PUSH_FRONT: {
	//		my_list.push_front(test_cmd[i][1]);
	//		break;
	//	}
	//	case INSERT: {
	//		my_list.insert(test_cmd[i][1], test_cmd[i][2]);
	//		break;
	//	}
	//	case POP_BACK: {
	//		my_list.pop_back();
	//		break;
	//	}
	//	case POP_FRONT: {
	//		my_list.pop_front();
	//		break;
	//	}
	//	case ERASE: {
	//		my_list.erase(test_cmd[i][1]);
	//		break;
	//	}
	//	}
	//}
	int my_list_end = GetTickCount();

	int stl_list_begin = GetTickCount();
	/*for (int i = 0; i < NODE_SIZE; ++i) {
		switch (test_cmd[i][0]) {
		case PUSH_BACK: {
			stl_list.push_back(test_cmd[i][1]);
			break;
		}
		case PUSH_FRONT: {
			stl_list.push_front(test_cmd[i][1]);
			break;
		}
		case INSERT: {
			list<int>::iterator it = stl_list.begin();
			for (int k = 0; k < test_cmd[i][1]; ++k) {
				++it;
			}
			stl_list.insert(it, test_cmd[i][2]);
			break;
		}
		case POP_BACK: {
			stl_list.pop_back();
			break;
		}
		case POP_FRONT: {
			stl_list.pop_front();
			break;
		}
		case ERASE: {
			list<int>::iterator it = stl_list.begin();
			for (int k = 0; k < test_cmd[i][1]; ++k) {
				++it;
			}
			stl_list.erase(it);
			break;
		}
		}
	}
*/
	int stl_list_end = GetTickCount();

	printf("my list %d\n", (my_list_end - my_list_begin));
	printf("stl list %d\n", (stl_list_end - stl_list_begin));

	list<int>::iterator it = stl_list.begin();
	int cur = my_list.node[my_list.HEAD].next;
	while (it != stl_list.end()) {
		if (*it != my_list.node[cur].val) {
			printf("error!");
		}
		++it;
		cur = my_list.node[cur].next;
	}

	return 0;
}