여기에서는 반복 및 재귀 접근 방식을 사용하여 연결 목록의 길이를 찾는 방법을 볼 것입니다. 헤드 포인터가 주어지면 길이를 얻으려면 다음 단계를 따라야 합니다.
-
반복적 접근의 경우 -
-
현재 포인터가 null이 아닐 때까지 목록의 선두를 잡고 다음 노드로 이동하여 개수를 늘립니다.
-
-
재귀적 접근의 경우 -
- 헤드를 인수로 전달, 기본 조건은 인수가 null인 경우 0을 반환하고, 그렇지 않으면 재귀적으로 목록에 들어가 현재 노드에서 다음 노드를 보내고 1 + 하위 목록의 길이를 반환합니다.
예시
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int data) {
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = (*start);
(*start) = new_node;
}
int count_recursive(Node* start) {
if (start == NULL)
return 0;
return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
int count = 0;
Node* current = start;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
int main() {
Node* start = NULL;
append(&start, 1);
append(&start, 3);
append(&start, 1);
append(&start, 2);
append(&start, 1);
cout << "Node count using iterative approach: " << count_iterative(start) << endl;
cout << "Node count using recursion: " << count_recursive(start);
} 출력
Node count using iterative approach: 5 Node count using recursion: 5