크래프톤 정글

크래프톤 정글 8기 - TIL 31일차 (링크드 리스트 - C)

고웅 2025. 4. 10. 16:33

TIL - 2025.04.10 (목요일)

📝 오늘 배운 것: C로 구현하는 링크드 리스트

4월 10일, 크래프톤 정글에 입소한 지 벌써 1달이 되었다.
1~4주 차까지는 알고리즘 위주로 학습했고, 이제부터는 C 언어로 자료구조를 구현하거나 문제를 풀어보는 활동을 4주간 진행할 예정이다.

링크드 리스트란?

링크드 리스트(Linked List)는 데이터를 순차적으로 저장하는 자료구조로, 각 요소가 포인터를 통해 다음 요소와 연결되어 있다.
배열과는 달리 메모리상에서 연속된 공간에 있지 않으며, 노드(Node)라는 단위로 구성된다.

노드는 보통 두 가지 요소를 가진다:

  1. 데이터(Data): 실제 저장 값
  2. 포인터(Next): 다음 노드의 주소 (또는 참조)
[1 | ●] → [2 | ●] → [3 | null]

🔹 링크드 리스트의 종류

종류 설명
단일 연결 리스트 한 방향으로만 연결됨 (next만 존재)
이중 연결 리스트 앞뒤로 연결됨 (prev, next 모두 존재)
원형 연결 리스트 마지막 노드가 첫 노드를 가리킴

🔹 꼭 알아야 할 개념들

개념 설명
노드(Node) 데이터와 다음 노드에 대한 참조를 가진 기본 단위
헤드(Head) 리스트의 첫 번째 노드
포인터(Reference) 다음 노드를 가리키는 변수
삽입/삭제 중간에 노드를 추가하거나 제거할 수 있음 (배열보다 효율적)
순회(Traversal) 처음부터 끝까지 차례로 노드를 따라가며 처리
Null 체크 마지막 노드의 다음은 null 또는 None임

구현 예시: insertSortedLL

구현 목표

정글에서 제공해 준 과제 리스트? 에 있는 Q1_A_LL은 insertSortedLL을 구현해야 하는 과제다. 이 insertSortedLL은 링크드 리스트에 입력되는 값이 정렬이 되어 입력이 되어야 한다.

문제 설명

insertSortedLL()라는 C 함수를 작성하시오.

  • 이 함수는 사용자에게 정수를 입력받아, 해당 값을 오름차순으로 정렬된 연결 리스트에 삽입한다.
  • 함수의 동작 요건:
    1. 사용자가 입력한 정수를 정렬된 연결 리스트에 오름차순으로 삽입한다.
    2. 중복된 값은 삽입하지 않는다.
    3. 삽입이 성공하면, 삽입된 위치의 인덱스(index)를 반환해야 한다.
    4. 삽입에 실패한 경우(예: 중복 또는 메모리 문제)에는 -1을 반환해야 한다.
    5. 연결 리스트는 항상 정렬된 상태이거나 비어 있는 상태라고 가정할 수 있다.

주요 로직 설명

ListNode *cur = ll->head; // 현재 탐색 위치
ListNode *prev = NULL;    // 삽입을 위한 이전 노드
int index = 0;
while (cur != NULL && cur->item < item) {
    prev = cur;
    cur = cur->next;
    index++;
}
  • 리스트를 순회하며 item이 들어갈 위치를 탐색
  • 중복된 값이 있는 경우 아래 조건에서 바로 종료

위에서부터 설명하면 prev 즉 이전 노드가 cur 노드 값으로 설정된다. 이후 cur 노드는 cur 노드의 next 즉 다음 연결된 노드로 이동을 하게 된다. 이후 문제 요구사항에 있던 인덱스 값 반환을 위해 index 값을 1 증가한다.

// 중복 탐지 시 -1 반환
if (cur != NULL && cur->item == item) {
    printf("❌ Duplicate detected: %d already exists at index %d\n", item, index);
    return -1;
}

이 때 cur 값이 item 값보다 커지면 while 문의 중지 조건에 걸려 반복을 그만두게 된 상태에서 현재 노드의 item 값이 삽입하려는 item 값과 같은지 검사한다. 이때 같은 값 즉 기존 값과 중복된 값이 들어온 경우 요구 조건에 맞게 -1을 반환하며 종료한다.

중복 값 입력시 동작

위 GIF 가 중복된 값이 들어왔을 때의 동작 예시이다.

새로운 노드 삽입 과정

값이 중복되지 않았을 경우 아래와 같은 코드가 실행된다.

ListNode *newNode = (ListNode *) malloc(sizeof(ListNode));
if (newNode == NULL) return -1;

newNode->item = item;
newNode->next = cur;
  • 새 노드를 생성하고 값을 할당
  • 새 노드가 가리킬 다음 노드는 현재 위치(cur)
if (prev == NULL)
    ll->head = newNode; // 맨 앞에 삽입
else
    prev->next = newNode; // 중간 또는 맨 뒤에 삽입
  • prev가 NULL이면 맨 앞(head)에 삽입
  • 그렇지 않으면 prev 뒤에 삽입

insertSortedLL 실행 이해

전체 코드

ListNode *cur = ll->head; // 탐색용
	ListNode *prev = NULL; // 삽입 시 사용
	int index = 0; // 문제 요구 사항에 should return the index 가 있었다.

	printf("\n[INSERT] Trying to insert %d into linked list...\n", item);

	// 삽입 위치 탐색
	while (cur != NULL && cur->item < item) {
		prev = cur;
		cur = cur->next;
		index++;
	}

	// 중복 탐지 시 -1 반환
	if (cur != NULL && cur->item == item) {
		printf("❌ Duplicate detected: %d already exists at index %d\n", item, index);
		return -1;
	}

	ListNode *newNode = (ListNode *) malloc(sizeof(ListNode)); // 메모리 동적 할당
	// 메모리 할당에 실패 한 경우 -1 반환
	if (newNode == NULL) {
		printf("❌ Memory allocation failed for %d\n", item);
		return -1;
	}

	newNode->item = item;
	newNode->next = cur;

	if (prev == NULL) {
		printf("🔗 Inserting %d at the head\n", item);
		ll->head = newNode;
	} else {
		printf("🔗 Inserting %d after %d\n", item, prev->item);
		prev->next = newNode;
	}

	ll->size++;
	printf("✅ Inserted %d at index %d | New size: %d\n", item, index, ll->size);

	// 현재 리스트 상태 출력 (없어도 무방함)
	printf("📌 Current list: ");
	ListNode *temp = ll->head;
	while (temp != NULL) {
		printf("%d ", temp->item);
		temp = temp->next;
	}
	printf("\n");

	return index;

😅 트러블 슈팅

prev와 cur등 포인터 변수를 이용해서 반복문을 돌리는 것에서 접근 방식을 떠올리는데 애를 먹었다. 또한 prev->next에 newNode를 연결하는 등 생각보다 왜 그렇게 설정을 하는지 이해가 되지 않아서 오랜 시간 이해를 위해 손으로 그려가면서 이해를 하려 노력했다. 

🧐 느낀 점

c언어... 너무 어렵다. 3년 만에 포인터와 구조체를 만나니 머리가 아프다.

🔚 마무리

링크드 리스트 삽입 함수를 직접 구현하면서, 자료구조의 개념뿐 아니라 C의 포인터와 메모리 할당에 대해서도 한층 깊이 이해할 수 있었다.
앞으로의 자료구조 과제도 기대되며, 이 과정을 차곡차곡 기록해 나갈 예정이다.

저작자표시 동일조건