[SWEA] 2. 링크드 리스트

오늘은 링크드 리스트에 관한 내용을 공부하였다. 링크드 리스트의 경우 코딩 테스트 문제들에서는 한 번도 사용한 기억이 없는 것 같다. 보통 배열을 사용하거나 요즘 들어서는 vector를 사용하는 경우가 더 많았던 것 같다. 그래서 링크드 리스트는 학교 수업에서만 몇 번 사용한 것 같다. 하지만 학교 수업에서 배열을 이용하여 huffman encoding을 하려고 했을 때 배열로 구현하려다가 실패하고 링크드 리스트로 구현했던 기억이 있다. 오늘 들은 강의에서도 코딩 테스트 문제에서 링크드 리스트는 많이 쓰이는 자료구조라고 하니 이렇게 배열이나 vector 보다 링크드 리스트가 편한 경우도 있나 보다!

 

강의자료의 처음에 메모리 풀이라는 정적 할당의 한 방식을 보았다. 처음 보는 방식이었는데 되게 신기하였다.

struct Node {
	int data;
	Node* next;
};

Node node[MAX_NODE];
int nodeCnt;
Node* head;

Node* getNode(int data) {
	node[nodeCnt].data = data;
	node[nodeCnt].next = nullptr;
	return &node[nodeCnt++];
}

위와 같이 평소에는 linked list를 사용할 때 malloc을 이용하여 동적으로 메모리를 할당하는데 이 경우 미리 node 구조체의 메모리를 여러 개 확보해놓고 문제를 푸는 식이었다. linked list는 중간에 메모리를 할당하고 해제하는 것들이 조심스러워 코딩 테스트 문제에는 잘 사용하지 않았는데 이러한 방식이면 문제의 크기가 주어진 코딩 테스트 문제들에서는 충분히 활용 가능할 것 같았다. 

 

그다음에는 single linked list와 double linked list에 관하여 삽입 삭제 탐색에 관한 함수들에 대해 공부하고 기본 문제 풀이를 하였다. 구현을 다 하기는 했지만 한 번에 구현에 성공하지는 못하고 디버깅을 하며 중간에 삐걱거린 부분이 좀 많은 것 같다. 주어진 문제에서 double linked list에서 tail을 변수로 제공하지 않아 tail을 사용하지 않고 연습을 하는 문제인 줄 알았는데 설명 강의를 들으니 tail을 사용하여 문제를 푼다고 하였다. tail을 사용하여 문제를 다시 한번 풀어봐야겠다. 물론 오늘 배운 링크드 리스트를 STL을 사용하여 쉽게 사용할 수 있겠지만 어제 들은 교수님의 말씀처럼 이렇게 사소한 것들이 좋은 개발자를 만드는 것이지 않을까 싶다!