연결 리스트 Q1. 정렬 연결 리스트에 값 삽입하기

자료구조 C 실습 · 연결 리스트 · Q1

연결 리스트 Q1. 정렬 연결 리스트에 값 삽입하기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section A Linked List insertSortedLL

이미 정렬된 단일 연결 리스트가 있을 때, 새 값을 적절한 위치에 끼워 넣고 그 인덱스까지 반환하는 문제다. 핵심은 새 노드를 직접 연결하는 것보다, 먼저 몇 번째 자리에 들어가야 하는지 찾고 기존 `insertNode`를 재사용하는 흐름이다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Linked_List\Q1_A_LL.c

대상 함수: insertSortedLL

카테고리: 연결 리스트

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Insert an integer to the sorted linked list
• 2: Print the index of the most recent input value
• 3: Print sorted linked list
• 0: Quit
• Input an integer that you want to add to the linked list
• The resulting linked list is

핵심 구현 흐름

STEP 1

head부터 시작해 새 값보다 작은 노드를 지나갈 때마다 인덱스를 하나씩 늘린다.

STEP 2

처음으로 `item`보다 크거나 같은 값을 만나면 그 위치가 삽입 지점이 된다.

STEP 3

찾아낸 인덱스를 `insertNode`에 넘겨 연결 작업은 헬퍼 함수에 맡긴다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: insertSortedLL

int insertSortedLL(LinkedList *ll, int item)
{
	// 리스트 자체가 예기치 못하게 비어있는 오류 상황이라면 
	if (ll == NULL)
		return -1;

	int index = 0;                // 내가 들어갈 자리가 몇 번째(인덱스)인지 셀 변수
	ListNode *cur = ll->head;     // 첫 번째 노드부터 출발

	// 나(item)보다 더 큰 놈이 나타날 때까지 계속 다음 칸으로 전진
	// (만일 나보다 큰 놈이 없으면 끝(NULL)까지 갈 테니 맨 뒤에 서게 됨)
	while (cur != NULL && cur->item < item)
	{
		cur = cur->next;
		index++;              // 한 칸 뒤로 갈 때마다 자리 번호도 1 증가시킴
	}

	// 알맞은 자리를 찾았으니 기존에 밑에 만들어져있는 insertNode 함수를 꿀 빨며 호출함
	// (알아서 연결 고리 끊고 이어주는 복잡한 과정은 insertNode가 다 해줌)
	insertNode(ll, index, item);

	return index;             // 내가 들어간 자리 번호를 반환해 줌 (보통 성공 여부나 인덱스 리턴함)
}

구현할 때 체크할 점

• 빈 리스트인 경우를 따로 처리하지 않으면 head 접근에서 바로 터진다.
• 정렬 조건이 `<`인지 `<=`인지에 따라 같은 값의 위치가 달라진다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 핵심은 새 노드를 직접 연결하는 것보다, 먼저 몇 번째 자리에 들어가야 하는지 찾고 기존 `insertNode`를 재사용하는 흐름이다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.