링크드리스트의 실전적 구현

요새는 라이브러리를 사용하여 코딩테스트를 진행하는 경우가 많지만, 가끔 직접 자료구조를 구현해야할 경우도 생긴다. 클래스로 아름답게 구현할 수도 있겠지만 빠르고 실수가 적도록 구현을 하기 위해 실전적인 포맷을 정리해보려 한다.

그리고 알다시피 메모리의 할당 및 해제에는 큰 cost가 들기 때문에 기본적으로 node pool을 활용한다. 문제의 메모리 제약사항을 잘확인해서 적당한 크기로 설정하자.

구현방식은 노드의 추가 위치에 따라 약간 다르므로 나눠서 정리하겠다.

노드를 맨 앞에 추가하는 경우

struct Node {  
	int value;  
	Node* next;  
}  
  
Node buf[100000000];  
int bufCount;  
  
Node* head;  
  
Node* myAlloc(int value, Node* next) {  
	buf[bufCount].value = value;  
	buf[bufCount].next = next;  
	return &buf[bufCount++];  
}  
  
void addNode(int value) {  
	if (head == nullptr) {  
		head = myAlloc(value, nullptr);  
		last = head;  
	} else {  
		last->next = myAlloc(value, nullptr);  
		last = last->next;  
	}  
}  

예를 들어 이를 이용해 스택을 구현한다치면 맨 앞에 노드를 추가하고 pop시에는 head를 한칸 앞으로 이동시키면 된다. 물론 꼭 리스트를 써야하는 상황이 아니라면 큰 배열에 stack pointer 변수 하나로 구현하는것이 훨씬 간단하긴 하다.

노드를 맨 뒤에 추가하는 경우

맨 앞에 추가하는 경우보다 코드가 조금 더 복잡하다. 아무래도 last 노드를 필요로 하기 때문에 그런 것 같다. 아무래도 분기도 있고 하다보니. 따라서 제약조건이 없다면 무조건 맨 앞에 추가하는 방식을 사용하도록 하자. 다만 리스트를 이용해서 Queue를 구현하는 경우는 이 방식을 사용해야 할 것이다.

struct Node {  
	int value;  
	Node* next;  
}  
  
Node buf[100000000];  
int bufCount;  
  
Node* head;  
Node* last;  
  
Node* myAlloc(int value, Node* next) {  
	buf[bufCount].value = value;  
	buf[bufCount].next = next;  
	return &buf[bufCount++];  
}  
  
void addNode(int value) {  
	if (head == nullptr) {  
		head = myAlloc(value, nullptr);  
		last = head;  
	} else {  
		last->next = myAlloc(value, nullptr);  
		last = last->next;  
	}  
}