[알고리즘] 단순 연결리스트 - 방문 연산, 탐색 연산, 합병 연산

단순 연결 리스트의 방문 연산

• 방문 연산 -> 리스트 상의 노드를 순차적으로 방문

1) 반복 기법

void display(LIstNode* head) {
	ListNode* p = head;
	while (p != NULL) {
		printf("%d->", p->data);
		p = p->link;
	}
	printf("/n")
}

//출력문 예시
// 1->2->3->5->10->

• p에 head 값을 준다.
• p가 NULL에 도달할때까지 while문을 반복해 리스트 안의 모든 데이터를 탐색하여 출력한다.

 

 

2) 순환 기법

void display_recur(LIstNode* head) {
	ListNode* p = head;

	if (p != NULL) {
		printf("%d->", p->data);
		display_recur(p->link);
	}
}

//출력문 예시
// 1->2->3->5->10->

• 결과는 첫번째 방법과 똑같지만 재귀호출 방식을 사용했다.

 

단순 연결 리스트의 탐색 연산

- 특정한 데이터 값을 갖는 노드를 찾는 연산.

 

 

ListNode* search(ListNode* head, int x) { // x는 찾을 데이터 값
	ListNode* p;
	p = head;

	while (p != NULL) {
		if (p->data == x) return p; // 탐색 성공
		p = p->link;
	}
	return p; // 탐색에 실패할 경우 NULL 반환
}

 

int x는 찾을 데이터 값이다. 현재 position을 뜻하는 ListNoe형 포인터 변수 p에는 head값을 넣어준다.

p는 head에서 시작해서 찾고자 하는 데이터와 같은 값이 나올 때까지 while문을 돌면서 탐색한다. 탐색할 값을 찾으면 if문 조건에 걸리게 되며 노드 p를 반환한다. 탐색에 실패할 경우 p는 결국 NULL에 도달할 것이며 NULL을 반환할 것이다.

 

단순 연결 리스트의 합병 연산

- 합병 연산은 2개의 리스트를 합하는 연산이다.

합병 연산은 3가지의 경우의 수가 있다

1.  첫 번째 리스트가 비어있을 경우
2. 두 번째 리스트가 비어있을 경우
3. 첫 번째, 두 번째 리스트 모두 비어있지 않을 경우

이를 생각하며 코드를 구상하면 된다!

 

ListNode* contact(ListNode* head1, ListNode* head2) {
	ListNOde* p;
	if (head1 == NULL) return head2; // head1의 리스트가 비어있을 경우
	else if (head2 == NULL) return head1; // head2의 리스트가 비어있을 경우
	else { // 둘 다 비어있지 않을 경우
		p = head;
		while (p->link != NULL) { // head1의 끝에 도달할때까지
			p = p->link; // p가 head1의 마지막 노드가 됨.
		}
		p->link = head2; //head1의 마지막 노드를 head2에 연결
		return head1; // head1에 head2가 연결되었으므로 head1을 return
	}
}