연결리스트 - 순회하기

연결리스트 순회 (traverse)

 

연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회(traverse) 한다고 말한다.

아래 함수는 입력된 문자열 word와 동일한 단어를 저장한 노드를 찾아서 그 노드의 주소를 반환한다. 그것을 위해서 연결리스트를 순회한다.

 

 Node *find(char *word) {       /* 검색할 단어를 받는다. */
 	Node *p = head;     /* p가 첫번째 head 노드를 가리키도록 함 */
 	while (p != NULL) {
 		if (strcmp(p->data, word)==0)    /* word : 내가 찾는 단어 */
 			return p;
 		p = p->next;
 	}
 return NULL;
}

 

검색할 단어를 먼저 받는다. 그리고 p가 head 노드를 가리키도록 한다.

 

p가 NULL 이 아닌 경우(=노드가 존재할 동안) p의 data 와 검색할 단어를 비교한다. 단어가 일치하면 p의 주소를 반환하고 그렇지 않으면 NULL을 반환한다.

 

 

 

아래 그림처럼 p는 head 노드를 가리키며, p가 오른쪽으로 한 칸씩 이동하는 형태이다.

 

 

 

 

 

 

 

다음은 연결리스트의 index번째 노드의 주소를 반환해보자.

 

Node *get_node(int index) {
 	if (index < 0)        /* 노드가 존재 x */
 		return NULL;
 	Node *p = head;       /* p가 head 노드를 가리킨다 */
 	for (int i=0; i<index && p!=NULL; i++)
 		p = p->next;
 	return p;
}

 

for (int i=0; i<index && p!=NULL; i++) 에서 p = NULL 일때는 p 가 오른쪽으로 한 칸씩 순회하는데 이때 범위를 벗어나게 될 때를 의미한다.

 

 

다음 그림과 같이 보면 이해가 쉽다.