Page 388 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

09 return ptr; /* 검색 성공 */
10
11 ptr = ptr->next;
12
13 return NULL; /* 검색 실패 */
14
15 (실습 9-8[C]에서 계속)

노드를 검색하는 Search 함수
Search 함수는 리스트에서 노드를 선형 검색하는 함수입니다. 머리 노드부터 뒤쪽 포인터를
이용해 순서대로 스캔합니다. 이때 머리 노드는 더미 노드가 아니라 더미 노드의 다음 노드입

니다. 즉, 그림 9-23에서 list->head가 가리키는 더미 노드의 뒤쪽 포인터가 가리키는 노드
A가 머리 노드입니다. 따라서 검색을 시작하는 노드의 위치는 list->head가 가리키는 노드가
아닌 list->head->next가 가리키는 노드입니다.

head 더미 노드입니다.

－ A B C D E

머리 노드부터 검색을 시작합니다.
[그림 9-23] 노드 검색의 시작 위치
더미 노드, 머리 노드, 꼬리 노드를 가리키는 포인터가 head, head->next, head->prev임을 다시 한 번 확인하고 넘어
가세요.

Node *형의 포인터 a, b, c, d, e가 각각 노드 A, 노드 B, ..., 노드 E를 순서대로 가리키는 경우
각 노드를 가리키는 식은 다음과 같습니다. 각각의 식은 노드 자신을 의미합니다.

더미 노드 head e->next d->next->next a->prev b->prev->prev
노드 A a head->next e->next->next b->prev c->prev->prev
노드 B b a->next head->next->next c->prev d->prev->prev
노드 C c b->next a->next->next d->prev e->prev->prev
노드 D d c->next b->next->next e->prev head->prev->prev
노드 E e d->next c->next->next head->prev a->prev->prev

Search 함수는 while문으로 노드를 하나씩 스캔하는 과정에서 비교 함수인 compare 함수
를 사용합니다. compare 함수로 비교한 결과가 0이면 검색 성공이며 찾은 노드에 대한 포인

388 C 알고리즘