연결 리스트란?
연결 리스트(Linked List)는 데이터를 비연속적인 메모리 공간에 저장하는 선형 자료 구조입니다. 각 노드는 실제 데이터와 함께 다음 노드의 주소를 가리키는 포인터를 포함하고 있으며, 포인터를 따라가며 순차적으로 접근할 수 있습니다.
문제 정의
이 문제에서는 하나의 연결 리스트가 주어지며, 리스트의 모든 요소가 아니라 대체(alternate)되는 요소, 즉 홀수 번째 위치의 노드 값만 출력해야 합니다.
입력 : 2 -> 4 -> 1 -> 67 -> 48 -> 90 출력 : 2 -> 1 -> 48
설명 − 연결 리스트에서 1번째, 3번째, 5번째 노드의 값만 순서대로 출력합니다.
접근 방법: 플래그 변수 활용
가장 직관적인 방법은 플래그(flag) 변수를 사용하는 것입니다. 플래그를 0으로 초기화한 뒤 노드를 순회하면서 다음 규칙을 적용합니다.
- 플래그가 0이면 현재 노드의 값을 출력하고 플래그를 1로 변경합니다.
- 플래그가 1이면 값을 출력하지 않고 플래그를 0으로 되돌립니다.
- 매번 다음 노드로 이동합니다.
이렇게 하면 노드를 하나씩 건너뛰면서 원하는 값만 출력할 수 있습니다.
C++ 구현 예제 (반복문)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void printAlternateNode(struct Node* head) {
int flag = 0;
while (head != NULL) {
if (flag == 0) {
printf(" %d ", head->data);
flag = 1;
}
else
flag = 0;
head = head->next;
}
}
void insertNode(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main() {
struct Node* head = NULL;
insertNode(&head, 23);
insertNode(&head, 4);
insertNode(&head, 98);
insertNode(&head, 5);
insertNode(&head, 71);
printAlternateNode(head);
return 0;
}실행 결과
71 98 23
위 코드는 새 노드를 항상 리스트 맨 앞에 삽입하는 방식으로 구성했기 때문에, 최종 리스트는 71 → 5 → 98 → 4 → 23이 되고, 여기서 홀수 번째 노드인 71, 98, 23이 출력됩니다.
재귀를 이용한 구현
반복문 대신 재귀 호출로도 동일한 결과를 얻을 수 있습니다. 현재 노드의 값을 출력한 뒤, 다다음 노드(next->next)를 인자로 함수를 다시 호출하면 됩니다.
void printAlternateNode(struct Node* head) {
if (head == NULL)
return;
printf(" %d ", head->data);
if (head->next != NULL)
printAlternateNode(head->next->next);
}재귀 방식은 코드가 훨씬 간결하다는 장점이 있지만, 리스트가 매우 길 경우 호출 스택이 깊어져 스택 오버플로우가 발생할 수 있습니다. 따라서 데이터 크기에 따라 반복문 방식과 재귀 방식을 적절히 선택하는 것이 좋습니다.
마무리
연결 리스트의 대체 노드 출력은 플래그 변수 또는 재귀 호출을 통해 O(n) 시간 복잡도로 해결할 수 있습니다. 두 방식 모두 별도의 추가 공간 없이 원본 리스트를 유지한 채 처리할 수 있다는 공통된 장점이 있습니다.