이 글에서는 연결 리스트(Linked List)에서 주어진 인덱스에 해당하는 노드의 데이터를 출력하는 방법을 알아봅니다. 배열과 달리 연결 리스트는 일반적으로 인덱스 개념을 가지지 않기 때문에, 리스트를 처음부터 끝까지 순회하면서 원하는 위치에 도달했을 때 해당 노드의 데이터를 출력하는 방식으로 문제를 해결해야 합니다.
예를 들어, 연결 리스트에 29, 34, 43, 56, 88 다섯 개의 노드가 저장되어 있고 인덱스 값으로 1, 2, 4가 주어진다면, 출력 결과는 각 인덱스에 위치한 노드인 34, 43, 88이 됩니다.
예시
연결 리스트: 29->34->43->56->88 입력: 1 2 4 출력: 34 43 88
위 연결 리스트 표현에서 노란색으로 강조된 노드들이 바로 출력 대상이 되는 노드, 즉 지정된 인덱스에 위치한 노드들입니다.
접근 방법
이 문제는 포인터 하나와 초기값을 1로 설정한 카운터 변수를 활용하여 해결할 수 있습니다. 노드를 한 칸씩 순회할 때마다 카운터 값을 증가시키고, 카운터 값이 찾고자 하는 키(인덱스) 값과 일치하는지 확인합니다. 두 값이 일치하는 순간 해당 노드의 데이터를 출력하고, 포인터를 다음 노드로 이동시켜 같은 과정을 반복하면 원하는 인덱스에 있는 노드들을 모두 얻을 수 있습니다.
아래 코드는 위에서 설명한 알고리즘을 C 언어로 구현한 것입니다.
알고리즘
시작
단계 1 -> 구조체 타입의 노드 변수 생성
int형 data 선언
node 타입의 포인터 *next 선언
단계 2 -> struct node* intoList(int data) 함수 생성
malloc을 사용해 newnode 생성
newnode->data = data 설정
newnode->next = NULL 설정
newnode 반환
단계 3 -> void displayList(struct node *catchead) 함수 선언
struct node *temp 생성
IF catchead == NULL 이면
"리스트가 비어 있습니다" 출력
return
End
temp = catchead 설정
While (temp != NULL) 동안 반복
temp->data 출력
temp = temp->next 설정
End
단계 4 -> int search(int key, struct node *head) 함수 선언
int형 index 선언
struct node *newnode 생성
index = 0, newnode = head 설정
While (newnode != NULL && newnode->data != key) 동안 반복
index 증가
newnode = newnode->next 설정
End
return (newnode != NULL) ? index : -1
단계 5 -> main() 함수 내부
struct node* head = intoList(9)로 노드 생성
displayList(head) 호출
index = search(24, head) 설정
IF (index >= 0)
index 출력
ELSE
"리스트에서 찾을 수 없습니다" 출력
EndIF
종료
구현 예제
#include <stdio.h>
#include <stdlib.h>
//노드의 구조체 정의
struct node {
int data;
struct node *next;
};
struct node* intoList(int data) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = NULL;
return newnode;
}
//리스트를 출력하는 함수
void displayList(struct node *catchead) {
struct node *temp;
if (catchead == NULL) {
printf("List is empty.\n");
return;
}
printf("elements of list are : ");
temp = catchead;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
//요소를 탐색하는 함수
int search(int key,struct node *head) {
int index;
struct node *newnode;
index = 0;
newnode = head;
while (newnode != NULL && newnode->data != key) {
index++;
newnode = newnode->next;
}
return (newnode != NULL) ? index : -1;
}
int main() {
int index;
struct node* head = intoList(9); //리스트에 요소 삽입
head->next = intoList(76);
head->next->next = intoList(13);
head->next->next->next = intoList(24);
head->next->next->next->next = intoList(55);
head->next->next->next->next->next = intoList(109);
displayList(head);
index = search(24,head);
if (index >= 0)
printf("%d found at position %d\n", 24, index);
else
printf("%d not found in the list.\n", 24);
index=search(55,head);
if (index >= 0)
printf("%d found at position %d\n", 55, index);
else
printf("%d not found in the list.\n", 55);
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
elements of list are : 9 76 13 24 55 109 24 found at position 3 55 found at position 4