Chapter 04. 단순 연결 리스트의 ADT(추상 자료형)와 구현(1)

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

앞서 다룬 예제도 연결 리스트로 볼 수 있지만, 완벽한 형태의 연결 리스트는 아니었습니다. 이번 시간부터 본격적으로 연결 리스트를 공부하게 됩니다. 처음 공부할 내용은 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 '단순 연결 리스트'입니다.

---

기능적으로 무엇인가를 변경하거나 추가하지 않는다면 ADT를 변경할 이유는 없습니다. 하지만 이번 시간에는 연결 리스트에 정렬 관련 기능을 추가하기 위해서 ADT를 조금 확장하고자 합니다. 확장된 ADT는 다음과 같습니다.

void ListInit(List* plist);

void LInsert(List* plist, LData data);

int LFirst(List* plist, LData* pdata);

int LNext(List* plist, LData* pdata);

LData LRemove(List* plist);

int LCount(List* plist);

void SetSortRule(List* plist, int (*comp)(LData d1, LData d2));
//리스트에 정렬의 기준이 되는 함수를 등록한다.

위 ADT에 새로 추가된 함수는 SetSortRule이 전부입니다. 해당 함수는 데이터의 정렬을 담당합니다. 해당 함수의 매개변수를 보면 함수 포인터를 받고 있습니다. 따라서 해당 매개변수를 보고 다음과 같은 함수의 정의가 필요할 것임을 알 수 있습니다.

int comp(LData d1, LData d2)
{
	if (d1 < d2) return 0;
	else return 1;
}

위 함수는 두 개의 d1, d2를 비교하여 무엇이 더 큰 값인지를 판단합니다. 그리고 그 결과를 반환합니다. 이 결과를 바탕으로 우리는 데이터를 정렬할 수 있습니다. 반환하는 값은 굳이 0과 1일 필요는 없습니다.

 

그리고 위의 ADT에 명시되어 있지는 않지만 우리는 다음과 관련해서 결정을 해야 합니다.

 "새 노드를 추가할 때, 리스트의 머리와 꼬리 중 어디에 저장을 할 것인가?"

두 가지 방법 모두 장점과 단점이 있습니다. 우선 머리에 추가할 경우 장점과 단점은 다음과 같습니다.

• 장점 : 포인터 변수 tail이 불필요하다.
• 단점 : 저장된 순서를 유지하지 않는다.

반면 꼬리에 추가할 경우의 장점과 단점은 다음과 같습니다.

• 장점 : 저장된 순서가 유지된다.
• 단점 : 포인터 변수 tail이 필요하다.

어떠한 방법이 더 좋다고 판단할 성격의 문제는 아닙니다. 다만, 비교적 많은 수의 자료구조 서적들, 그리고 이 책의 저자는 노드를 머리에 추가하는 방식으로 연결 리스트를 구현하는 것을 선호합니다. 그 이유는 다음과 같습니다.

• 포인터 변수 tail을 유지하기 위해 넣어야 할 부가적인 코드가 번거롭게 느껴질 수 있다.
• 리스트 자료구조는 저장된 순서를 유지해야 하는 자료구조가 아니다.

---

앞선 예제에서 구현한 연결 리스트는 새로운 노드를 꼬리에 붙이는 구조를 가졌습니다. 그리고 head 포인터가 가장 첫 번째의 노드를 가리켰습니다. 그렇기 때문에 이 노드들을 추가, 삭제, 조회하는 방법에 있어 첫 번째 노드와 두 번째 이후의 노드에 차이가 있었습니다. head 포인터를 통해서 가장 먼저 첫 번째 노드를 확인하고, 그 이후부터는 반복문과 next 멤버 변수를 통해서 조회했기 때문입니다.

 

그래서 이 책의 저자는 다음과 같은 구조로 리스트를 구현할 것을 제시했습니다. 새로 추가되는 노드는 머리에 붙입니다. 이로써 tail 포인터 변수는 사라집니다. 그리고 head 포인터가 첫 번째 노드를 바로 가리키게 하지 않고 더미 노드를 가리키게 합니다. 더미 노드는 유효한 데이터를 지니지 않는 빈 노드를 의미합니다. head 포인터가 더미 노드를 가리키게 하고 이후 더미 노드가 첫 번째 노드를 가리키게 함으로써, 실질적으로 head 포인터는 첫 번째 노드를 가리키지 않고, 또 첫 번째 노드라고 하는 것은 실제로는 더미 노드 뒤에 위치하기 때문에 위치적으로는 두 번째 노드가 됩니다.

 

이렇게 head 포인터와 첫 번째 노드 사이에 더미 노드를 추가하게 되면, 조회 과정을 모두 일관된 형태로 구현할 수 있게 됩니다.