연결 리스트(Linked List)가 주어졌을 때, 끝에서 n번째에 위치한 노드를 출력하는 것이 이번 글의 목표입니다. 여기서 중요한 점은 노드의 순서를 변경하지 않고, 단순히 마지막에서 n번째 노드의 값만 출력해야 한다는 것입니다.
예시
입력 -: 10 20 30 40 50 60
N = 3
출력 -: 40
위 예시에서 첫 번째 노드부터 차례대로 10, 20, 30, 40, 50, 60이 있으며, 끝에서 세 번째 노드는 40입니다.
효율적인 접근 방법
리스트 전체를 처음부터 끝까지 탐색하는 대신, 다음과 같은 효율적인 방법을 사용할 수 있습니다.
- 노드 구조체 타입의 임시 포인터(예:
temp)를 하나 선언합니다. - 이
temp포인터를 헤드(head) 포인터가 가리키는 첫 번째 노드로 설정합니다. - 카운터를 리스트의 전체 노드 개수로 설정합니다.
temp를count - n번 만큼temp → next로 이동시킵니다.temp → data값을 출력합니다.
이 방법을 사용하면 카운트가 5일 때, 반복문은 5 - 3 = 2번만 실행됩니다. 즉, 인덱스 0의 10에서 시작해 인덱스 1의 20, 그리고 인덱스 2의 30까지 이동하면 결과인 40에 도달하게 됩니다. 이처럼 리스트 전체를 끝까지 순회할 필요가 없으므로 시간과 메모리를 절약할 수 있습니다.
알고리즘
Start
Step 1 -> 노드 구조체와 temp, next, head 포인터 생성
struct node
int data
struct node *next, *head, *temp
End
Step 2 -> 리스트에 노드를 삽입하는 함수 선언
void insert(int val)
struct node* newnode = (struct node*)malloc(sizeof(struct node))
newnode->data = val
IF head == NULL
set head = newnode
set head->next = NULL
End
Else
Set temp = head
Loop While temp->next != NULL
Set temp = temp->next
End
Set newnode->next = NULL
Set temp->next = newnode
End
Step 3 -> 리스트를 출력하는 함수 선언
void display()
IF head == NULL
Print no node
End
Else
Set temp = head
Loop While temp != NULL
Print temp->data
Set temp = temp->next
End
End
Step 4 -> 연결 리스트의 끝에서 n번째 노드를 찾는 함수 선언
void last(int n)
Set temp = head
Loop For i = 0 and i < count - n and i++
Set temp = temp->next
End
Print temp->data
Step 5 -> main() 함수에서
struct node* head = NULL 로 노드 생성
n을 3으로 선언
insert(10) 함수 호출로 노드 삽입
display() 함수 호출로 리스트 출력
last(n) 함수 호출로 끝에서 n번째 노드 탐색
Stop
C 코드 구현 예제
#include<stdio.h>
#include<stdlib.h>
// 노드 구조체 정의
struct node{
int data;
struct node *next;
}*head,*temp;
int count=0;
// 리스트에 노드를 삽입하는 함수
void insert(int val){
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = NULL;
if(head == NULL){
head = newnode;
temp = head;
count++;
} else {
temp->next=newnode;
temp=temp->next;
count++;
}
}
// 리스트를 출력하는 함수
void display(){
if(head==NULL)
printf("no node ");
else {
temp=head;
while(temp!=NULL) {
printf("%d ",temp->data);
temp=temp->next;
}
}
}
// 연결 리스트의 끝에서 n번째 노드를 찾는 함수
void last(int n){
int i;
temp=head;
for(i=0;i<count-n;i++){
temp=temp->next;
}
printf(" %drd node from the end of linked list is : %d" ,n,temp->data);
}
int main(){
// 리스트 생성
struct node* head = NULL;
int n=3;
// 리스트에 요소 삽입
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);
insert(6);
// 리스트 출력
printf(" linked list is : ");
display();
// 끝에서 n번째 요소를 찾는 함수 호출
last(n);
return 0;
}
실행 결과
linked list is : 1 2 3 4 5 6
3rd node from the end of linked list is : 4
마무리
이 프로그램은 연결 리스트의 총 노드 개수를 미리 파악한 뒤, count - n번 만큼만 포인터를 이동시켜 원하는 노드를 찾습니다. 두 개의 포인터를 활용하는 투 포인터(two-pointer) 기법을 사용하면 한 번의 순회만으로도 끝에서 n번째 노드를 찾을 수 있어 더욱 효율적입니다. 실무에서는 리스트 길이를 미리 알 수 없는 경우가 많으므로, 상황에 맞는 최적의 방법을 선택하는 것이 중요합니다.