[Algorithms] 오름차순 데이터 저장 기반 double linked list

 

head / tail을 사용해서 양쪽 끝단을 시용한다. → Double Linked List의 특징

단, head의 경우 next의 값부터 사용하는 것을 전제로 함.

이유는 head->next를 첫번째 값으로 사용했을 경우, null 상태일때 대처를 손쉽게 할 수 있기 때문임.

 

const int MAX_N = 30001;
struct node {
	int val;
	node* next;
	node* prev;
	node* alloc(int _val, node* _next, node* _prev) {
		val = _val;
		next = _next;
		prev = _prev;
		return this;
	}
}buf[MAX_N], *head, *tail;
int bCnt;

void init() {
	for (int i = 0; i < bCnt; i++) {
		buf[i].val = 0;
		buf[i].next = buf[i].prev = 0;
	}
	bCnt = 0;
	head = tail = 0;
	head = buf[bCnt++].alloc(0, 0, 0);
}

node* find(int data) {
	node* ptr = head;
	for (; ptr->next; ptr = ptr->next) {
		if (ptr->next->val > data) {
			return ptr;
		}
	}
	return 0;
}

void insert(int data) {
	if (tail == 0) {
		head->next = tail = buf[bCnt++].alloc(data, 0, 0);
	}
	else {
		node* ptr = find(data);
		if (ptr == 0) {
			tail->next = buf[bCnt++].alloc(data, 0, tail);
			tail = tail->next;
		}
		else {
			node* temp = buf[bCnt++].alloc(data, ptr->next, ptr);
			ptr->next->prev = temp;
			ptr->next = temp;
		}
	}
}

int remove(int index) {
	int idx = 0;
	int res = -1;
	node* ptr = head;
	for (; ptr->next; ptr = ptr->next) {
		if (idx == index) {
			res = ptr->next->val;
			if (ptr->next == tail) tail = ptr;
			if(ptr->next->next) ptr->next->next->prev = ptr;
			ptr->next = ptr->next->next;
			
			break;
		}
		idx++;
	}
	return res;
}

int searchByIndex(int index) {
	int idx = 0;
	int res = -1;
	node* ptr = head;
	for (; ptr->next; ptr = ptr->next) {
		if (idx == index) {
			res = ptr->next->val;
			break;
		}
		idx++;
	}
	return res;
}