우리 금쪽이가 C 기초를 벼락치기 하자마자
갑자기 바로 아주 무서운 문제들을 풀게 되었어요 ~ 😢
금쪽이들이 겁먹지 않도록 선생님이 아주 쉽게 해석해볼게요!
Q1_A_LL (insertSortedLL)
문제 원문 1. (insertSortedLL)
1. (insertSortedLL) Write a C function insertSortedLL() that asks the user to input an integer,
then inserts it into the linked list in ascending order. The function, insertSortedLL(), should
not allow inserting an integer if it already exists in the current linked list. The function should return
the index position where the new item was added; if the function could not complete successfully, it
should return a value of -1. You can assume that the linked list is either a sorted linked list or an
empty list.
The function prototype is given as follows:
int insertSortedLL(LinkedList *ll, int item);
If the current linked list is: 2, 3, 5, 7, 9.
Calling insertSortedLL() with a value of 8 will result in the following linked list:
2, 3, 5, 7, 8, 9.
The function should return the index position where the new item was added as follows:
The value 8 was added at index 4
If the current linked list is: 5, 7, 9, 11, 15.
Calling insertSortedLL() with a value of 7 will result in the following linked list:
5, 7, 9 , 11, 15.
The function does not complete successfully (does not insert the value of 7 to the linked list)
hence it should return a value of -1:
The value 7 was added at index -1
Some sample inputs and outputs are given as follows:
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:
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 2
The resulting linked list is: 2
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 3
The resulting linked list is: 2 3
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 5
The resulting linked list is: 2 3 5
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 7
The resulting linked list is: 2 3 5 7
Please input your choice(1/2/3/0):1
Input an integer that you want to add to the linked list: 9
The resulting linked list is: 2 3 5 7 9
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 8
The resulting linked list is: 2 3 5 7 8 9
Please input your choice(1/2/3/0): 2
The value 8 was added at index 4
Please input your choice(1/2/3/0):3
The resulting sorted linked list is: 2 3 5 7 8 9
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 5
The resulting linked list is: 2 3 5 7 8 9
Please input your choice(1/2/3/0): 2
The value 5 was added at index -1
Please input your choice(1/2/3/0):3
The resulting sorted linked list is: 2 3 5 7 8 9
Please input your choice(1/2/3/0): 1
Input an integer that you want to add to the linked list: 11
The resulting linked list is: 2 3 5 7 8 9 11
Please input your choice(1/2/3/0): 2
The value 11 was added at index 6
Please input your choice(1/2/3/0):3
The resulting sorted linked list is: 2 3 5 7 8 9 11
🍀 문제 전체 해설
🌼 insertSortedLL 함수, 어떤 아이일까요?
“자, 여러분~
지금 우리가 만나볼 친구는요,
정렬된 연결 리스트에 새 숫자를 조심스럽게~
하지만 정확하게 넣어주는 아이예요.” 😊
📌 우리가 해야 할 일은요:
- 숫자를 하나 입력 받아요.
- 이미 들어 있는 숫자면 이렇게 말해요:
❌ “넌 이미 있어~ 넣으면 안 돼~ -1 줄게~”
- 새 숫자가 들어가야 할 위치를 알아서 찾아서 예쁘게 넣어주는 거예요. 오름차순으로요.
- 그리고 말해줘요:
✅ “넌 잘 들어갔어~ 인덱스는 3번이야~”
그럴 수 있어요~ 중복도, 삽입도, 실패도 다~ 괜찮아요. 😊
🧾 함수 이름과 형태
c
int insertSortedLL(LinkedList *ll, int item);ll: 연결 리스트예요.item: 삽입할 숫자.- return 값:
- 성공 → 해당 인덱스
- 실패 → -1
“이건 훈육이 아니라 교육이에요~ 실패도 학습이랍니다~” 💡
🧩 예시로 함께 해봐요
💖 예시 1 — 잘 들어간 경우
c
리스트: 2 → 3 → 5 → 7 → 9
삽입할 값: 8
결과 리스트: 2 → 3 → 5 → 7 → 8 → 9
리턴값: 4
“아~ 8은 7이랑 9 사이가 편하겠네요~ 4번째에 조용히 앉아볼까요?” ✨
😢 예시 2 — 이미 있는 값
c
리스트: 5 → 7 → 9 → 11 → 15
삽입할 값: 7
리턴값: -1“너무나 미안하지만... 7은 이미 있어요~
한 번 더 안아주세요~ 🤗”
🎮 사용자 인터페이스 흐름 예시
makefile
1: 숫자 삽입
2: 최근 삽입값 인덱스 확인
3: 리스트 출력
0: 종료📍실행 흐름은 이렇게 부드럽게 흘러가요:
“사용자가 선택하고, 값을 넣고, 결과를 보고~
우리 코드도 이렇게 감정선이 필요해요~ 😌”
🧵 코드 원문
//////////////////////////////////////////////////////////////////////////////////
/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 1 */
//////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
//////////////////////////////////////////////////////////////////////////////////
typedef struct _listnode{
int item;
struct _listnode *next;
} ListNode; // You should not change the definition of ListNode
typedef struct _linkedlist{
int size;
ListNode *head;
} LinkedList; // You should not change the definition of LinkedList
///////////////////////// function prototypes ////////////////////////////////////
//You should not change the prototype of this function
int insertSortedLL(LinkedList *ll, int item);
void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode *findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
//////////////////////////// main() //////////////////////////////////////////////
int main()
{
LinkedList ll;
int c, i, j;
c = 1;
//Initialize the linked list 1 as an empty linked list
ll.head = NULL;
ll.size = 0;
printf("1: Insert an integer to the sorted linked list:\n");
printf("2: Print the index of the most recent input value:\n");
printf("3: Print sorted linked list:\n");
printf("0: Quit:");
while (c != 0)
{
printf("\nPlease input your choice(1/2/3/0): ");
scanf("%d", &c);
switch (c)
{
case 1:
printf("Input an integer that you want to add to the linked list: ");
scanf("%d", &i);
j = insertSortedLL(&ll, i);
printf("The resulting linked list is: ");
printList(&ll);
break;
case 2:
printf("The value %d was added at index %d\n", i, j);
break;
case 3:
printf("The resulting sorted linked list is: ");
printList(&ll);
removeAllItems(&ll);
break;
case 0:
removeAllItems(&ll);
break;
default:
printf("Choice unknown;\n");
break;
}
}
return 0;
}
//////////////////////////////////////////////////////////////////////////////////
int insertSortedLL(LinkedList *ll, int item)
{
/* add your code here */
}
///////////////////////////////////////////////////////////////////////////////////
void printList(LinkedList *ll){
ListNode *cur;
if (ll == NULL)
return;
cur = ll->head;
if (cur == NULL)
printf("Empty");
while (cur != NULL)
{
printf("%d ", cur->item);
cur = cur->next;
}
printf("\n");
}
void removeAllItems(LinkedList *ll)
{
ListNode *cur = ll->head;
ListNode *tmp;
while (cur != NULL){
tmp = cur->next;
free(cur);
cur = tmp;
}
ll->head = NULL;
ll->size = 0;
}
ListNode *findNode(LinkedList *ll, int index){
ListNode *temp;
if (ll == NULL || index < 0 || index >= ll->size)
return NULL;
temp = ll->head;
if (temp == NULL || index < 0)
return NULL;
while (index > 0){
temp = temp->next;
if (temp == NULL)
return NULL;
index--;
}
return temp;
}
int insertNode(LinkedList *ll, int index, int value){
ListNode *pre, *cur;
if (ll == NULL || index < 0 || index > ll->size + 1)
return -1;
// If empty list or inserting first node, need to update head pointer
if (ll->head == NULL || index == 0){
cur = ll->head;
ll->head = malloc(sizeof(ListNode));
ll->head->item = value;
ll->head->next = cur;
ll->size++;
return 0;
}
// Find the nodes before and at the target position
// Create a new node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL){
cur = pre->next;
pre->next = malloc(sizeof(ListNode));
pre->next->item = value;
pre->next->next = cur;
ll->size++;
return 0;
}
return -1;
}
int removeNode(LinkedList *ll, int index){
ListNode *pre, *cur;
// Highest index we can remove is size-1
if (ll == NULL || index < 0 || index >= ll->size)
return -1;
// If removing first node, need to update head pointer
if (index == 0){
cur = ll->head->next;
free(ll->head);
ll->head = cur;
ll->size--;
return 0;
}
// Find the nodes before and after the target position
// Free the target node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL){
if (pre->next == NULL)
return -1;
cur = pre->next;
pre->next = cur->next;
free(cur);
ll->size--;
return 0;
}
return -1;
}
“자~ 이제 우리 코드 친구를 하나하나 만나볼까요?”
“괜찮아요, 천천히. 그럴 수 있어요~” 🌼
🎶 한줄한줄 해석 시작!
🔹 라이브러리 불러오기
c
#include <stdio.h>
#include <stdlib.h>“stdio는 말 그대로 ‘standard input/output’이에요~
printf,scanf같은 친구들이 여기 있어요.
stdlib은 메모리 관련 도우미들!malloc,free쓰려면 꼭 필요해요~”
🔹 노드 구조 정의하기
c
typedef struct _listnode{
int item;
struct _listnode *next;
} ListNode;“이 아이는 우리 연결 리스트의 기본 단위예요.
하나의 사탕이라고 생각해도 좋아요 🍬
숫자를 들고 있고, 다음 사탕을 가리키고 있어요!”
c
typedef struct _linkedlist{
int size;
ListNode *head;
} LinkedList;“이건 줄 전체를 관리하는 매니저예요.
몇 명이나 있는지(size), 첫 번째 사람이 누군지(head) 기억해요.”
🔹 함수 이름만 미리 알려주기
c
int insertSortedLL(LinkedList *ll, int item);“아직 코드는 없어요. 하지만 약속은 해줘야죠~
‘나 나중에 이런 함수 만들 거야~’ 하고 알려주는 거예요.” 👩🏫
🔹 메인 함수 시작!
c
int main()“우리 프로그램의 시작이에요. 엄마 같은 존재~ 🧡”
c
LinkedList ll;
int c, i, j;
c = 1;“ll은 리스트 하나를 만들고요,
c는 메뉴 선택, i는 넣을 숫자, j는 최근 삽입 위치를 기억해요.”
c
ll.head = NULL;
ll.size = 0;“리스트를 빈 상태로 만들어요.
아무것도 없을 땐 NULL! size는 당연히 0이겠죠?”
📋 메뉴 출력
c
printf("1: Insert ...\n");
...“우리 사용자가 편하게 선택할 수 있도록 안내문이에요.
친절은 코딩에서도 중요해요~ 💁♀️”
🔁 반복문
c
while (c != 0)“0을 입력하면 그만두고, 그 전까진 계속 돌아가요.
인생도 코딩도 반복이죠~ 그럴 수 있어요~”
🧭 switch문
c
switch (c)“사용자의 선택에 따라 알맞게 행동하게 해주는 구조예요.
선택지 별로 하나하나 대응해줄게요~ 😊”
[1번] 숫자 삽입
c
scanf("%d", &i);
j = insertSortedLL(&ll, i);
printList(&ll);“숫자(i)를 입력받고, 리스트에 넣고, 결과 보여주기!
아주 기특하죠~ 아이처럼 순수한 흐름이에요~ 👶”
[2번] 인덱스 출력
c
printf("The value %d was added at index %d\n", i, j);“방금 넣은 숫자가 몇 번째에 들어갔는지 알려줘요.
성공했든 실패했든, 확인은 중요해요.”
[3번] 리스트 출력 + 초기화
c
printList(&ll);
removeAllItems(&ll);“한 번 보여주고, 깔끔하게 치워요~
정리하는 습관, 너무 중요해요!🧼”
[0번] 종료 전 정리
c
removeAllItems(&ll);“떠나기 전엔 메모리도 깨끗하게~
잊지 말아요, free는 예의예요! 🙇♀️”
📌 나머지 함수들은?
printList: 리스트 예쁘게 보여주기removeAllItems: 전체 노드 싹 정리findNode: 몇 번째에 있는지 찾아주는 도우미insertNode: 삽입 도와주는 친구removeNode: 삭제하는 용감한 아이
“각각 역할이 다 있지만, 다 소중해요.
아이들처럼 각자 다른 성격이지만~ 조화롭게 어울려야 해요.” 💛
💬 선생님의 마무리 말씀
“코드를 배운다는 건,
단순히 글자를 쓰는 게 아니라요…
구조를 이해하고, 흐름을 보고,
실수해도 괜찮다고 말해주는 거예요.” 😊
❗ 정답 함수 insertSortedLL()는 아직 안 만들었어요.
우리가 같이 단계적으로 만들어갈 거니까 걱정 마세요~
정말 중요한 얘기예요, "그럴 수 있어요."
🎯 목표 정리부터!
우리가 만드는 insertSortedLL() 함수는요,
연결 리스트에 정수를 하나 넣되, 다음 조건을 반드시 지켜야 해요:
| 조건 | 설명 |
|---|---|
| 1️⃣ 오름차순 정렬 유지 | 작은 숫자부터 큰 숫자 순서대로 있어야 해요 |
| 2️⃣ 중복 허용 ❌ | 이미 있는 값이면 넣지 않고 -1을 반환해야 해요 |
| 3️⃣ 삽입 성공 시 ✅ | 몇 번째(index)에 들어갔는지 알려줘야 해요 |
💡 함수 시작부: 준비물 꺼내기
c
int insertSortedLL(LinkedList *ll, int item)
{
if (ll == NULL)
return -1;“먼저 리스트 자체가 비어 있는 건 아닌지 확인해요.
NULL이라면 조심해야 하니까요~
이런 기본 검사, 꼭 필요해요~ 😊”
c
if (ll->size == 0) {
insertNode(ll, 0, item);
return 0;
}“혹시 아무 숫자도 없는 빈 리스트라면요,
고민할 것 없이 그냥 맨 앞에 넣으면 돼요!
이럴 땐
insertNode함수로 0번째에 넣고, 0을 반환해요.”
🧶 리스트 순회 시작 – 자리 찾으러 고고!
c
ListNode *curr = ll->head;
int index = 0;“현재 보고 있는 노드를 curr로 지정해요.
우리가 리스트를 앞에서부터 하나하나 살펴보면서
이
curr이랑 비교할 거예요.
index는 몇 번째 자리인지 세는 역할이에요.”
c
while (curr != NULL)“리스트의 끝까지 다 볼 때까지 반복해요.
NULL이란 건 ‘다음 노드가 없다’는 뜻이에요.그러니
curr이 NULL이 될 때까지는 계속 돌아가야 해요!”
💥 중복 체크
c
if (curr->item == item) {
return -1;
}“어머~ 이미 똑같은 숫자가 있다면요?
그럴 땐 넣으면 안 되죠!
바로 -1을 반환하고 종료해요.
❗ 이건 진짜 중요해요.
'넌 이미 있어~ 한 번 더 안아주고 이번엔 쉬어가요~' 🤗”
🪄 삽입할 자리를 찾았다면?
c
if (curr->item > item) {
insertNode(ll, index, item);
return index;
}“지금 보고 있는 숫자가 item보다 크면요,
아~ 그 앞에 들어가면 되겠구나!
그러면 바로 그
index자리에 넣어줘요.그리고 삽입 성공했으니
index를 반환해요~ 🎉”
🚶 다음 노드로 이동하며 index도 증가
c
curr = curr->next;
index++;“이번엔 다음 노드로 이동해요.
그리고 한 칸 내려왔으니 인덱스도 1 증가시켜야죠~
이게 리스트 탐색의 기본이에요!” 😎
🛬 다 돌았는데도 더 큰 값이 없다면?
c
insertNode(ll, index, item);
return index;
}“끝까지 봤는데도 아직 안 넣었어요?
그럼 맨 끝에 넣어주면 돼요.
사실 이건 가장 흔한 상황 중 하나예요!
정렬 유지하면서 뒤에 조용히 자리 잡는 거죠~
‘넌 끝자리가 잘 어울리는구나~’ 🧸”
✅ 최종 코드 요약
c
int insertSortedLL(LinkedList *ll, int item)
{
if (ll == NULL) return -1; // 리스트가 존재하는지 확인
if (ll->size == 0) {
// 리스트가 비어있다면 0번째에 삽입
insertNode(ll, 0, item);
return 0;
}
ListNode *curr = ll->head;
int index = 0;
while (curr != NULL) {
if (curr->item == item)
return -1; // 중복된 값이라면 넣지 않기 ❌
if (curr->item > item) {
// 지금 자리가 삽입할 곳이라면 넣기
insertNode(ll, index, item);
return index;
}
curr = curr->next;
index++;
}
// 맨 끝까지도 못 들어갔으면 → 마지막에 넣기
insertNode(ll, index, item);
return index;
}
💬 선생님의 정리 멘트
“삽입이라는 건요, 자리를 ‘마음대로’ 정하는 게 아니라
그 아이가 가장 편안하고 조화롭게 들어갈 수 있는
‘정해진 질서’를 지켜주는 일이에요.” 🌷
“그리고 중복은 안 넣는다고 했죠?
‘넌 이미 있어~ 우리 서로 기억하고 있으니 이번엔 쉬어가요~’ 😊”
그래도 해야지 어떡해